@TechReport{      salvati:hal-00773126,
  Author        = "Salvati, Sylvain and Walukiewicz, Igor",
  Abstract      = {{We consider simply-typed lambda calculus with fixpoint operators. Evaluation of a term gives as a result the B{\"o}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{\"o}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.}},
  affiliation   = "INRIA Bordeaux - Sud-Ouest - INRIA Bordeaux - Sud-Ouest , Laboratoire Bordelais de Recherche en Informatique - LaBRI",
  date-added    = "2013-11-15 12:43:25 +0000",
  date-modified = "2013-12-21 21:21:41 +0000",
  hal_id        = "hal-00773126",
  Keywords      = "simply-typed lambda calculus and higher-order recursive schemes",
  Language      = "Anglais",
  Month         = "January",
  Pages         = "42",
  PDF           = "http://hal.inria.fr/hal-00773126/PDF/m.pdf",
  Title         = "{Evaluation is MSOL compatible}",
  Type          = "Rapport de recherche",
  URL           = "http://hal.inria.fr/hal-00773126",
  Year          = "2013",
  bdsk-url-1    = "http://hal.inria.fr/hal-00773126",
  File          = "Evaluation is MSOL compatible - Salvati, Walukiewicz (1) (0) - a - a - w.pdf",
  file-2        = "Evaluation is MSOL compatible - Salvati, Walukiewicz (0) (0) - a - a - w.pdf"
}

@TechReport{ salvati:hal-00773126, Author = "Salvati, Sylvain and Walukiewicz, Igor", Abstract = {{We consider simply-typed lambda calculus with fixpoint operators. Evaluation of a term gives as a result the B{\"o}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{\"o}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.}}, affiliation = "INRIA Bordeaux - Sud-Ouest - INRIA Bordeaux - Sud-Ouest , Laboratoire Bordelais de Recherche en Informatique - LaBRI", date-added = "2013-11-15 12:43:25 +0000", date-modified = "2013-12-21 21:21:41 +0000", hal_id = "hal-00773126", Keywords = "simply-typed lambda calculus and higher-order recursive schemes", Language = "Anglais", Month = "January", Pages = "42", PDF = "http://hal.inria.fr/hal-00773126/PDF/m.pdf", Title = "{Evaluation is MSOL compatible}", Type = "Rapport de recherche", URL = "http://hal.inria.fr/hal-00773126", Year = "2013", bdsk-url-1 = "http://hal.inria.fr/hal-00773126", File = "Evaluation is MSOL compatible - Salvati, Walukiewicz (1) (0) - a - a - w.pdf", file-2 = "Evaluation is MSOL compatible - Salvati, Walukiewicz (0) (0) - a - a - w.pdf" }