Cores of Countably Categorical Structures

Manuel Bodirsky

doi:10.2168/LMCS-3(1:2)2007

Manuel Bodirsky - Cores of Countably Categorical Structures

lmcs:2224 - Logical Methods in Computer Science, January 25, 2007, Volume 3, Issue 1 - https://doi.org/10.2168/LMCS-3(1:2)2007

Cores of Countably Categorical StructuresArticle

Authors: Manuel Bodirsky

A relational structure is a core, if all its endomorphisms are embeddings.
This notion is important for computational complexity classification of constraint satisfaction problems. It is a fundamental fact that every finite structure has a core, i.e., has an endomorphism such that the structure induced by its image is a core; moreover, the core is unique up to isomorphism. Weprove that every \omega -categorical structure has a core. Moreover, every \omega-categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or \omega
-categorical. We discuss consequences for constraint satisfaction with \omega
-categorical templates.

https://doi.org/10.2168/LMCS-3(1:2)2007

Source: arXiv.org:cs/0612069

Volume: Volume 3, Issue 1

Published on: January 25, 2007

Imported on: September 23, 2005

Keywords: Computer Science - Logic in Computer Science, F.4.1

Licence: arXiv.org - Assumed non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

35 Documents citing this article

Antoine Mottet;Michael Pinsker, 2024, Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures, Journal of the ACM, 71, 5, pp. 1-47, 10.1145/3689207, https://doi.org/10.1145/3689207.

Libor Barto;Bertalan Bodor;Marcin Kozik;Antoine Mottet;Michael Pinsker, 2023, Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, Homo Politicus (Academy of Humanities and Economics in Lodz), pp. 1-13, 10.1109/lics56636.2023.10175732, https://ruj.uj.edu.pl/xmlui/handle/item/326045.

Antoine Mottet;Michael Pinsker, 2022, Smooth approximations and CSPs over finitely bounded homogeneous structures, Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 1-13, 10.1145/3531130.3533353.

Michael Pinsker, 2022, Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep, 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL), pp. 80-87, 10.1109/ismvl52857.2022.00019.

Manuel Bodirsky;Bertalan Bodor, 2021, Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property, 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-13, 10.1109/lics52264.2021.9470683.

Manuel Bodirsky;Bertalan Bodor, 2021, Permutation groups with small orbit growth, Journal of Group Theory, 24, 4, pp. 643-709, 10.1515/jgth-2018-0220, https://doi.org/10.1515/jgth-2018-0220.

Manuel Bodirsky;Florent Madelaine;Antoine Mottet, 2021, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, SIAM Journal on Computing, 50, 4, pp. 1359-1409, 10.1137/19m128466x.

Mike Behrisch;Edith Vargas-García, 2021, On a stronger reconstruction notion for monoids and clones, arXiv (Cornell University), 33, 6, pp. 1487-1506, 10.1515/forum-2020-0205, http://arxiv.org/abs/1901.08683.

Libor Barto;Michael Pinsker, 2020, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), SIAM Journal on Computing, 49, 2, pp. 365-393, 10.1137/18m1216213.

Manuel Bodirsky;Thomas Quinn-Gregson, 2020, Solving equation systems in ω-categorical algebras, Journal of Mathematical Logic, 21, 03, 10.1142/s0219061321500203.

Manuel Bodirsky;Antoine Mottet;Miroslav Olšák;Jakub Opršal;Michael Pinsker;Ross Willard, 2020, 𝜔-categorical structures avoiding height 1 identities, arXiv (Cornell University), 374, 1, pp. 327-350, 10.1090/tran/8179, http://arxiv.org/abs/2006.12254.

Libor Barto;Michael Kompatscher;Miroslav Olšák;Van Pham Trung;Michael Pinsker, 2019, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, Journal of Mathematical Logic, 19, 02, pp. 1950010, 10.1142/s0219061319500107.

MANUEL BODIRSKY;MICHAEL PINSKER;ANDRÁS PONGRÁCZ, 2019, PROJECTIVE CLONE HOMOMORPHISMS, arXiv (Cornell University), 86, 1, pp. 148-161, 10.1017/jsl.2019.23, http://arxiv.org/abs/1409.4601.

Manuel Bodirsky;Barnaby Martin;Michael Pinsker;András Pongrácz, 2019, Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, Durham Research Online (Durham University), 48, 4, pp. 1224-1264, 10.1137/16m1082974, http://dro.dur.ac.uk/20039/.

Manuel Bodirsky;Antoine Mottet;Miroslav Olsak;Jakub Oprsal;Michael Pinsker;Ross Willard, 2019, Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems), arXiv (Cornell University), pp. 1-12, 10.1109/lics.2019.8785883, http://arxiv.org/abs/1901.04237.

