11 citations · 39 across the 9 of their papers we have counts for
10 papers
Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes
Balder ten Cate, Víctor Dalmau, Jakub Opršal
A Datalog program can be viewed as a syntactic specification of a functor from database instances over some schema to database instances over another schema. The same holds more ge…
Functors on relational structures which admit both left and right adjoints
Víctor Dalmau, Andrei Krokhin, Jakub Opršal
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors and between thin categories of relational s…
ω-categorical structures avoiding height 1 identities
Manuel Bodirsky, Antoine Mottet, Miroslav Olšák +3
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial…
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Manuel Bodirsky, Antoine Mottet, Miroslav Olšák +3
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial…
Deciding the existence of minority terms
Alexandr Kazda, Jakub Opršal, Matt Valeriote +1
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation that satisfies the minority equations $m(y,x,…
Complexity of term representations of finitary functions
Erhard Aichinger, Nebojša Mudrinski, Jakub Opršal
The clone of term operations of an algebraic structure consists of all operations that can be expressed by a term in the language of the structure. We consider bounds for the lengt…
Robust algorithms with polynomial loss for near-unanimity CSPs
Víctor Dalmau, Marcin Kozik, Andrei Krokhin +3
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain…
A relational description of higher commutators in Mal'cev varieties
Jakub Opršal
We give a relational description of higher commutator operators, which were introduced by Bulatov, in varieties with a Mal'cev term. Furthermore, we use this result to prove that f…
Distributive and anti-distributive Mendelsohn triple systems
Diane M. Donovan, Terry S. Griggs, Thomas A. McCourt +2
We prove that the existence spectrum of Mendelsohn triple systems whose associated quasigroups satisfy distributivity corresponds to the Loeschian numbers, and provide some enumera…
Universal Lyndon Words
Arturo Carpi, Gabriele Fici, Stepan Holub +2
A word over an alphabet is a Lyndon word if there exists an order defined on for which is lexicographically smaller than all of its conjugates (other than itself).…