Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
DOI10.1142/S0218196798000132zbMATH Open0923.20043OpenAlexW1986593186MaRDI QIDQ4354236FDOQ4354236
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
Recommendations
finitely generated semigroupstime complexityword problemisoperimetric functionsfinitely presented semigroups
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)
Cites Work
- Logical Reversibility of Computation
- Subgroups of finitely presented groups
- On the geometry of semigroup presentations
- A comparison of polynomial time reducibilities
- Symmetric space-bounded computation
- 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
- Embedding Theorems with Amalgamation for Semigroups†
- One-tape, off-line Turing machine computations
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
- Context-Limited Grammars
- 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
- Data management support for database management
- Gruppen mit vorgeschriebenem Wortproblem
- Hierarchies of Computable groups and the word problem
- Time- and tape-bounded Turing acceptors and AFLs
Cited In (17)
- Space functions and space complexity of the word problem in semigroups.
- Groups finitely presented in Burnside varieties
- Complexity of the word problem for commutative semigroups of fixed dimension
- Anisimov's theorem for inverse semigroups.
- Isoperimetric functions of groups and computational complexity of the word problem
- Title not available (Why is that?)
- 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)
