Evaluation is MSOL compatible - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Evaluation is MSOL compatible

Sylvain Salvati

Résumé

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.
Fichier principal
Vignette du fichier
m.pdf (1 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00773126 , version 1 (11-01-2013)
hal-00773126 , version 2 (14-01-2013)

Identifiants

Citer

Sylvain Salvati, Igor Walukiewicz. Evaluation is MSOL compatible. FSTTCS, 2013, Guwahati, India. pp.103-114, ⟨10.4230/LIPIcs.FSTTCS.2013.103⟩. ⟨hal-00773126v2⟩
276 Consultations
116 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More