Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems

DOI10.1007/978-3-540-70590-1_13zbMath1145.68449OpenAlexW1819637175MaRDI QIDQ3522018

Masahiko Sakai, Yoshiharu Kojima

Publication date: 28 August 2008

Published in: Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70590-1_13

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

Automatically Proving and Disproving Feasibility Conditions ⋮ Controlled Term Rewriting ⋮ Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies ⋮ Closure of Tree Automata Languages under Innermost Rewriting

Cites Work

• Reachability and confluence are undecidable for flat term rewriting systems
• Encompassment properties and automata with constraints
• Decidable approximations of term rewriting systems
• The Confluence Problem for Flat TRSs
• Bottom-Up Rewriting Is Inverse Recognizability Preserving
• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems