4 citations · 9 across the 9 of their papers we have counts for
7 papers · 1 filter
A finer reparameterisation theorem for MSO and FO queries on strings
Lê Thành Dũng Nguyên, Paweł Parys
We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(…
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…
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…
Intersection Types for Unboundedness Problems
Paweł Parys
Intersection types have been originally developed as an extension of simple types, but they can also be used for refining simple types. In this survey we concentrate on the latter…
Intersection Types and Counting
Paweł Parys
We present a new approach to the following meta-problem: given a quantitative property of trees, design a type system such that the desired property for the tree generated by an in…