Search

• < Previous
• 1
• Next >

---

Recursion Schemes, the MSO Logic, and the U quantifier

Paweł Parys.

We study the model-checking problem for recursion schemes: does the tree generated by a given higher-order recursion scheme satisfy a given logical sentence. The problem is known to be decidable for sentences of the MSO logic. We prove decidability for an extension of MSO in which we additionally&nbsp;[&hellip;]

---

On the Expressive Power of Higher-Order Pushdown Systems

Paweł Parys.

We show that deterministic collapsible pushdown automata of second order can recognize a language that is not recognizable by any deterministic higher-order pushdown automaton (without collapse) of any order. This implies that there exists a tree generated by a second order collapsible pushdown&nbsp;[&hellip;]

---