LIPIcs.RTA.2011.267.pdf
- Filesize: 492 kB
- 16 pages
Document
Soundness of Unravelings for Deterministic Conditional Term Rewriting Systems via Ultra-Properties Related to Linearity
Authors
-
Part of:
Volume:
22nd International Conference on Rewriting Techniques and Applications (RTA'11) (RTA 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Rewriting Techniques and Applications (RTA) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-04-26
Cite AsGet BibTex
Naoki Nishida, Masahiko Sakai, and Toshiki Sakabe. Soundness of Unravelings for Deterministic Conditional Term Rewriting Systems via Ultra-Properties Related to Linearity. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 267-282, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.RTA.2011.267
https://doi.org/10.4230/LIPIcs.RTA.2011.267
Abstract
Unravelings are transformations from a conditional term rewriting
system (CTRS, for short) over an original signature into an
unconditional term rewriting systems (TRS, for short) over an extended
signature. They are not sound for every CTRS w.r.t. reduction, while
they are complete w.r.t. reduction. Here, soundness w.r.t. reduction
means that every reduction sequence of the corresponding unraveled
TRS, of which the initial and end terms are over the original
signature, can be simulated by the reduction of the original CTRS. In
this paper, we show that an optimized variant of Ohlebusch's
unraveling for deterministic CTRSs is sound w.r.t. reduction if the
corresponding unraveled TRSs are left-linear or both right-linear and
non-erasing. We also show that soundness of the variant implies that
of Ohlebusch's unraveling.
Keywords
- conditional term rewriting
- program transformation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads