Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Ikebuchi, Mirai; Nakano, Keisuke http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-91882
URL:

;

On Repetitive Right Application of B-Terms

pdf-format:


Abstract

B-terms are built from the B combinator alone defined by B == lambda f.lambda g.lambda x. f~(g~x), which is well-known as a function composition operator. This paper investigates an interesting property of B-terms, that is, whether repetitive right applications of a B-term cycles or not. We discuss conditions for B-terms to have and not to have the property through a sound and complete equational axiomatization. Specifically, we give examples of B-terms which have the property and show that there are infinitely many B-terms which do not have the property. Also, we introduce a canonical representation of B-terms that is useful to detect cycles, or equivalently, to prove the property, with an efficient algorithm.

BibTeX - Entry

@InProceedings{ikebuchi_et_al:LIPIcs:2018:9188,
  author =	{Mirai Ikebuchi and Keisuke Nakano},
  title =	{{On Repetitive Right Application of B-Terms}},
  booktitle =	{3rd International Conference on Formal Structures for  Computation and Deduction (FSCD 2018)},
  pages =	{18:1--18:15},
  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/9188},
  URN =		{urn:nbn:de:0030-drops-91882},
  doi =		{10.4230/LIPIcs.FSCD.2018.18},
  annote =	{Keywords: Combinatory logic, B combinator, Lambda calculus}
}

Keywords: Combinatory logic, B combinator, Lambda calculus
Seminar: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
Issue date: 2018
Date of publication: 2018


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