Higher-order program verification via HFL model checking

N Kobayashi, T Tsukada, K Watanabe - … , ESOP 2018, Held as Part of the …, 2018 - Springer
There are two kinds of higher-order extensions of model checking: HORS model checking
and HFL model checking. Whilst the former has been applied to automated verification of …

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

C Grellois, PA Melliès - International Symposium on Mathematical …, 2015 - Springer
In this paper, we explain how the connection between higher-order model-checking and
linear logic recently exhibited by the authors leads to a new and conceptually enlightening …

Compositional higher-order model checking via ω-regular games over Böhm trees

T Tsukada, CHL Ong - Proceedings of the Joint Meeting of the Twenty …, 2014 - dl.acm.org
We introduce type-checking games, which are ω-regular games over Böhm trees,
determined by a type of the Kobayashi-Ong intersection type system. These games are a …

A model for behavioural properties of higher-order programs

S Salvati, I Walukiewicz - 24th EACSL Annual Conference on Computer …, 2015 - hal.science
We consider simply typed lambda-calculus with fixpoints as a non-interpreted functional
programming language: the result of the execution of a program is its normal form that can …

Semantics of linear logic and higher-order model-checking

C Grellois - 2016 - hal.science
This thesis studies problems of higher-order model-checking from a semantic and logical
perspective. Higher-order model-checking is concerned with the verification of properties …

Higher-order recursion schemes and collapsible pushdown automata: Logical properties

CH Broadbent, A Carayol, CHL Ong… - ACM Transactions on …, 2021 - dl.acm.org
This article studies the logical properties of a very general class of infinite ranked trees,
namely, those generated by higher-order recursion schemes. We consider, for both monadic …

Typing weak MSOL properties

S Salvati, I Walukiewicz - Logical Methods in Computer …, 2017 - lmcs.episciences.org
We consider lambda-Y-calculus as a non-interpreted functional programming language: the
result of the execution of a program is its normal form that can be seen as the tree of calls to …

Automatically disproving fair termination of higher-order functional programs

K Watanabe, R Sato, T Tsukada, N Kobayashi - ACM SIGPLAN Notices, 2016 - dl.acm.org
We propose an automated method for disproving fair termination of higher-order functional
programs, which is complementary to Murase et al.'s recent method for proving fair …

Lambda y-calculus with priorities

I Walukiewicz - 2019 34th Annual ACM/IEEE Symposium on …, 2019 - ieeexplore.ieee.org
The lambda Y-calculus with priorities is a variant of the simply-typed lambda calculus
designed for higher-order model-checking. The higher-order model-checking problem asks …

A type system describing unboundedness

P Parys - Discrete Mathematics & Theoretical Computer …, 2020 - dmtcs.episciences.org
We consider nondeterministic higher-order recursion schemes as recognizers of languages
of finite words or finite trees. We propose a type system that allows to solve the simultaneous …