Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
From MaRDI portal
Publication:1107523
DOI10.1016/0020-0190(88)90049-XzbMath0653.03026MaRDI QIDQ1107523
Friedrich Otto, Paliath Narendran
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (11)
A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ On confluence of one-rule trace-rewriting systems ⋮ On confluence versus strong confluence for one-rule trace-rewriting systems ⋮ One-rule trace-rewriting systems and confluence ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Word problems over traces which are solvable in linear time ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ On deciding confluence of finite string-rewriting systems modulo partial commutativity ⋮ Word problems over traces which are solvable in linear time ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Confluence problems for trace rewriting systems
Cites Work
- Unnamed Item
- Unnamed Item
- The undecidability of the preperfectness of Thue systems
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Rewriting systems and word problems in a free partially commutative monoid
- Testing for the Church-Rosser property
- Completion of a Set of Rules Modulo a Set of Equations
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
This page was built for publication: Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
