72 citations · 368 across the 79 of their papers we have counts for
36 papers · 1 filter
The Complexity of Resilience for Digraph Queries
Manuel Bodirsky, Žaneta Semanišinová
We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature of directe…
Taking model-complete cores
Manuel Bodirsky, Bertalan Bodor, Paolo Marimon
A first-order theory is a model-complete core theory if every first-order formula is equivalent modulo to an existential positive formula; a core companion of a theory …
On the Computational Power of Extensional ESO
Manuel Bodirsky, Santiago Guzmán Pro
Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence and an input structure $\mathbb…
Structures preserved by primitive actions of
Manuel Bodirsky, Bertalan Bodor
We present a dichotomy for structures that are preserved by primitive actions of : such a structure primitively positively constructs all finite…
Hereditary First-Order Logic: the tractable quantifier prefix classes
Manuel Bodirsky, Santiago Guzmán-Pro
Many computational problems can be modelled as the class of all finite structures that satisfy a fixed first-order sentence hereditarily, i.e., we require that ever…
A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
Manuel Bodirsky, Édouard Bonnet, Žaneta Semanišinová
We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain that is preserved by all order-preserving bije…