文章基本信息

标题：Evaluation is MSOL-compatible
本地全文：下载
作者：Sylvain Salvati ; Igor Walukiewicz
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：103-114
DOI：10.4230/LIPIcs.FSTTCS.2013.103
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Simply typed $lambda Y$-calculus; Monadic second order