Multipass automata and group word problems

DOI10.1016/j.tcs.2015.06.054zbMath1329.68160arXiv1404.7442OpenAlexW1615638926MaRDI QIDQ495997

Paul E. Schupp, Francesca Fiorenzi, Nicholas W. M. Touikan, Michel Coornaert, Tullio G. 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

word problemcontext-free languagefinitely 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)

Related Items (5)

The (nested) word problem ⋮ The language of self-avoiding walks ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ On a class of poly-context-free groups generated by automata ⋮ Groups whose word problems are not semilinear

Cites Work

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

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