Zobrazeno 1 - 10
of 416
pro vyhledávání: '"BODIRSKY, MANUEL"'
Autor:
Bodirsky, Manuel, Guzmán-Pro, Santiago
Many computational problems can be modelled as the class of all finite relational structures $\mathbb A$ that satisfy a fixed first-order sentence $\phi$ hereditarily, i.e., we require that every substructure of $\mathbb A$ satisfies $\phi$. In this
Externí odkaz:
http://arxiv.org/abs/2411.10860
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon's simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity g
Externí odkaz:
http://arxiv.org/abs/2411.09646
We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain ${\mathbb Q}$ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classic
Externí odkaz:
http://arxiv.org/abs/2409.07285
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classes are Logspace, NP-complete, co-NP-complete and Pspace-complete. The p
Externí odkaz:
http://arxiv.org/abs/2408.13840
Autor:
Bodirsky, Manuel, Starke, Florian
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three Datalog fragments that are particularly important for finite-domain con
Externí odkaz:
http://arxiv.org/abs/2407.04924
Autor:
Bodirsky, Manuel, Guzmán-Pro, Santiago
In this paper, we introduce the generic circular triangle-free graph $\mathbb C_3$ and propose a finite axiomatization of its first order theory. In particular, our main results show that a countable graph $G$ embeds into $\mathbb C_3$ if and only if
Externí odkaz:
http://arxiv.org/abs/2404.12082
We study mixed identities for oligomorphic automorphism groups of countable relational structures. Our main result gives sufficient conditions for such a group to not admit a mixed identity without particular constants. We study numerous examples and
Externí odkaz:
http://arxiv.org/abs/2401.09205
Publikováno v:
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '24). Association for Computing Machinery, New York, NY, USA, Article 14, 1-14, 2024
Valued constraint satisfaction problems (VCSPs) constitute a large class of computational optimisation problems. It was shown recently that, over finite domains, every VCSP is in P or NP-complete, depending on the admitted cost functions. In this art
Externí odkaz:
http://arxiv.org/abs/2309.15654