From the 1 of 5 linked papers with an AI index.
5 papers
A Dichotomy Theorem for Ordinal Ranks in MSO
Damian NiwiÅski, PaweÅ Parys, MichaÅ Skrzypczak
The paper investigates monadic second‑order formulas over the full binary tree that require a well‑founded witness set, defines an ordinal rank for such sets, and proves a decidabl…
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…
Constrained Adaptive Rejection Sampling
PaweÅ Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick +1
Language Models (LMs) are increasingly used in applications where generated outputs must satisfy strict semantic or syntactic constraints. Existing approaches to constrained genera…
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…
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…