Up2Europe est un accélérateur d’idées pour des projets de coopération.
La plateforme Ma Région Sud fait partie de l'écosystème de Up2Europe qui permet de booster la coopération à un niveau supérieur!
Besoin d'aide ? La Région Sud vous accompagne
Laissez-vous guider par notre équipe d'experts ! Saisissez votre mail et nous reviendrons vers vous rapidement
Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones
(CSP-Infinity)
Date du début: 1 oct. 2016,
Date de fin: 30 sept. 2021
PROJET
TERMINÉ
The complexity of constraint satisfaction problems (CSPs) is a field in rapid development, and involves central questions in graph homomorphisms, finite model theory, reasoning in artificial intelligence, and, last but not least, universal algebra. In previous work, it was shown that a substantial part of the results and tools for the study of the computational complexity of CSPs can be generalised to infinite domains when the constraints are definable over a homogeneous structure. There are many computational problems, in particular in temporal and spatial reasoning, that can be modelled in this way, but not over finite domains. Also in finite model theory and descriptive complexity, CSPs over infinite domains arise systematically as problems in monotone fragments of existential second-order logic.In this project, we will advance in three directions:(a) Further develop the universal-algebraic approach for CSPs over homogeneous structures. E.g., provide evidence for a universal-algebraic tractability conjecture for such CSPs.(b) Apply the universal-algebraic approach. In particular, classify the complexity of all problems in guarded monotone SNP, a logic discovered independently in finite model theory and ontology-based data-access.(c) Investigate the complexity of CSPs over those infinite domains that are most relevant in computer science, namely the integers, the rationals, and the reals. Can we adapt the universal-algebraic approach to this setting?
Accédez au prémier réseau pour la cooperation européenne
Se connecter
Bonjour, vous êtes sur la plateforme Région Sud Provence-Alpes-Côte d’Azur dédiée aux programmes thématiques et de coopération territoriale. Une équipe d’experts vous accompagne dans vos recherches de financements.
Contactez-nous !
Contactez la Région Sud Provence-Alpes-Côte d'Azur
Vous pouvez nous écrire en Anglais, Français et Italien