Physical Sciences and Mathematics Commons^™

Counter Machines And Crystallographic Structures, Natasha Jonoska, Mile Krajcevski, Gregory Mccolm

Mathematics and Statistics Faculty Publications

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 DCL_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 DCL_d. An intersection of d languages in DCL₁ defines DCL_d. We prove that there is …