Space functions and space complexity of the word problem in semigroups.
DOI10.1007/s00037-012-0058-0zbMath1322.20054MaRDI 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
algorithms; word problem; time complexity; finitely generated semigroups; finitely presented semigroups; isoperimetric functions; space complexity; Dehn functions; generators and relations in semigroups
68Q25: Analysis of algorithms and problem complexity
20M05: Free semigroups, generators and relations, word problems
03D15: Complexity of computation (including implicit computational complexity)
20F69: Asymptotic properties of groups
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D40: Word problems, etc. in computability and recursion theory
20F06: Cancellation theory of groups; application of van Kampen diagrams
03D10: Turing machines and related notions
