Space Complexity and Word Problems of Groups

DOI10.1515/GCC.2009.261zbMath1185.68347OpenAlexW2127235208MaRDI 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

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Word problems of groups: formal languages, characterizations and decidability ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Free products of semigroups and monoids with a deterministic context-free word problem

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

This page was built for publication: Space Complexity and Word Problems of Groups