Multipass automata and group word problems

DOI10.1016/J.TCS.2015.06.054zbMATH Open1329.68160arXiv1404.7442OpenAlexW1615638926MaRDI QIDQ495997FDOQ495997

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

Publication date: 16 September 2015

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• The (nested) word problem
• 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)