New Undecidability Results for Properties of Term Rewrite Systems

DOI10.1016/j.entcs.2012.11.012zbMath1291.68222OpenAlexW2140520835WikidataQ113318030 ScholiaQ113318030MaRDI QIDQ5166638

Rakesh M. Verma

Publication date: 27 June 2014

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2012.11.012

zbMATH Keywords

reachabilitydecision problemsconfluenceterm rewrite systemsnormalization properties

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items

Uniqueness of Normal Forms for Shallow Term Rewrite Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
• The reachability and related decision problems for monadic and semi-constructor TRSs
• 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
• Computing in systems described by equations
• Universality of a reversible two-counter machine
• Decidability for left-linear growing term rewriting systems.
• Characterizing confluence by rewrite closure and right ground term rewrite systems
• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• A new decidability technique for ground term rewriting systems with applications
• The Confluence Problem for Flat TRSs
• Computer Science Logic

This page was built for publication: New Undecidability Results for Properties of Term Rewrite Systems