Opendata, web and dolomites


Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones

Total Cost €


EC-Contrib. €






Project "CSP-Infinity" data sheet

The following table provides information about the project.


Organization address
postcode: 1069

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Germany [DE]
 Project website
 Total cost 1˙416˙250 €
 EC max contribution 1˙416˙250 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2015-CoG
 Funding Scheme ERC-COG
 Starting year 2016
 Duration (year-month-day) from 2016-10-01   to  2021-09-30


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 


 Project objective

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?


year authors and title journal last update
List of publications.
2018 Manuel Bodirsky, Barnaby Martin, Antoine Mottet
Discrete Temporal Constraint Satisfaction Problems
published pages: 1-41, ISSN: 0004-5411, DOI: 10.1145/3154832
Journal of the ACM 65/2 2019-10-29
2019 Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
published pages: 1224-1264, ISSN: 0097-5397, DOI: 10.1137/16m1082974
SIAM Journal on Computing 48/4 2019-10-29
2018 Manuel Bodirsky, David Evans, Michael Kompatscher, Michael Pinsker
A counterexample to the reconstruction of ω-categorical structures from their endomorphism monoid
published pages: 57-82, ISSN: 0021-2172, DOI: 10.1007/s11856-018-1645-9
Israel Journal of Mathematics 224/1 2019-10-29
2018 Manuel Bodirsky, David Bradley-Williams, Michael Pinsker, András Pongrácz
The universal homogeneous binary tree
published pages: 133-163, ISSN: 0955-792X, DOI: 10.1093/logcom/exx043
Journal of Logic and Computation 28/1 2019-10-29
2018 Manuel Bodirsky, Antoine Mottet
A Dichotomy for First-Order Reducts of Unary Structures
published pages: , ISSN: 1860-5974, DOI:
Logical Methods in Computer Science Volume 14, Issue 2 2019-10-29
2018 Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
published pages: , ISSN: , DOI:
1 2019-10-09
2018 Manuel Bodirsky, Marcello Mamino
Tropically Convex Constraint Satisfaction
published pages: 481-509, ISSN: 1432-4350, DOI: 10.1007/s00224-017-9762-0
Theory of Computing Systems 62/3 2019-10-09
2018 Martin, Barnaby; Jonsson, Peter; Bodirsky, Manuel; Mottet, Antoine
Classification transfer for qualitative reasoning problems
published pages: , ISSN: , DOI:
2 2019-10-09
2017 Bodirsky, Manuel ; Mamino, Marcello
Constraint Satisfaction Problems over Numeric Domains
published pages: , ISSN: , DOI: 10.4230/DFU.Vol7.15301.79
2018 Erhard Aichinger, Nebojša Mudrinski, Jakub Opršal
Complexity of term representations of finitary functions
published pages: 1101-1118, ISSN: 0218-1967, DOI: 10.1142/S0218196718500480
International Journal of Algebra and Computation 28/06 2019-06-18
2018 Bodirsky, Manuel; Martin, Barnaby; Mamino, Marcello; Mottet, Antoine
The complexity of disjunctive linear Diophantine constraints
published pages: , ISSN: , DOI:
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, 27-31 August 2018 [Conference proceedings] 1 2019-06-18
2018 Bodirsky, Manuel; Mamino, Marcello; Viola, Caterina
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
published pages: , ISSN: , DOI:
27th EACSL Annual Conference on Computer Science Logic (CSL 2018) 6 2019-06-18
2018 Libor Barto, Jakub Opršal, Michael Pinsker
The wonderland of reflections
published pages: 363-398, ISSN: 0021-2172, DOI: 10.1007/s11856-017-1621-9
Israel Journal of Mathematics 223/1 2019-06-18

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "CSP-INFINITY" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "CSP-INFINITY" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

VictPart (2019)

Righting Victim Participation in Transitional Justice

Read More  


The Enemy of the Good: Towards a Theory of Moral Progress

Read More  

Photopharm (2020)

Photopharmacology: From Academia toward the Clinic.

Read More