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.FSTTCS.2013.103
URN: urn:nbn:de:0030-drops-43652
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4365/
Go to the corresponding LIPIcs Volume Portal

Salvati, Sylvain ; Walukiewicz, Igor

Evaluation is MSOL-compatible

pdf-format:
6.pdf (0.9 MB)

Abstract

We consider simply-typed lambda calculus with fixpoint operators.
Evaluation of a term gives as a result the Böhm tree of the term.
We show that evaluation is compatible with monadic second-order logic (MSOL). This means that for a fixed finite vocabulary of terms, the MSOL properties of Böhm trees of terms are effectively MSOL properties of terms themselves. Theorems of this kind have been known for some graph operations: unfolding, and Muchnik iteration. Similarly to those results, our main theorem has diverse applications. It can be used to show decidability results, to construct classes of graphs with decidable MSOL theory, or to obtain MSOL formulas expressing behavioral properties of terms. Another application is decidability of a control-flow synthesis problem.

BibTeX - Entry

@InProceedings{salvati_et_al:LIPIcs:2013:4365,
  author =	{Sylvain Salvati and Igor Walukiewicz},
  title =	{{Evaluation is MSOL-compatible}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{103--114},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4365},
  URN =		{urn:nbn:de:0030-drops-43652},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.103},
  annote =	{Keywords: Simply typed $lambda Y$-calculus; Monadic second order}
}

Keywords: Simply typed $lambda Y$-calculus; Monadic second order
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

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