NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems

DOI10.1137/0222010MaRDI QIDQ4037688zbMATH OpenOpenAlexFDO

Authors Michio Oyamaguchi

Publication date 16 May 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222010

zbMATH Keywords

call-by-need computationsleft- linear systemsequentialityterm-rewriting systems

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Decidable call-by-need computations in term rewriting
• Sequentiality in orthogonal term rewriting systems
• A refinement of strong sequentiality for term rewriting with constructors
• Sequentiality, monadic second-order logic and tree automata.
• Decidable call by need computations in term rewriting (extended abstract)

Cited in

(13)

• Strong and NV-sequentiality of constructor systems
• A refinement of strong sequentiality for term rewriting with constructors
• Decidability for left-linear growing term rewriting systems.
• Decidable call-by-need computations in term rewriting
• Sequentiality, monadic second-order logic and tree automata.
• Context-sensitive rewriting strategies
• Call-by-need reduction for membership conditional term rewriting systems
• Root-neededness and approximations of neededness
• Optimal normalization in orthogonal term rewriting systems
• Decidable approximations of term rewriting systems
• Decidable call by need computations in term rewriting (extended abstract)
• A sequential reduction strategy
• Ground approximations of term rewriting systems

This page was built for publication: NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems

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