Space functions and space complexity of the word problem in semigroups.
DOI10.1007/s00037-012-0058-0zbMath1322.20054OpenAlexW2117390311MaRDI QIDQ395608
Publication date: 29 January 2014
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0058-0
algorithmsword problemtime complexityfinitely generated semigroupsfinitely presented semigroupsisoperimetric functionsspace complexityDehn functionsgenerators and relations in semigroups
Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Complexity of computation (including implicit computational complexity) (03D15) Asymptotic properties of groups (20F69) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Word problems, etc. in computability and recursion theory (03D40) Cancellation theory of groups; application of van Kampen diagrams (20F06) Turing machines and related notions (03D10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
- Filling length in finitely presentable groups.
- The geometry of the word problem for finitely generated groups.
- Free and fragmenting filling length.
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- On the geometry of semigroup presentations
- There is only one gap in the isoperimetric spectrum
- Isoperimetric and isodiametric functions of groups
- Isoperimetric functions of groups and computational complexity of the word problem
- On the complexity of reduction algorithms in Novikov-Boone constructions
- On the complexity of the identity problem for finitely defined groups
- Space functions of groups
- Subgroups of finitely presented groups
- On Dehn functions of free products of groups
- Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
- Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
- FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
- A non-cyclic one-relator group all of whose finite quotients are cyclic
This page was built for publication: Space functions and space complexity of the word problem in semigroups.
