4 citations · 9 across the 6 of their papers we have counts for
13 papers
Unboundedness for Recursion Schemes: A Simpler Type System
David Barozzini, Paweł Parys, Jan Wróblewski
Decidability of the problems of unboundedness and simultaneous unboundedness (aka. the diagonal problem) for higher-order recursion schemes was established by Clemente, Parys, Salv…
Higher-Order Model Checking Step by Step
Paweł Parys
We show a new simple algorithm that solves the model-checking problem for recursion schemes: check whether the tree generated by a given higher-order recursion scheme is accepted b…
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…
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…
Compositionality of the MSO+U Logic
Paweł Parys
We prove that the MSO+U logic is compositional in the following sense: whether an MSO+U formula holds in a tree T depends only on MSO+U-definable properties of the root of T and of…
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…