Deciding confluence of certain term rewriting systems in polynomial time

DOI10.1016/j.apal.2004.04.005zbMath1072.68051OpenAlexW2050626079MaRDI QIDQ1886319

Guillem Godoy, Rakesh M. Verma, Ashish Kumar Tiwari

Publication date: 18 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.04.005

zbMATH Keywords

Term rewritingConfluenceGround rewrite systemsShallow linear rewrite systems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

Uniqueness of Normal Forms for Shallow Term Rewrite Systems ⋮ A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems ⋮ Normalization properties for shallow TRS and innermost rewriting ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orderings for term-rewriting systems
• A fast algorithm for generating reduced ground rewriting systems from a set of ground equations
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Reachability and confluence are undecidable for flat term rewriting systems
• The Church-Rosser property for ground term-rewriting systems is decidable
• Abstract congruence closure
• Algorithms and reductions for rewriting problems. II.
• Proving termination with multiset orderings
• Fast Decision Procedures Based on Congruence Closure
• Variations on the Common Subexpression Problem
• Bi-rewriting, a term rewriting technique for monotonic order relations
• Classes of term rewrite systems with polynomial confluence problems

This page was built for publication: Deciding confluence of certain term rewriting systems in polynomial time