Document Open Access Logo

Notes on Structure-Preserving Transformations of Conditional Term Rewrite Systems

Authors Karl Gmeiner, Naoki Nishida

PDF
Thumbnail PDF

File

OASIcs.WPTE.2014.3.pdf
  • Filesize: 433 kB
  • 12 pages

Document Identifiers

Author Details

Karl Gmeiner
Naoki Nishida

Cite As Get BibTex

Karl Gmeiner and Naoki Nishida. Notes on Structure-Preserving Transformations of Conditional Term Rewrite Systems. In First International Workshop on Rewriting Techniques for Program Transformations and Evaluation. Open Access Series in Informatics (OASIcs), Volume 40, pp. 3-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/OASIcs.WPTE.2014.3

Abstract

Transforming conditional term rewrite systems (CTRSs) into unconditional systems (TRSs) is a common approach to analyze properties of CTRSs via the simpler framework of unconditional rewriting. In the past many different transformations have been introduced for this purpose. One class of transformations, so-called unravelings, have been analyzed extensively in the past. 

In this paper we provide an overview on another class of transformations that we call structure-preserving transformations. In these transformations the structure of the conditional rule, in particular their left-hand side is preserved in contrast to unravelings. We provide an overview of transformations of this type and define a new transformation that improves previous approaches.

Subject Classification

Keywords
  • conditional term rewriting
  • unraveling
  • condition elimination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sergio Antoy, Bernd Brassel, and Michael Hanus. Conditional narrowing without conditions. In Proc. 5th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, 27-29 August 2003, Uppsala, Sweden, pages 20-31. ACM Press, 2003. Google Scholar
  2. Jan A. Bergstra and Jan Willem Klop. Conditional rewrite rules: Confluence and termination. Journal of Computer and System Sciences, 32(3):323-362, 1986. Google Scholar
  3. Elio Giovanetti and Corrado Moiso. Notes on the elimination of conditions. In Stéphane Kaplan and Jean-Pierre Jouannaud, editors, Proc. 1st Int. Workshop on Conditional Rewriting Systems (CTRS'87), Orsay, France, 1987, volume 308 of Lecture Notes in Computer Science, pages 91-97, Orsay, France, 1988. Springer. ISBN 3-540-19242-5. Google Scholar
  4. Karl Gmeiner and Bernhard Gramlich. Transformations of conditional rewrite systems revisited. In Andrea Corradini and Ugo Montanari, editors, Recent Trends in Algebraic Development Techniques (WADT 2008) - Selected Papers, volume 5486 of Lecture Notes in Computer Science, pages 166-186. Springer, 2009. Google Scholar
  5. Karl Gmeiner, Bernhard Gramlich, and Felix Schernhammer. On (un)soundness of unravelings. In Christopher Lynch, editor, Proc. 21st International Conference on Rewriting Techniques and Applications (RTA 2010), July 11-13, 2010, Edinburgh, Scotland, UK, LIPIcs (Leibniz International Proceedings in Informatics), July 2010. Google Scholar
  6. Karl Gmeiner, Bernhard Gramlich, and Felix Schernhammer. On soundness conditions for unraveling deterministic conditional rewrite systems. In Ashish Tiwari, editor, Proc. 23rd International Conference on Rewriting Techniques and Applications (RTA 2012), May 30 to June 2, 2012, Nagoya, Japan, LIPIcs (Leibniz International Proceedings in Informatics), May/June 2012. Google Scholar
  7. Karl Gmeiner, Naoki Nishida, and Bernhard Gramlich. Proving confluence of conditional term rewriting systems via unravelings. In Nao Hirokawa and Vincent van Oostrom, editors, Proceedings of the 2nd International Workshop on Confluence, pages 35-39, 2013. Google Scholar
  8. Claus Hintermeier. How to transform canonical decreasing ctrss into equivalent canonical trss. In Conditional and Typed Rewriting Systems, 4th International Workshop, CTRS-94, Jerusalem, Israel, July 13-15, 1994, Proceedings, volume 968 of Lecture Notes in Computer Science, pages 186-205, 1995. Google Scholar
  9. Massimo Marchiori. Unravelings and ultra-properties. In Michael Hanus and Mario Mario Rodríguez-Artalejo, editors, Proc. 5th Int. Conf. on Algebraic and Logic Programming, Aachen, volume 1139 of Lecture Notes in Computer Science, pages 107-121. Springer, September 1996. Google Scholar
  10. Massimo Marchiori. On deterministic conditional rewriting. Technical Report MIT LCS CSG Memo n.405, MIT, Cambridge, MA, USA, October 1997. Google Scholar
  11. Naoki Nishida, Masahiko Sakai, and Toshiki Sakabe. Partial inversion of constructor term rewriting systems. In Jürgen Giesl, editor, Proc. 16th International Conference on Rewriting Techniques and Applications (RTA'05), Nara, Japan, April 19-21, 2005, volume 3467 of Lecture Notes in Computer Science, pages 264-278. Springer, April 2005. Google Scholar
  12. Naoki Nishida, Masahiko Sakai, and Toshiki Sakabe. Soundness of unravelings for deterministic conditional term rewriting systems via ultra-properties related to linearity. In Manfred Schmidt-Schauss, editor, Proc. 22nd International Conference on Rewriting Techniques and Applications (RTA 2011), May 30 to June 1, 2011, Novi Sad, Serbia, LIPIcs (Leibniz International Proceedings in Informatics), 2011. pages 267-282. Google Scholar
  13. Enno Ohlebusch. Advanced Topics in Term Rewriting. Springer, 2002. Google Scholar
  14. Grigore Rosu. From conditional to unconditional rewriting. In José Luiz Fiadeiro, Peter D. Mosses, and Fernando Orejas, editors, WADT, volume 3423 of Lecture Notes in Computer Science, pages 218-233. Springer, 2004. Google Scholar
  15. Traian-Florin Şerbănuţă and Grigore Roşu. Computationally equivalent elimination of conditions. In Frank Pfenning, editor, Proc. 17th International Conference on Rewriting Techniques and Applications, Seattle, WA, USA, August 12-14, 2006, volume 4098 of Lecture Notes in Computer Science, pages 19-34. Springer, 2006. Google Scholar
  16. Patrick Viry. Elimination of conditions. J. Symb. Comput., 28(3):381-401, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact