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

DOI10.1007/978-3-540-70590-1_13MaRDI QIDQ3522018zbMATH OpenOpenAlexFDO

Authors Yoshiharu Kojima, Masahiko Sakai

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)

Recommendations

• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems
• Decidability of innermost termination and context-sensitive termination for semi-constructor term rewriting systems
• scientific article; zbMATH DE number 4043235
• Publication:4938609
• Decidability of reachability for disjoint union of term rewriting systems

Cites work

• scientific article; zbMATH DE number 1615242 (Why is no real title available?)
• scientific article; zbMATH DE number 1332639 (Why is no real title available?)
• scientific article; zbMATH DE number 1380887 (Why is no real title available?)
• scientific article; zbMATH DE number 794243 (Why is no real title available?)
• scientific article; zbMATH DE number 1405630 (Why is no real title available?)
• Bottom-Up Rewriting Is Inverse Recognizability Preserving
• Decidable approximations of term rewriting systems
• Encompassment properties and automata with constraints
• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems
• Reachability and confluence are undecidable for flat term rewriting systems
• The Confluence Problem for Flat TRSs

Cited in

(8)

• Automatically Proving and Disproving Feasibility Conditions
• Term rewriting with prefix context constraints and bottom-up strategies
• Controlled term rewriting
• Reachability analysis of innermost rewriting
• Reachability analysis of innermost rewriting
• Closure of tree automata languages under innermost rewriting
• Innermost-Reachability and Innermost-Joinability Are Decidable for Shallow Term Rewrite Systems
• Decidability of innermost termination and context-sensitive termination for semi-constructor term rewriting systems

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

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