Deciding confluence of certain term rewriting systems in polynomial time

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

Rakesh M. Verma, Guillem Godoy, 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 rewriting; Confluence; Ground rewrite systems; Shallow linear rewrite systems

Mathematics Subject Classification ID

68Q42: Grammars and rewriting systems

Related Items

A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems, Normalization properties for shallow TRS and innermost rewriting

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