Strong and NV-sequentiality of constructor systems
Author
Salvador Lucas
Abstract
Constructor Systems (CSs) are an important subclass of Term Rewriting Systems
(TRSs) which can be used as an abstract model of some programming languages.
While normalizing strategies are always desirable for
achieving a good computational behavior of programs, when dealing with
lazy languages infinitary normalizing strategies should be considered
instead since (finite approximations of) infinite data structures can
be returned as the result of computations. We have shown that
NV-sequential TRSs (hence strongly sequential TRSs, a subclass
of them) provide an appropriate basis for the effective definition of
normalizing and infinitary normalizing strategies. In this paper, we show that
strongly sequential and NV-sequential CSs coincide. Since the
implementation of NV-sequential TRSs has been
underexplored in comparison to strongly sequential TRSs,
this coincidence suggests that,
in programming languages, it is a good option to implement
NV-sequentiality as strong sequentiality.
Keywords
programming languages, sequentiality,
strategies, term rewriting.