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)
presentationfinitely generated groupsmonoidsformal languagederivational complexityword problemsrelatorssmall cancellationcontext- free languagesGrzegorczyk hierarchypseudonatural algorithms
Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items (2)
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Pseudo-natural algorithms for finitely generated presentations of monoids and groups
