2026-06-01T01:13:20Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/531972023-08-10T17:36:45Zcom_20.500.14352_14col_20.500.14352_21
A Fully Abstract Semantics for Constructor Systems
López-Fraguas, F.J.
Rodríguez-Hortalá, Juan
Sánchez-Hernández, Jaime
Treinen, Ralf
004.43
Lenguajes de programación
1203.23 Lenguajes de Programación
20th international conference on Rewriting Techniques and Applications, RTA 2009, Brasilia, Brazil, June 29–July 1, 2009
Constructor-based term rewriting systems are a useful subclass of TRS, in particular for programming purposes. In this kind of systems constructors determine a universe of values, which are the expected output of the computations. Then it would be natural to think of a semantics associating each expression to the set of its reachable values. Somehow surprisingly, the resulting semantics has poor properties, for it is not compositional nor fully abstract when non-confluent systems are considered. In this paper we propose a novel semantics for expressions in constructor systems, which is compositional and fully abstract (with respect to sensible observation functions, in particular the set of reachable values for an expression), and therefore can serve as appropriate basis for semantic based analysis or manipulation of such kind of rewrite systems.
Sección Deptal. de Sistemas Informáticos y Computación
Fac. de Ciencias Matemáticas
TRUE
pub
2023-06-20T13:38:55Z
2023-06-20T13:38:55Z
2009
book part
https://hdl.handle.net/20.500.14352/53197
XXXX-XXXX
10.1007/978-3-642-02348-4 23
eng
Lecture Notes in Computer Science
Spanish projects Merit-Forms-UCM (TIN2005-09207-C03-03),
Promesas-CAM (S-0505/TIC/0407)
STAMP (TIN2008-06622-C03-01/TIN).
restricted access
application/pdf
Springer