Decidable Call-by-Need Computations in Term Rewriting
| hal.structure.identifier | Linguistic signs, grammar and meaning: computational logic for natural language [SIGNES] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | DURAND, Irène | |
| dc.contributor.author | MIDDELDORP, Aart | |
| dc.date.accessioned | 2024-04-15T09:53:53Z | |
| dc.date.available | 2024-04-15T09:53:53Z | |
| dc.date.created | 2003 | |
| dc.date.issued | 2005 | |
| dc.identifier.issn | 0890-5401 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198634 | |
| dc.description.abstractEn | The theorem of Huet and Lévy stating that for orthogonal rewrite systems (i) every reducible term contains a needed redex and (ii) repeated contraction of needed redexes results in a normal form if the term under consideration has a normal form, forms the basis of all results on optimal normalizing strategies for orthogonal rewrite systems. However, needed redexes are not computable in general. In the paper we show how the use of approximations and elementary tree automata techniques allows one to obtain decidable conditions in a simple and elegant way. Surprisingly, by avoiding complicated concepts like index and sequentiality we are able to cover much larger classes of rewrite systems. We also study modularity aspects of the classes in our hierarchy. It turns out that none of the classes is preserved under signature extension. By imposing various conditions we recover the preservation under signature extension. By imposing some more conditions we are able to strengthen the signature extension results to modularity for disjoint and constructor-sharing combinations. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | Term Rewriting | |
| dc.subject.en | Strategies | |
| dc.subject.en | Call-by-Need | |
| dc.subject.en | Tree Automata | |
| dc.title.en | Decidable Call-by-Need Computations in Term Rewriting | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Informatique et langage [cs.CL] | |
| bordeaux.journal | Information and Computation | |
| bordeaux.page | 95-126 | |
| bordeaux.volume | 2 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 196 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00338565 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00338565v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Information%20and%20Computation&rft.date=2005&rft.volume=2&rft.issue=196&rft.spage=95-126&rft.epage=95-126&rft.eissn=0890-5401&rft.issn=0890-5401&rft.au=DURAND,%20Ir%C3%A8ne&MIDDELDORP,%20Aart&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||