2010/10/14 by Maria Monks, Monks, Maria
Computer Science · #03D05 #Computability, Logic, AI Algorithms #F.1.1 #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1010.3039
openalex publication_date 2010/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let A be a finite alphabet and let L contained in (A*)n be an n-variable language over A. We say that L is regular if it is the language accepted by a synchronous n-tape finite state automaton, it is quasi-regular if it is accepted by an asynchronous n-tape automaton, and it is weakly regular if it is accepted by a non-deterministic asynchronous n-tape automaton. We investigate the closure properties of the classes of regular, quasi-regular, and weakly regular languages under first-order logic, and apply these observations to an open decidability problem in automatic group theory.