Counter machines and crystallographic structures #MMPMID27616944
Jonoska N; Krajcevski M; McColm G
Nat Comput 2016[Mar]; 15 (1): 97-113 PMID27616944show ga
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 ???d, 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 ???d An intersection of d languages in ???1 defines ???d. 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 ???d. The proof uses the following result: given a digraph ? and a group G, there is a unique digraph ? such that G ? Aut ?, G acts freely on the structure, and ?/G ? ?.