Space Complexity and Word Problems of Groups

DOI10.1515/GCC.2009.261zbMath1185.68347MaRDI QIDQ5189807

Richard M. Thomas, Stephen R. Lakin

Publication date: 11 March 2010

Published in: Groups – Complexity – Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc.2009.261

Mathematics Subject Classification ID

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

\(\mathcal C\)-graph automatic groups., Word problems of groups: formal languages, characterizations and decidability

Cites Work

• Groups and NTS languages
• Groups, the theory of ends, and context-free languages
• About the descriptive power of certain classes of finite string-rewriting systems
• The theory of ends, pushdown automata, and second-order logic
• Investigations on Hotz groups for arbitrary grammars
• Actions of finite groups of graphs and related automorphisms of free groups
• Eine neue Invariante für kontextfreie Sprachen
• On the Hotz group of a context-free grammar
• Group presentations, formal languages and characterizations of one- counter groups
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• Monoid presentations of groups by finite special string-rewriting systems
• The word problem