Counter machines and crystallographic structures.
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 withdcounters recognize the class 𝒟𝒞ℒdAn intersection ofdlanguages in 𝒟𝒞ℒ1defines 𝒟𝒞ℒd. We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of ad-dimensional periodic (di)graph and the class of languages in 𝒟𝒞ℒd. The proof uses the following result: given a digraph Δ and a groupG, there is a unique digraph Γ such thatG≤ Aut Γ,Gacts freely on the structure, and Γ/G≅ Δ.
Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA.
N
N
Jonoska
Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA.
M
M
Krajcevski
Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA.
G
G
McColm
Context-free languages; Counter machines; Crystallographic structures; Periodic digraphs