19 citations · 44 across the 18 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…