The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
From MaRDI portal
Publication:4013403
DOI10.1007/BF01213858zbMath0780.68080MaRDI QIDQ4013403
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ On weakly confluent monadic string-rewriting systems ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Lambda-confluence for context rewriting systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Using string-rewriting for solving the word problem for finitely presented groups
- Decidable sentences of Church-Rosser congruences
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Special monoids and special Thue systems
- Systems of reductions
- Thue systems as rewriting systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Testing for the Church-Rosser property
- Completing a finite special string-rewriting system on the congruence class of the empty word
- Presentations of groups and monoids
- Confluent and Other Types of Thue Systems
