Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem

DOI10.1142/S0218196798000132zbMath0923.20043OpenAlexW1986593186MaRDI QIDQ4354236

Jean-Camille Birget

Publication date: 15 September 1997

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196798000132

zbMATH Keywords

word problemtime complexityfinitely generated semigroupsfinitely presented semigroupsisoperimetric functions

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) 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 (12)

LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS ⋮ On Subquadratic Derivational Complexity of Semi-Thue Systems ⋮ FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ Groups finitely presented in Burnside varieties ⋮ THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ DEHN FUNCTION AND LENGTH OF PROOFS ⋮ Reductions and functors from problems to word problems ⋮ Space functions of groups ⋮ Anisimov's Theorem for inverse semigroups

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

This page was built for publication: Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem