Pseudo-natural algorithms for finitely generated presentations of monoids and groups
type: Item
instance of: scholarly article
title: Pseudo-natural algorithms for finitely generated presentations of monoids and groups
zbMATH Open document ID: 0665.20019
DOI: 10.1016/S0747-7171(88)80034-8
author: Klaus Madlener
author: Friedrich Otto
published in: Journal of Symbolic Computation
publication date: 1988-01-01T00:00:00Z
review text: Many problems in algebra (e.g. word problems) and formal language theory (e.g. derivability-membership in r.e. languages) ask whether a certain word can be produced by insertions and/or deletions of words from a given set (relators or productions). Usually there is a ``natural strategy'' to solve the problem, i.e. an exhaustive search through all possible derivations. In some cases the problems are naturally structured to allow efficient search procedures (e.g. small cancellation theory in Combinatorial Group Theory, the CKY algorithm for membership in context- free languages). Based on these observations, the authors consider pseudonatural algorithms for word problems of finitely generated groups and monoids in the Grzegorczyk hierarchy \(\{E_ n:\) \(n\geq 1\}\). The best pseudonatural algorithms can yield complexities arbitrarily far from the inherent complexity of the problem itself in the hierarchy. Thus the authors restrict the usual notion of derivation to strong derivation where only insertions of trivial relators are allowed. They prove that the resulting notion of strong derivational complexity of a word (the length of the shortest strong derivation) realizes optimal algorithms in a Grzegorczyk class. Theorem 3.5. Let \(n\geq 1\). For each finitely generated group G with an \(E_ n\)-decidable word problem, there exists a finitely generated presentation \(<\Sigma;L>\) satisfying the following two conditions: (i) the set L of defining relators is \(E_ 1\) decidable (hence context-sensitive); (ii) The strong derivational complexity of \(<\Sigma;L>\) is bounded above by a function in the class \(E_ n\). Examples are shown to exist of such presentations (with tight bound n) where the derivational complexity has a tight derivational complexity in \(E_ m\) with predetermined gap m (even from a context-free presentation). A similar statement for context-free relators is false since only finitely presented groups have context-free sets of defining relators. Similar …
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4087915
zbMATH Keywords: word problems
zbMATH Keywords: formal language
zbMATH Keywords: relators
zbMATH Keywords: small cancellation
zbMATH Keywords: context- free languages
zbMATH Keywords: pseudonatural algorithms
zbMATH Keywords: finitely generated groups
zbMATH Keywords: Grzegorczyk hierarchy
zbMATH Keywords: derivational complexity
zbMATH Keywords: presentation
zbMATH Keywords: monoids
MaRDI profile type: Publication
cites work: Q4085266
cites work: Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
cites work: Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität
cites work: Finite complete rewriting systems and the complexity of word problem
cites work: Q5824357
cites work: A note on a special one-rule semi-Thue system
cites work: Q3862379
cites work: A finite Thue system with decidable word problem and without equivalent finite canonical system
cites work: Q5581665
cites work: Q4145882
cites work: Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
cites work: Das Identitätsproblem für Gruppen mit einer definierenden Relation
cites work: Q4135772
cites work: On theories with a combinatorial definition of 'equivalence'
cites work: Q4105657
cites work: Infinite regular Thue systems
cites work: Classes of recursive functions based on Ackermann's function
cites work: Word problems and a homological finiteness condition for monoids
cites work: Q4044553
description: scientific article; zbMATH DE number 4087915