New Undecidability Results for Properties of Term Rewrite Systems

DOI10.1016/J.ENTCS.2012.11.012MaRDI QIDQ5166638zbMATH OpenOpenAlexWikidataFDO

Authors 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

confluencedecision problemsnormalization propertiesreachabilityterm rewrite systems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1086665
• The undecidability of self-embedding for term rewriting systems
• Undecidable properties on length-two string rewriting systems
• A new decidability technique for ground term rewriting systems with applications
• Relative undecidability in term rewriting. I: The termination hierarchy
• Degrees of Undecidability in Term Rewriting
• Decidability of reachability for disjoint union of term rewriting systems
• On sufficient-completeness and related properties of term rewriting systems
• Relative undecidability in term rewriting. II: The confluence hierarchy

Cites work

• A new decidability technique for ground term rewriting systems with applications
• A polynomial algorithm for uniqueness of normal forms of linear shallow term rewrite systems
• Algorithms and reductions for rewriting problems
• Characterizing confluence by rewrite closure and right ground term rewrite systems
• Computer Science Logic
• Computing in systems described by equations
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Decidability for left-linear growing term rewriting systems.
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• On the Normalization and Unique Normalization Properties of Term Rewrite Systems
• Rewriting
• The Church-Rosser property for ground term-rewriting systems is decidable
• The Confluence Problem for Flat TRSs
• The reachability and related decision problems for monadic and semi-constructor TRSs
• Universality of a reversible two-counter machine

Cited in

(12)

• Reachability and confluence are undecidable for flat term rewriting systems
• Relative undecidability in term rewriting. I: The termination hierarchy
• Homomorphism theorem and unreachability for \(\omega\) rewriting systems
• Undecidable properties on length-two string rewriting systems
• The \Pi^0_2 -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• scientific article; zbMATH DE number 17534 (Why is no real title available?)
• Uniqueness of normal forms for shallow term rewrite systems
• Processes, Terms and Cycles: Steps on the Road to Infinity
• Some undecidable termination problems for semi-Thue systems
• Tail reduction free term rewriting systems revisited
• Ground approximations of term rewriting systems
• Undecidable properties of flat term rewrite systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5166638)