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;]

---

A Recursive Approach to Solving Parity Games in Quasipolynomial Time

Karoliina Lehtinen ; Paweł Parys ; Sven Schewe ; Dominik Wojtczak.

Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of&nbsp;[&hellip;]

---

Weak Alternating Timed Automata

Pawel Parys ; Igor Walukiewicz.

Alternating timed automata on infinite words are considered. The main result is a characterization of acceptance conditions for which the emptiness problem for these automata is decidable. This result implies new decidability results for fragments of timed temporal logics. It is also shown that,&nbsp;[&hellip;]

---