Space Complexity and Word Problems of Groups
From MaRDI portal
Publication:5189807
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
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