Reachability and confluence are undecidable for flat term rewriting systems

DOI10.1016/S0020-0190(03)00310-7zbMath1161.68502MaRDI QIDQ1014436

Florent Jacquemard

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

term rewritingtheory of computation

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (8)

Deciding confluence of certain term rewriting systems in polynomial time ⋮ The reachability and related decision problems for monadic and semi-constructor TRSs ⋮ Some decidability results on one-pass reductions ⋮ Levels of undecidability in rewriting ⋮ Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems ⋮ Undecidable properties of flat term rewrite systems ⋮ Unique Normalization for Shallow TRS ⋮ Undecidable Properties on Length-Two String Rewriting Systems

Cites Work

• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• The Church-Rosser property for ground term-rewriting systems is decidable
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reachability and confluence are undecidable for flat term rewriting systems