License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2011.107
URN: urn:nbn:de:0030-drops-31119
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3111/
Go to the corresponding LIPIcs Volume Portal

Aoto, Takahito ; Yamada, Toshiyuki ; Chiba, Yuki

Natural Inductive Theorems for Higher-Order Rewriting

pdf-format:
3.pdf (0.5 MB)

Abstract

The notion of inductive theorems is well-established in first-order term rewriting. In higher-order term rewriting, in contrast, it is not straightforward to extend this notion because of extensionality (Meinke, 1992). When extending the term rewriting based program transformation of Chiba et al. (2005) to higher-order term rewriting, we need extensibility, a property stating that inductive theorems are preserved by adding new functions via macros. In this paper, we propose and study a new notion of inductive theorems for higher-order rewriting, natural inductive theorems. This allows to incorporate properties such as extensionality and extensibility, based on simply typed S-expression rewriting (Yamada, 2001).

BibTeX - Entry

@InProceedings{aoto_et_al:LIPIcs:2011:3111,
  author =	{Takahito Aoto and Toshiyuki Yamada and Yuki Chiba},
  title =	{{Natural Inductive Theorems for Higher-Order Rewriting}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{107--121},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9 },
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Manfred Schmidt-Schau{\ss}},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3111},
  URN =		{urn:nbn:de:0030-drops-31119},
  doi =		{10.4230/LIPIcs.RTA.2011.107},
  annote =	{Keywords: Inductive Theorems, Higher-Order Equational Logic, Simply-Typed S-Expression Rewriting Systems, Term Rewriting Systems}
}

Keywords: Inductive Theorems, Higher-Order Equational Logic, Simply-Typed S-Expression Rewriting Systems, Term Rewriting Systems
Collection: 22nd International Conference on Rewriting Techniques and Applications (RTA'11)
Issue Date: 2011
Date of publication: 26.04.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI