Decidable approximations of term rewriting systems

DOI10.1007/3-540-61464-8_65zbMath1503.68117OpenAlexW1551719154MaRDI QIDQ5055873

Florent Jacquemard

Publication date: 9 December 2022

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

Full work available at URL: https://doi.org/10.1007/3-540-61464-8_65

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items

Root-neededness and approximations of neededness, Reducing non-occurrence of specified runtime errors to all-path reachability problems of constrained rewriting, Unnamed Item, Some decidability results on one-pass reductions, Levels of undecidability in rewriting, Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems, On Proving Soundness of the Computationally Equivalent Transformation for Normal Conditional Term Rewriting Systems by Using Unravelings, Tree automata for rewrite strategies, A theoretical limit for safety verification techniques with regular fix-point computations, Closure of Tree Automata Languages under Innermost Rewriting, Decidable call-by-need computations in term rewriting, Murg term rewrite systems, Termination criteria for tree automata completion, Bottom-up rewriting for words and terms, Handling Left-Quadratic Rules When Completing Tree Automata, Strong and NV-sequentiality of constructor systems, Decidable call by need computations in term rewriting (extended abstract), Soft typing for ordered resolution, Derivation trees of ground term rewriting systems., The combinator S

Cites Work

• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Reductions in tree replacement systems
• Sequentiality in orthogonal term rewriting systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems
• Recursive Unsolvability of a problem of Thue
• Simulation of Turing machines by a left-linear rewrite rule
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item