19 citations · 44 across the 18 of their papers we have counts for
12 papers · 1 filter
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic -Transitions Is 2-ExpTime-Complete
Stefan Göller, Paweł Parys
We consider the problem of deciding whether a given pushdown system all of whose -transitions are deterministic is weakly bisimulation finite, that is, whether it is w…
Higher-Order Nonemptiness Step by Step
Paweł Parys
We show a new simple algorithm that checks whether a given higher-order grammar generates a nonempty language of trees. The algorithm amounts to a procedure that transforms a gramm…
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 (wit…
Bisimulation Finiteness of Pushdown Systems Is Elementary
Stefan Göller, Paweł Parys
We show that in case a pushdown system is bisimulation equivalent to a finite system, there is already a bisimulation equivalent finite system whose size is elementarily bounded in…
Cost Automata, Safe Schemes, and Downward Closures
David Barozzini, Lorenzo Clemente, Thomas Colcombet +1
In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to sho…
Parity Games: Another View on Lehtinen's Algorithm
Paweł Parys
Recently, five quasi-polynomial-time algorithms solving parity games were proposed. We elaborate on one of the algorithms, by Lehtinen (2018). Czerwiński et al. (2019) observe that…
Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
Paweł Parys
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time…
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow +3
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and St…
The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
Lorenzo Clemente, Paweł Parys, Sylvain Salvati +1
A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We…
Ordered Tree-Pushdown Systems
Lorenzo Clemente, Paweł Parys, Sylvain Salvati +1
We define a new class of pushdown systems where the pushdown is a tree instead of a word. We allow a limited form of lookahead on the pushdown conforming to a certain ordering rest…
Higher-Order Pushdown Systems with Data
Paweł Parys
We propose a new extension of higher-order pushdown automata, which allows to use an infinite alphabet. The new automata recognize languages of data words (instead of normal words)…
Strictness of the Collapsible Pushdown Hierarchy
Alexander Kartzow, Paweł Parys
We present a pumping lemma for each level of the collapsible pushdown graph hierarchy in analogy to the second author's pumping lemma for higher-order pushdown graphs (without coll…