G. Mashevitzky;B. Plotkin;E. Plotkin, 2018, Action of endomorphism semigroups on definable sets, International Journal of Algebra and Computation, 28, 08, pp. 1585-1612, 10.1142/s0218196718400106.

Manuel Bodirsky, 2018, Finite Relation Algebras with Normal Representations, Lecture notes in computer science, pp. 3-17, 10.1007/978-3-030-02149-8_1.

Manuel Bodirsky;Florent Madelaine;Antoine Mottet, 2018, A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP, arXiv (Cornell University), pp. 105-114, 10.1145/3209108.3209156, http://arxiv.org/abs/1802.03255.

Christian Glaßer;Peter Jonsson;Barnaby Martin, 2017, Circuit satisfiability and constraint satisfaction around Skolem Arithmetic, Durham Research Online (Durham University), 703, pp. 18-36, 10.1016/j.tcs.2017.08.025, http://dro.dur.ac.uk/22848/.

Libor Barto;Michael Kompatscher;Miroslav Olsak;Trung Van Pham;Michael Pinsker, 2017, The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems, 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-12, 10.1109/lics.2017.8005128.

Manuel Bodirsky;David Bradley-Williams;Michael Pinsker;András Pongrácz, 2017, The universal homogeneous binary tree, arXiv (Cornell University), 28, 1, pp. 133-163, 10.1093/logcom/exx043, http://arxiv.org/abs/1409.2170.

Manuel Bodirsky;Peter Jonsson;Trung Van Pham, 2017, The Complexity of Phylogeny Constraint Satisfaction Problems, ACM Transactions on Computational Logic, 18, 3, pp. 1-42, 10.1145/3105907.

Peter Jonsson, 2017, Constants and finite unary relations in qualitative constraint reasoning, Artificial Intelligence, 257, pp. 1-23, 10.1016/j.artint.2017.12.003.

Christian Pech;Maja Pech, 2016, Towards a Ryll‐Nardzewski‐type theorem for weakly oligomorphic structures, arXiv (Cornell University), 62, 1-2, pp. 25-34, 10.1002/malq.201400067, http://arxiv.org/abs/1303.7429.

Libor Barto;Michael Pinsker, 2016, The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 615-622, 10.1145/2933575.2934544.

Manuel Bodirsky;Antoine Mottet, 2016, Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 623-632, 10.1145/2933575.2934515.

Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Torunczyk, 2015, Locally Finite Constraint Satisfaction Problems, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, abs 1203 1876, pp. 475-486, 10.1109/lics.2015.51.

Manuel Bodirsky, 2015, Ramsey classes: examples and constructions, arXiv (Cornell University), pp. 1-48, 10.1017/cbo9781316106853.002, http://arxiv.org/abs/1502.05146.

Manuel Bodirsky;Victor Dalmau;Barnaby Martin;Antoine Mottet;Michael Pinsker, 2015, Distance constraint satisfaction problems, arXiv (Cornell University), 247, pp. 87-105, 10.1016/j.ic.2015.11.010, http://arxiv.org/abs/1004.3842.

Manuel Bodirsky;H. Dugald Macpherson;Johan Thapper, 2013, Constraint satisfaction tractability from semi-lattice operations on infinite sets, arXiv (Cornell University), 14, 4, pp. 1-19, 10.1145/2528933, http://arxiv.org/abs/1111.6616.

Manuel Bodirsky;Víctor Dalmau, 2012, Datalog and constraint satisfaction with infinite templates, RECERCAT (Consorci de Serveis Universitaris de Catalunya), 79, 1, pp. 79-100, 10.1016/j.jcss.2012.05.012, http://hdl.handle.net/10230/36351.

Dugald Macpherson, 2011, A survey of homogeneous structures, Discrete Mathematics, 311, 15, pp. 1599-1634, 10.1016/j.disc.2011.01.024.

Manuel Bodirsky;Jan Kára, 2010, The complexity of temporal constraint satisfaction problems, Journal of the ACM, 57, 2, pp. 1-41, 10.1145/1667053.1667058.

Manuel Bodirsky;Martin Hils;Barnaby Martin, 2010, On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction, 2010 25th Annual IEEE Symposium on Logic in Computer Science, 117, pp. 90-99, 10.1109/lics.2010.13.

Manuel Bodirsky;Jan Kara, 2008, The complexity of temporal constraint satisfaction problems, Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 29-38, 10.1145/1374376.1374382.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3195 times.

This article's PDF has been downloaded 557 times.