Pseudo-natural algorithms for the word problem for finitely presented monoids and groups

DOI10.1016/S0747-7171(85)80022-5zbMath0591.20038OpenAlexW2075639491MaRDI QIDQ1074716

Friedrich Otto, Klaus Madlener

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/s0747-7171(85)80022-5

zbMATH Keywords

algorithmword problemfinitely presented groupstring rewriting systemdegree of complexitypseudo-natural algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (25)

The Dehn function of Richard Thompson's group \(F\) is quadratic. ⋮ SECOND ORDER DEHN FUNCTIONS OF GROUPS AND MONOIDS ⋮ LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS ⋮ Polynomially-bounded Dehn functions of groups ⋮ Thue systems as rewriting systems ⋮ Taming the hydra: The word problem and extreme integer compression ⋮ Complexity, combinatorial group theory and the language of palutators ⋮ FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY ⋮ Pseudo-natural algorithms for finitely generated presentations of monoids and groups ⋮ Algorithmically complex residually finite groups ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ Logspace and compressed-word computations in nilpotent groups ⋮ A note on confluent Thue systems ⋮ McNaughton families of languages. ⋮ Volume distortion in groups. ⋮ Algorithmic problems in groups with quadratic Dehn function ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem ⋮ Dehn functions of finitely presented metabelian groups ⋮ Finiteness and Dehn functions of automatic monoids having directed fellow traveller property. ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ DEHN FUNCTION AND LENGTH OF PROOFS ⋮ Space functions of groups ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Decidable sentences of Church-Rosser congruences
• Finite complete rewriting systems and the complexity of word problem
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• 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
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Subgroups of finitely presented groups
• Confluent and Other Types of Thue Systems
• The honest subrecursive classes are a lattice
• Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Computable Algebra, General Theory and Theory of Computable Fields
• Strong Computability and Variants of the Uniform Halting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 the word problem for finitely presented monoids and groups