5 papers · 1 filter
Subsumption in with TBoxes Is in ExpTime
Michał Henne, Barbara Morawska, Paweł Parys
Description Logics (DLs) are a family of formal languages used for representing and reasoning about structured knowledge in terms of concepts and their relationships. The expressiv…
Generalised Quantifiers Based on Rabin-Mostowski Index
Denis Kuperberg, Damian Niwiński, Paweł Parys +1
In this work we introduce new generalised quantifiers which allow us to express the Rabin-Mostowski index of automata. Our main results study expressive power and decidability of t…
A Dichotomy Theorem for Ordinal Ranks in MSO
Damian Niwiński, Paweł Parys, Michał Skrzypczak
We focus on formulae of monadic second-order logic over the full binary tree, such that the witness is a well-founded set. The ordinal rank $\mathr…
Extending the WMSO+U Logic With Quantification Over Tuples
Anita Badyl, Paweł Parys
We study a new extension of the weak MSO logic, talking about boundedness. Instead of a previously considered quantifier U, expressing the fact that there exist arbitrarily large f…
On the Computability of Measures of Regular Sets of Infinite Trees
Damian Niwiński, Paweł Parys, Michał Skrzypczak
The Rabin tree theorem yields an algorithm to solve the satisfiability problem for monadic second-order logic over infinite trees. Here we solve the probabilistic variant of this p…