Higher-Order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties

10/13/2020
by   Christopher H. Broadbent, et al.
0

This paper studies the logical properties of a very general class of infinite ranked trees, namely those generated by higher-order recursion schemes. We consider three main problems – model-checking, logical refection (aka global model-checking) and selection – for both monadic second-order logic and modal mu-calculus and prove that they can be effectively answered positively. For that, we rely on the known connexion between higher-order recursion schemes and collapsible pushdown automata and on previous work regarding parity games played on transition graphs of collapsible pushdown automata.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset