Evaluation is MSOL compatible

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 properties of terms. Another application is decidability of a control-flow synthesis problem.
Type de document :
Communication dans un congrès
FSTTCS, 2013, Guwahati, India. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 24, pp.103-114, 2013, LIPIcs. 〈10.4230/LIPIcs.FSTTCS.2013.103〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00773126
Contributeur : Sylvain Salvati <>
Soumis le : lundi 14 janvier 2013 - 22:33:00
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : samedi 1 avril 2017 - 05:03:14

Fichier

m.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sylvain Salvati, Igor Walukiewicz. Evaluation is MSOL compatible. FSTTCS, 2013, Guwahati, India. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 24, pp.103-114, 2013, LIPIcs. 〈10.4230/LIPIcs.FSTTCS.2013.103〉. 〈hal-00773126v2〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

123