On weakly confluent monadic string-rewriting systems
From MaRDI portal
Publication:685433
DOI10.1016/0304-3975(93)90213-DzbMath0778.68049MaRDI QIDQ685433
Louxin Zhang, Friedrich Otto, Klaus Madlener, Paliath Narendran
Publication date: 9 January 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Symbolic computation and algebraic computation (68W30) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items
Computing presentations for subgroups of polycyclic groups and of context-free groups, Codes modulo finite monadic string-rewriting systems, A polynomial algorithm testing partial confluence of basic semi-Thue systems, McNaughton families of languages., Deciding the NTS property of context-free grammars, The pre-NTS property is undecidable for context-free grammars, A polynomial algorithm testing partial confluence of basic semi-Thue systems
Cites Work
- 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
- Groups, the theory of ends, and context-free languages
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Some undecidability results for non-monadic Church-Rosser Thue systems
- The accessibility of finitely presented groups
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- On deciding whether a monoid is a free monoid or is a group
- Complete semi-Thue systems for abelian groups
- Thue systems as rewriting systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Elements of finite order for finite weight-reducing and confluent Thue systems
- When is an extension of a specification consistent? Decidable and undecidable cases
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Presentations of groups and monoids
- Infinite regular Thue systems
- On theories with a combinatorial definition of 'equivalence'
- The Knuth-Bendix Completion Procedure and Thue Systems
- Proving termination with multiset orderings
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
