56
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Finitary semantics of linear logic and higher-order model-checking

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          This article is concerned with semantic methods for higher-order verification. Given an alternating parity automaton A, we introduce a variant of the Scott semantics of linear logic extended with a colouring modality and a fixed point operator. We prove that the interpretation of a higher-order recursion scheme in the resulting model of the lambdaY-calculus is the set of states from which the tree it generates is accepted by A. The finiteness of the model therefore leads to a new proof of the decidability of MSO formulas at the root of trees generated by higher-order recursion schemes. By using a connection between the denotations in this model and an appropriate type system, together with the finiteness of the semantics, we also obtain a new decidability proof of the selection problem.

          Related collections

          Author and article information

          Journal
          1502.05147

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article