Multipass automata and group word problems

DOI10.1016/J.TCS.2015.06.054MaRDI QIDQ495997zbMATH OpenOpenAlexFDO

Authors Michel Coornaert, Francesca Fiorenzi, Paul E. Schupp, Nicholas W. M. Touikan, Tullio Ceccherini-Silberstein

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.7442

zbMATH Keywords

context-free languageword problemfinitely generated groupmultipass automatonpushdown automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes.

Recommendations

• On groups whose word problem is solved by a counter automaton.
• Extended finite automata over groups
• scientific article
• Parallel poly-pushdown groups
• Automata with counters that recognize word problems of free products

Cites work

• scientific article; zbMATH DE number 3426894 (Why is no real title available?)
• scientific article; zbMATH DE number 3714968 (Why is no real title available?)
• scientific article; zbMATH DE number 3470032 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1842475 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3381862 (Why is no real title available?)
• A Finitely Presented Group Whose 3-Dimensional Integral Homology is not Finitely Generated
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Global rigidity of solvable group actions on \(S^1\)
• Groups with poly-context-free word problem.
• Groups, graphs, languages, automata, games and second-order monadic logic
• Groups, the theory of ends, and context-free languages
• On Context-Free Languages
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Semigroups, Presburger formulas, and languages
• \(C^1\)-actions of Baumslag-Solitar groups on \(S^1\)

Cited in

(7)

• Parallel poly-pushdown groups
• The (nested) word problem
• Automata with counters that recognize word problems of free products
• Groups whose word problems are not semilinear
• Groups whose word problems are accepted by abelian \(G\)-automata
• The language of self-avoiding walks
• On a class of poly-context-free groups generated by automata

This page was built for publication: Multipass automata and group word problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495997)