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

DOI10.1137/0222010zbMath0766.68069OpenAlexW2076609932MaRDI QIDQ4037688

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

term-rewriting systemssequentialitycall-by-need computationsleft- linear system

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (10)

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

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