Counter machines, Crystallographic structures, Context-free languages, Periodic digraphs
Digital Object Identifier (DOI)
One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages DCLd,d=0,1,2,…, within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class DCLd. An intersection of d languages in DCL1 defines DCLd. We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in DCLd. The proof uses the following result: given a digraph Δ and a group G, there is a unique diagraph Γ such that G ≤ AutΓ,G acts freely on the structure, and Γ/G ≅ Δ.
Was this content written or created while at USF?
Citation / Publisher Attribution
Natural Computing, v. 15, issue 1, p. 97-113
This is a post-peer-review, pre-copyedit version of an article published in JNatural Computing. The final authenticated version is available online at: https://doi.org/10.1007/s11047-015-9527-0.
Scholar Commons Citation
Jonoska, Natasha; Krajcevski, Mile; and McColm, Gregory, "Counter Machines and Crystallographic Structures" (2016). Mathematics and Statistics Faculty Publications. 9.