Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
From MaRDI portal
Publication:4354236
DOI10.1142/S0218196798000132zbMath0923.20043MaRDI QIDQ4354236
Publication date: 15 September 1997
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
word problem; time complexity; finitely generated semigroups; finitely presented semigroups; isoperimetric functions
20M05: Free semigroups, generators and relations, word problems
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
DEHN FUNCTION AND LENGTH OF PROOFS, THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY, LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS, FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY, Anisimov's Theorem for inverse semigroups, CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS, Space functions and space complexity of the word problem in semigroups., A strong geometric hyperbolicity property for directed graphs and monoids., Reductions and functors from problems to word problems, Groups finitely presented in Burnside varieties, Space functions of groups
Cites Work
- Data management support for database management
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- On the geometry of semigroup presentations
- Symmetric space-bounded computation
- Gruppen mit vorgeschriebenem Wortproblem
- A comparison of polynomial time reducibilities
- Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
- Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
- Time- and tape-bounded Turing acceptors and AFLs
- Subgroups of finitely presented groups
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- Embedding Theorems with Amalgamation for Semigroups†
- HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
- Context-Limited Grammars
- Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
- Hierarchies of Computable groups and the word problem
- One-tape, off-line Turing machine computations
- Logical Reversibility of Computation
