10 papers · 1 filter
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…
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…
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 $\mathb…
The Complexity of Resilience Problems via Valued Constraint Satisfaction
Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz
Valued constraint satisfaction problems (VCSPs) constitute a large class of computational optimization problems. It was shown recently that, over finite domains, every VCSP is in P…