Pseudo-natural algorithms for finitely generated presentations of monoids and groups

DOI10.1016/S0747-7171(88)80034-8zbMath0665.20019MaRDI QIDQ1115973

Friedrich Otto, Klaus Madlener

Publication date: 1988

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

presentation; finitely generated groups; monoids; formal language; derivational complexity; word problems; relators; small cancellation; context- free languages; Grzegorczyk hierarchy; pseudonatural algorithms

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20F05: Generators, relations, and presentations of groups

20M05: Free semigroups, generators and relations, word problems

20M35: Semigroups in automata theory, linguistics, etc.

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P, About the descriptive power of certain classes of finite string-rewriting systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite complete rewriting systems and the complexity of word problem
• A note on a special one-rule semi-Thue system
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Word problems and a homological finiteness condition for monoids
• Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Infinite regular Thue systems
• Classes of recursive functions based on Ackermann's function
• On theories with a combinatorial definition of 'equivalence'
• Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität