Mostrar el registro sencillo del ítem
dc.contributor.author
Bonelli, Eduardo Augusto
dc.contributor.author
Kesner, Delia
dc.contributor.author
Lombardi, Carlos
dc.contributor.author
Rios, Alejandro Norberto
dc.date.available
2019-03-30T00:09:45Z
dc.date.issued
2017-04
dc.identifier.citation
Bonelli, Eduardo Augusto; Kesner, Delia; Lombardi, Carlos; Rios, Alejandro Norberto; On abstract normalisation beyond neededness; Elsevier Science; Theoretical Computer Science; 672; 4-2017; 36-63
dc.identifier.issn
0304-3975
dc.identifier.uri
http://hdl.handle.net/11336/72890
dc.description.abstract
We study normalisation of multistep strategies, strategies that reduce a set of redexes at a time, focusing on the notion of necessary sets, those which contain at least one redex that cannot be avoided in order to reach a normal form. This is particularly appealing in the setting of non-sequential rewrite systems, in which terms that are not in normal form may not have any needed redex. We first prove a normalisation theorem for abstract rewrite systems (ARS), a general rewriting framework encompassing many rewriting systems developed by P-A. Melliès [20]. The theorem states that multistep strategies reducing so called necessary and never-gripping sets of redexes at a time are normalising in any ARS. Gripping refers to an abstract property reflecting the behaviour of higher-order substitution. We then apply this result to the particular case of PPC, a calculus of patterns and to the lambda-calculus with parallel-or.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
NEEDEDNESS
dc.subject
NORMALISATION
dc.subject
PATTERN CALCULI
dc.subject
REWRITING
dc.subject
SEQUENTIALITY
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
On abstract normalisation beyond neededness
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-03-29T12:11:08Z
dc.journal.volume
672
dc.journal.pagination
36-63
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bonelli, Eduardo Augusto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina
dc.description.fil
Fil: Kesner, Delia. Université Paris Diderot - Paris 7; Francia. Centre National de la Recherche Scientifique; Francia. Institut de Recherche en Informatique Fondamentale; Francia
dc.description.fil
Fil: Lombardi, Carlos. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina
dc.description.fil
Fil: Ríos, Alejandro. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
dc.journal.title
Theoretical Computer Science
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0304397517301019
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.tcs.2017.01.025
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1412.2118
Archivos asociados