License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2018.26
URN: urn:nbn:de:0030-drops-91964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9196/
Go to the corresponding LIPIcs Volume Portal

Nishida, Naoki ; Maeda, Yuya

Narrowing Trees for Syntactically Deterministic Conditional Term Rewriting Systems

pdf-format:
LIPIcs-FSCD-2018-26.pdf (0.6 MB)

Abstract

A narrowing tree for a constructor term rewriting system and a pair of terms is a finite representation for the space of all possible innermost-narrowing derivations that start with the pair and end with non-narrowable terms. Narrowing trees have grammar representations that can be considered regular tree grammars. Innermost narrowing is a counterpart of constructor-based rewriting, and thus, narrowing trees can be used in analyzing constructor-based rewriting to normal forms. In this paper, using grammar representations, we extend narrowing trees to syntactically deterministic conditional term rewriting systems that are constructor systems. We show that narrowing trees are useful to prove two properties of a normal conditional term rewriting system: one is infeasibility of conditional critical pairs and the other is quasi-reducibility.

BibTeX - Entry

@InProceedings{nishida_et_al:LIPIcs:2018:9196,
  author =	{Naoki Nishida and Yuya Maeda},
  title =	{{Narrowing Trees for Syntactically Deterministic Conditional Term Rewriting Systems}},
  booktitle =	{3rd International Conference on Formal Structures for  Computation and Deduction (FSCD 2018)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-077-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{108},
  editor =	{H{\'e}l{\`e}ne Kirchner},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9196},
  URN =		{urn:nbn:de:0030-drops-91964},
  doi =		{10.4230/LIPIcs.FSCD.2018.26},
  annote =	{Keywords: conditional term rewriting, innermost narrowing, regular tree grammar}
}

Keywords: conditional term rewriting, innermost narrowing, regular tree grammar
Collection: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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