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

DOI10.1142/S0218196798000132MaRDI QIDQ4354236zbMATH OpenOpenAlexFDO

Authors J.-C. 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

finitely generated semigroupstime complexityword problemisoperimetric functionsfinitely presented semigroups

Mathematics Subject Classification ID

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

Recommendations

• Space functions and space complexity of the word problem in semigroups.
• Isoperimetric functions of groups and computational complexity of the word problem
• Infinite string rewrite systems and complexity

Cites work

• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• A comparison of polynomial time reducibilities
• Context-Limited Grammars
• Data management support for database management
• Embedding Theorems with Amalgamation for Semigroups^†
• Gruppen mit vorgeschriebenem Wortproblem
• HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
• Hierarchies of Computable groups and the word problem
• Logical Reversibility of Computation
• On the geometry of semigroup presentations
• One-tape, off-line Turing machine computations
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• Subgroups of finitely presented groups
• 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
• Symmetric space-bounded computation
• Time- and tape-bounded Turing acceptors and AFLs

Cited in

(17)

• Space functions and space complexity of the word problem in semigroups.
• Complexity of the word problem for commutative semigroups of fixed dimension
• Groups finitely presented in Burnside varieties
• Isoperimetric functions of groups and computational complexity of the word problem
• Anisimov's theorem for inverse semigroups.
• scientific article; zbMATH DE number 1936760 (Why is no real title available?)
• 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
• Space functions of groups.
• On Subquadratic Derivational Complexity of Semi-Thue Systems
• DEHN FUNCTION AND LENGTH OF PROOFS
• A semigroup with linearithmic Dehn function
• Lower bounds on words separation: are there short identities in transformation semigroups?
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• Reductions and functors from problems to word problems
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY

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

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