Space complexity and word problems of groups

DOI10.1515/GCC.2009.261MaRDI QIDQ5189807zbMATH OpenOpenAlexFDO

Authors Stephen R. Lakin, Richard M. Thomas

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)

Recommendations

• Space functions of groups.
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Space functions and space complexity of the word problem in semigroups.
• scientific article; zbMATH DE number 3877408
• scientific article; zbMATH DE number 1534404

Cites work

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

Cited in

(20)

• Complexity, combinatorial group theory and the language of palutators
• Complete problems for symmetric logspace involving free groups
• Word problems of groups: formal languages, characterizations and decidability
• Space functions of groups.
• Space functions and space complexity of the word problem in semigroups.
• C-graph automatic groups.
• A space efficient algorithm for group structure computation
• scientific article; zbMATH DE number 1263208 (Why is no real title available?)
• scientific article; zbMATH DE number 475370 (Why is no real title available?)
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• scientific article; zbMATH DE number 1534404 (Why is no real title available?)
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Topology of asymptotic cones and non-deterministic polynomial time computations
• The Compressed Word Problem for Groups
• The bounded and precise word problems for presentations of groups
• Words and mixing times in finite simple groups.
• Free products of semigroups and monoids with a deterministic context-free word problem
• Commutative semigroups with a context-free word problem
• Average-case complexity and decision problems in group theory.

This page was built for publication: Space complexity and word problems of groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189807)