License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.49
URN: urn:nbn:de:0030-drops-155602
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15560/
Go to the corresponding LIPIcs Volume Portal

Kikuchi, Kentaro ; Aoto, Takahito

Simple Derivation Systems for Proving Sufficient Completeness of Non-Terminating Term Rewriting Systems

pdf-format:
LIPIcs-FSTTCS-2021-49.pdf (0.6 MB)

Abstract

A term rewriting system (TRS) is said to be sufficiently complete when each function yields some value for any input. Proof methods for sufficient completeness of terminating TRSs have been well studied. In this paper, we introduce a simple derivation system for proving sufficient completeness of possibly non-terminating TRSs. The derivation system consists of rules to manipulate a set of guarded terms, and sufficient completeness of a TRS holds if there exists a successful derivation for each function symbol. We also show that variations of the derivation system are useful for proving special cases of local sufficient completeness of TRSs, which is a generalised notion of sufficient completeness.

BibTeX - Entry

@InProceedings{kikuchi_et_al:LIPIcs.FSTTCS.2021.49,
  author =	{Kikuchi, Kentaro and Aoto, Takahito},
  title =	{{Simple Derivation Systems for Proving Sufficient Completeness of Non-Terminating Term Rewriting Systems}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15560},
  URN =		{urn:nbn:de:0030-drops-155602},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.49},
  annote =	{Keywords: Term rewriting, Sufficient completeness, Local sufficient completeness, Non-termination, Derivation rule, Well-founded induction schema}
}

Keywords: Term rewriting, Sufficient completeness, Local sufficient completeness, Non-termination, Derivation rule, Well-founded induction schema
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

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