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

Submitted 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

33 Documents citing this article

Libor Barto;Bertalan Bodor;Marcin Kozik;Antoine Mottet;Michael Pinsker, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, pp. 1-13, 2023, Boston, MA, USA, 10.1109/lics56636.2023.10175732.

Antoine Mottet;Michael Pinsker, arXiv (Cornell University), Smooth approximations and CSPs over finitely bounded homogeneous structures, pp. 1-13, 2022, Haifa Israel, 10.1145/3531130.3533353, https://arxiv.org/abs/2011.03978.

Michael Pinsker, arXiv (Cornell University), Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep, 168, pp. 80-87, 2022, Dallas, TX, USA, 10.1109/ismvl52857.2022.00019, https://arxiv.org/abs/2203.17182.

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;Bertalan Bodor, 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property, 57, pp. 1-13, 2021, Rome, Italy, 10.1109/lics52264.2021.9470683.

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), arXiv (Cornell University), 49, 2, pp. 365-393, 10.1137/18m1216213, https://arxiv.org/abs/1909.06201.

Manuel Bodirsky;Antoine Mottet;Miroslav Olšák;Jakub Opršal;Michael Pinsker;et al., 2020, 𝜔-categorical structures avoiding height 1 identities, Transactions of the American Mathematical Society, 374, 1, pp. 327-350, 10.1090/tran/8179, https://doi.org/10.1090/tran/8179.

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

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, https://arxiv.org/abs/1409.4601.

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

Manuel Bodirsky;Barnaby Martin;Michael Pinsker;András Pongrácz, 2019, Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, SIAM Journal on Computing, 48, 4, pp. 1224-1264, 10.1137/16m1082974, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.119.

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, arXiv (Cornell University), Finite Relation Algebras with Normal Representations, pp. 3-17, 2018, 10.1007/978-3-030-02149-8_1, https://arxiv.org/abs/1810.13335.

Manuel Bodirsky;Florent Madelaine;Antoine Mottet, arXiv (Cornell University), A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP, 2018, Oxford United Kingdom, 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, Theoretical Computer Science, 703, pp. 18-36, 10.1016/j.tcs.2017.08.025, https://doi.org/10.1016/j.tcs.2017.08.025.

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

Manuel Bodirsky;David Bradley-Williams;Michael Pinsker;András Pongrácz, 2017, The universal homogeneous binary tree, Repository of the Academy's Library (Library of the Hungarian Academy of Sciences), 28, 1, pp. 133-163, 10.1093/logcom/exx043, http://real.mtak.hu/161344/1/1409.2170.pdf.

Manuel Bodirsky;Peter Jonsson;Trung Van Pham, 2017, The Complexity of Phylogeny Constraint Satisfaction Problems, arXiv (Cornell University), 18, 3, pp. 1-42, 10.1145/3105907, https://arxiv.org/abs/1503.07310.

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, https://doi.org/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, https://arxiv.org/abs/1303.7429.

Libor Barto;Michael Pinsker, arXiv (Cornell University), The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems, 2016, New York NY USA, 10.1145/2933575.2934544, https://arxiv.org/abs/1602.04353.

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

Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Torunczyk, CiteSeer X (The Pennsylvania State University), Locally Finite Constraint Satisfaction Problems, pp. 475-486, 2015, Kyoto, Japan, 10.1109/lics.2015.51, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.702.3798.

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

Manuel Bodirsky;Victor Dalmau;Barnaby Martin;Antoine Mottet;Michael Pinsker, 2015, Distance constraint satisfaction problems, Information and Computation, 247, pp. 87-105, 10.1016/j.ic.2015.11.010, https://doi.org/10.1016/j.ic.2015.11.010.

Manuel Bodirsky;H. Dugald Macpherson;Johan Thapper, 2013, Constraint satisfaction tractability from semi-lattice operations on infinite sets, 14, 4, pp. 1-19, 10.1145/2528933, https://hal.science/hal-00756929.

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

Manuel Bodirsky;Jan Kára, 2010, The complexity of temporal constraint satisfaction problems, CiteSeer X (The Pennsylvania State University), 57, 2, pp. 1-41, 10.1145/1667053.1667058, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.2354.

Manuel Bodirsky;Martin Hils;Barnaby Martin, arXiv (Cornell University), On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction, 117, pp. 90-99, 2010, Edinburgh, United Kingdom, 10.1109/lics.2010.13, https://arxiv.org/abs/0909.5097.

Manuel Bodirsky;Jan Kara, CiteSeer X (The Pennsylvania State University), The complexity of temporal constraint satisfaction problems, pp. 29-38, 2008, Victoria British Columbia Canada, 10.1145/1374376.1374382, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.422.896.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1547 times.

This article's PDF has been downloaded 337 times.