About the descriptive power of certain classes of finite string-rewriting systems
type: Item
instance of: scholarly article
title: About the descriptive power of certain classes of finite string-rewriting systems
zbMATH Open document ID: 0697.20017
DOI: 10.1016/0304-3975(89)90002-9
author: Klaus Madlener
author: Friedrich Otto
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: This paper is a survey of results concerning classification of monoids and groups presented by certain types of rewriting systems. It contains a large sampling of results, including proofs for some of the simpler ones, and contains an extensive bibliography of 61 entries. It also contains a number of examples which illuminate the results, or in some cases, the limitations of the results. A finite set \(\Sigma\), the alphabet, and a finite set \(R\subset \Sigma^*\times \Sigma^*\), the rewriting rules, form a presentation for a monoid \(M_ R\), often called the syntactic monoid, namely, the quotient of the free monoid \(\Sigma^*\) by the congruence generated by R. Group presentations by rewriting systems are defined analogously, but with the usual convention of providing a second copy of \(\Sigma\) to denote the inverses of the elements of \(\Sigma\) and by providing outside of the set R the relations making corresponding elements in the two copies of \(\Sigma\) inverses of each other. The difference between a presentation by a rewriting system and a presentation in the usual sense is that reductions using the rewriting system can be considered to have a sense of direction - derivations in the sense of formal language theory. Topics considered in the paper range from questions of decidability to classifications of monoid- or group-theoretic properties in terms of language-theoretic properties to questions of computational complexity. Numerous technical, but reasonable, conditions are attached to the rewriting systems, but these cannot be reproduced in the space of this review. A sampling of results may give a flavor of the paper. If a monoid \(M_ R\) has a presentation such that the class of 1 is a regular, or context-free language, then every presentation has this property. Hence, the monoid can be called regular or context-free. A group is regular if and only if it is finite. A finitely generated group is context-free if and only if it contains a subgroup of finite …
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 20E06
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 03D05
zbMATH DE Number: 4142300
zbMATH Keywords: rewriting systems
zbMATH Keywords: rewriting rules
zbMATH Keywords: syntactic monoid
zbMATH Keywords: Group presentations
zbMATH Keywords: formal language
zbMATH Keywords: decidability
zbMATH Keywords: computational complexity
zbMATH Keywords: context-free language
zbMATH Keywords: finitely generated group
zbMATH Keywords: subgroup of finite index
zbMATH Keywords: confluent string-rewriting system
zbMATH Keywords: Gregorczyk hierarchy
zbMATH Keywords: word problem
zbMATH Keywords: finitely presented monoids
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90002-9
OpenAlex ID: W2074251444
cites work: Q4085266
cites work: Q3339311
cites work: Groups and NTS languages
cites work: Q3329652
cites work: Q3748486
cites work: Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
cites work: n-level rewriting systems
cites work: Finite complete rewriting systems and the complexity of word problem
cites work: An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
cites work: Systems of reductions
cites work: Q4129638
cites work: A connection between the integral homology and the centre of a rational linear group
cites work: NTS languages are deterministic and congruential
cites work: Confluent and Other Types of Thue Systems
cites work: Decidable sentences of Church-Rosser congruences
cites work: Thue systems as rewriting systems
cites work: Monadic Thue systems
cites work: Finiteness properties of groups
cites work: Q4195154
cites work: Complete semi-Thue systems for abelian groups
cites work: Q3775715
cites work: The accessibility of finitely presented groups
cites work: Presentations of groups and monoids
cites work: Q3341886
cites work: Q5824357
cites work: Groups and Simple Languages
cites work: On a special monoid with a single defining relation
cites work: A note on a special one-rule semi-Thue system
cites work: Q3994922
cites work: A finite Thue system with decidable word problem and without equivalent finite canonical system
cites work: The Knuth-Bendix Completion Procedure and Thue Systems
cites work: Q3756512
cites work: Q5581665
cites work: Q3992832
cites work: Q4145882
cites work: Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
cites work: Q3775714
cites work: Pseudo-natural algorithms for finitely generated presentations of monoids and groups
cites work: Commutativity in groups presented by finite Church-Rosser Thue systems
cites work: Q3825236
cites work: Q4135772
cites work: Q3779786
cites work: Groups, the theory of ends, and context-free languages
cites work: Complexity results on the conjugacy problem for monoids
cites work: The problems of cyclic equality and conjugacy for finite complete rewriting systems

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Elements of finite order for finite weight-reducing and confluent Thue systems

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Infinite regular Thue systems

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: On deciding whether a monoid is a free monoid or is a group

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: On deciding the confluence of a finite string-rewriting system on a given congruence class

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Word problems and a homological finiteness condition for monoids

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: A Finitely Presented Group Whose 3-Dimensional Integral Homology is not Finitely Generated

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: The equivalence problem for deterministic finite-turn pushdown automata

About the descriptive power of certain classes of finite string-rewriting systems (cites work)
cites work: Q4044553