On weakly confluent monadic string-rewriting systems
This paper studies particular string rewriting systems. It is investigated as to how far the various decidability results for finite, monadic, and confluent string-rewriting systems can be carried over to the class of finite monadic string-rewriting systems that are only weakly confluent. Here a monadic string-rewriting system \(R\) on some alphabet \(\Sigma\) is called weakly confluent if it is confluent on all the congruence classes \([a]_ R\), with \(a\in \Sigma\cup \{e\}\). After establishing that the property of weak confluence is tractable for finite monadic string-rewriting systems, we prove that many decision problems that are tractable for finite, monadic, and confluent systems are, in fact, undecidable for finite monadic systems that are only weakly confluent. An example is the word problem. On the other hand, for finite, monadic, and weakly confluent systems that present groups, the validation problem for linear sentences is decidable. Many decision problems, among them the word problem and the generalized word problem, can be expressed through linear sentences and, hence, they all are decidable in this setting. The paper closes with a specialized completion procedure for finite, monadic string-rewriting systems presenting groups. Given a system of this form, the completion procedure tries to construct an equivalent system of the same form that, in addition, is weakly confluent. The correctness and completeness of this procedure are shown, and some detailed examples are presented. This procedure, together with the decidability results mentioned before, presents an elegant and uniform way to perform computations in context-free groups effectively.
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- Complete semi-Thue systems for abelian groups
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Confluent and Other Types of Thue Systems
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Decidable sentences of Church-Rosser congruences
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Elements of finite order for finite weight-reducing and confluent Thue systems
- Groups and NTS languages
- Groups, the theory of ends, and context-free languages
- scientific article; zbMATH DE number 3888893 (Why is no real title available?)
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- scientific article; zbMATH DE number 4155899 (Why is no real title available?)
- scientific article; zbMATH DE number 43246 (Why is no real title available?)
- scientific article; zbMATH DE number 42096 (Why is no real title available?)
- scientific article; zbMATH DE number 50648 (Why is no real title available?)
- scientific article; zbMATH DE number 3528212 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- Infinite regular Thue systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- On deciding whether a monoid is a free monoid or is a group
- On theories with a combinatorial definition of 'equivalence'
- Presentations of groups and monoids
- Proving termination with multiset orderings
- Some undecidability results for non-monadic Church-Rosser Thue systems
- The accessibility of finitely presented groups
- The Knuth-Bendix Completion Procedure and Thue Systems
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Thue systems as rewriting systems
- When is an extension of a specification consistent? Decidable and undecidable cases
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- The pre-NTS property is undecidable for context-free grammars
- Computing presentations for subgroups of polycyclic groups and of context-free groups
- Codes modulo finite monadic string-rewriting systems
- McNaughton families of languages.
- Some results on Green's relations for monoids presented by monadic string-rewriting systems
- INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS
- scientific article; zbMATH DE number 4036065 (Why is no real title available?)
- scientific article; zbMATH DE number 42096 (Why is no real title available?)
- scientific article; zbMATH DE number 176741 (Why is no real title available?)
- scientific article; zbMATH DE number 177883 (Why is no real title available?)
- scientific article; zbMATH DE number 2068882 (Why is no real title available?)
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Deciding the NTS property of context-free grammars
- About the descriptive power of certain classes of finite string-rewriting systems
This page was built for publication: On weakly confluent monadic string-rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685433)
