About the descriptive power of certain classes of finite string-rewriting systems

DOI10.1016/0304-3975(89)90002-9zbMath0697.20017OpenAlexW2074251444MaRDI QIDQ910850

Klaus Madlener, Friedrich Otto

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90002-9

zbMATH Keywords

computational complexityword problemdecidabilitycontext-free languagerewriting systemsformal languagefinitely presented monoidssyntactic monoidfinitely generated groupsubgroup of finite indexrewriting rulesconfluent string-rewriting systemGregorczyk hierarchyGroup presentations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Automata and formal grammars in connection with logical questions (03D05) Abstract data types; algebraic specification (68Q65) Semigroups in automata theory, linguistics, etc. (20M35) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06)

Related Items (18)

Computing presentations for subgroups of polycyclic groups and of context-free groups ⋮ SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID ⋮ A finiteness condition for rewriting systems ⋮ Monoid presentations of groups by finite special string-rewriting systems ⋮ On the descriptive power of special Thue systems ⋮ On the rational subsets of the free group ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Completing a finite special string-rewriting system on the congruence class of the empty word ⋮ Theorem proving with group presentations: Examples and questions ⋮ Space Complexity and Word Problems of Groups ⋮ Schematization of infinite sets of rewrite rules generated by divergent completion processes ⋮ Confluence of some presentations associated with graphs ⋮ Semigroups presented by one relation and satisfying the Church-Rosser property ⋮ Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings ⋮ Rewriting systems, plain groups, and geodetic graphs ⋮ ON GROUPS PRESENTED BY MONADIC REWRITING SYSTEMS WITH GENERATORS OF FINITE ORDER ⋮ Growth functions for some one-relator monoids ⋮ GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups and NTS languages
• Decidable sentences of Church-Rosser congruences
• Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group
• Finite complete rewriting systems and the complexity of word problem
• Groups, the theory of ends, and context-free languages
• The accessibility of finitely presented groups
• A note on a special one-rule semi-Thue system
• Complexity results on the conjugacy problem for monoids
• 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
• On deciding whether a monoid is a free monoid or is a group
• NTS languages are deterministic and congruential
• n-level rewriting systems
• Complete semi-Thue systems for abelian groups
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Systems of reductions
• Thue systems as rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Word problems and a homological finiteness condition for monoids
• Pseudo-natural algorithms for finitely generated presentations of monoids and groups
• Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
• Elements of finite order for finite weight-reducing and confluent Thue systems
• A connection between the integral homology and the centre of a rational linear group
• On a special monoid with a single defining relation
• Monadic Thue systems
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• Presentations of groups and monoids
• Infinite regular Thue systems
• Groups and Simple Languages
• The Knuth-Bendix Completion Procedure and Thue Systems
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Commutativity in groups presented by finite Church-Rosser Thue systems
• Confluent and Other Types of Thue Systems
• The equivalence problem for deterministic finite-turn pushdown automata
• A Finitely Presented Group Whose 3-Dimensional Integral Homology is not Finitely Generated
• Finiteness properties of groups

This page was built for publication: About the descriptive power of certain classes of finite string-rewriting systems