6 citations · 8 across the 4 of their papers we have counts for
5 papers
Tractability Frontier for Dually-Closed Temporal Quantified Constraint Satisfaction Problems
Michał Wrona
A temporal (constraint) language is a relational structure with a first-order definition in the rational numbers with the order. We study here the complexity of the Quantified Cons…
Tractability of Quantified Temporal Constraints To The Max
Manuel Bodirsky, Hubie Chen, Michał Wrona
A temporal constraint language is a set of relations that are first-order definable over (Q;<). We show that several temporal constraint languages whose constraint satisfaction pro…
Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
Antoine Mottet, Tomáš Nagy, Michael Pinsker +1
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities ) have low relational width. This implies a c…
On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width
Michał Wrona
The relational width of a finite structure, if bounded, is always (1,1) or (2,3). In this paper we study the relational width of first-order expansions of finitely bounded homogene…
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width
Michał Wrona
Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures first-order definable in countably infinite finitely bounded homogeneous structures…