×

On a stronger reconstruction notion for monoids and clones. (English) Zbl 1507.08001

Motivated by one of the central reconstruction results by M. Rubin [Proc. Lond. Math. Soc. (3) 69, No. 2, 225–249 (1994; Zbl 0799.03037)], the authors introduce a new reconstruction notion, called automatic action compatibility, which is stronger than automatic homeomorphicity [M. Bodirsky et al., Trans. Am. Math. Soc. 369, No. 5, 3707–3740 (2017; Zbl 1377.03021)]. It is required that any abstract algebraic isomorphism from a permutation group, transformation monoid or clone to another such a structure from a given class, having an equipotent carrier, respects the action. The authors show how to lift automatic action compatibility from groups to monoids and then to clones, subject to certain assumptions. As a consequence they obtain some interesting automatic action compatibility results for monoids and clones.

MSC:

08A35 Automorphisms and endomorphisms of algebraic structures
08A40 Operations and polynomials in algebraic structures, primal algebras
54H15 Transformation groups and semigroups (topological aspects)
08A02 Relational systems, laws of composition
03C15 Model theory of denumerable and separable structures
03C40 Interpolation, preservation, definability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Ahlbrandt and M. Ziegler, Quasi-finitely axiomatizable totally categorical theories, Ann. Pure Appl. Logic 30 (1986), 63-82. · Zbl 0592.03018
[2] S. Barbina, Automorphism groups of omega-categorical structures, PhD thesis, University of Leeds, 2004.
[3] S. Barbina and D. Macpherson, Reconstruction of homogeneous relational structures, J. Symb. Log. 72 (2007), no. 3, 792-802. · Zbl 1128.03022
[4] L. Barto, The constraint satisfaction problem and universal algebra, Bull. Symb. Log. 21 (2015), no. 3, 319-337. · Zbl 1336.68113
[5] L. Barto and M. Kozik, Constraint satisfaction problems solvable by local consistency methods, J. ACM 61 (2014), no. 1, Article ID 3. · Zbl 1295.68126
[6] L. Barto and M. Kozik, Robustly solvable constraint satisfaction problems, SIAM J. Comput. 45 (2016), no. 4, 1646-1669. · Zbl 1350.68127
[7] L. Barto and M. Kozik, Absorption in universal algebra and CSP, The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups 7, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2017), 45-77. · Zbl 1482.68160
[8] L. Barto, A. Krokhin and R. Willard, Polymorphisms, and how to use them, The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups 7, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Wadern (2017), 1-44. · Zbl 1482.68161
[9] M. Behrisch, J. K. Truss and E. Vargas-García, Reconstructing the topology on monoids and polymorphism clones of the rationals, Studia Logica 105 (2017), no. 1, 65-91. · Zbl 1371.08002
[10] J. Bernik, R. Drnovšek, D. Kokol Bukovšek, T. Košir, M. Omladič and H. Radjavi, On semitransitive Jordan algebras of matrices, J. Algebra Appl. 10 (2011), no. 2, 319-333. · Zbl 1254.17027
[11] J. Bernik, L. Grunenfelder, M. Mastnak, H. Radjavi and V. G. Troitsky, On semitransitive collections of operators, Semigroup Forum 70 (2005), no. 3, 436-450. · Zbl 1082.15027
[12] J. Bernik and M. Mastnak, Lie algebras acting semitransitively, Linear Algebra Appl. 438 (2013), no. 6, 2777-2792. · Zbl 1297.17005
[13] J. Bernik and M. Mastnak, On semitransitive Lie algebras of minimal dimension, Linear Multilinear Algebra 62 (2014), no. 2, 207-217. · Zbl 1326.17004
[14] M. Bhattacharjee, D. Macpherson, R. G. Möller and P. M. Neumann, Notes on Infinite Permutation Groups, Texts Read. Math. 12, Hindustan Book Agency, New Delhi, 1997. · Zbl 0916.20001
[15] M. Bodirsky, Cores of countably categorical structures, Log. Methods Comput. Sci. 3 (2007), no. 1, Paper No. 2. · Zbl 1128.03021
[16] M. Bodirsky and H. Chen, Oligomorphic clones, Algebra Universalis 57 (2007), no. 1, 109-125. · Zbl 1121.08005
[17] M. Bodirsky and V. Dalmau, Datalog and constraint satisfaction with infinite templates, J. Comput. System Sci. 79 (2013), no. 1, 79-100. · Zbl 1263.68051
[18] M. Bodirsky, M. Hils and B. Martin, On the scope of the universal-algebraic approach to constraint satisfaction, Log. Methods Comput. Sci. 8 (2012), no. 3, Paper No. 13. · Zbl 1308.68062
[19] M. Bodirsky, P. Jonsson and T. Van Pham, The complexity of phylogeny constraint satisfaction problems, ACM Trans. Comput. Log. 18 (2017), no. 3, Article ID 23. · Zbl 1407.68206
[20] M. Bodirsky and J. Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57 (2010), no. 2, Article ID 9. · Zbl 1327.68125
[21] M. Bodirsky and J. Nešetřil, Constraint satisfaction with countable homogeneous templates, J. Logic Comput. 16 (2006), no. 3, 359-373. · Zbl 1113.03026
[22] M. Bodirsky and M. Pinsker, Topological Birkhoff, Trans. Amer. Math. Soc. 367 (2015), no. 4, 2527-2549. · Zbl 1375.03032
[23] M. Bodirsky, M. Pinsker and A. Pongrácz, Reconstructing the topology of clones, Trans. Amer. Math. Soc. 369 (2017), no. 5, 3707-3740. · Zbl 1377.03021
[24] M. Bodirsky, M. Pinsker and A. Pongrácz, Projective clone homomorphisms, J. Symb. Log. 86 (2021), no. 1, 148-161. · Zbl 07370805
[25] A. Bulatov, P. Jeavons and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (2005), no. 3, 720-742. · Zbl 1071.08002
[26] A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Society, Los Alamitos (2017), 319-330.
[27] P. J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 148 (1976), no. 2, 127-139. · Zbl 0313.20022
[28] P. J. Cameron, Orbits of permutation groups on unordered sets. II, J. Lond. Math. Soc. (2) 23 (1981), no. 2, 249-264. · Zbl 0498.20003
[29] G. L. Cherlin, Homogeneous directed graphs. The imprimitive case, Logic Colloquium ’85 (Orsay 1985), Stud. Logic Found. Math. 122, North-Holland, Amsterdam (1987), 67-88. · Zbl 0623.03037
[30] K. Cvetko-Vah, D. Kokol Bukovšek, T. Košir and G. Kudryavtseva, Semitransitive subsemigroups of the singular part of the finite symmetric inverse semigroup, Acta Math. Hungar. 131 (2011), no. 1-2, 1-24. · Zbl 1232.20070
[31] K. Cvetko-Vah, D. Kokol Bukovšek, T. Košir, G. Kudryavtseva, Y. Lavrenyuk and A. Oliynyk, Semitransitive subsemigroups of the symmetric inverse semigroups, Semigroup Forum 78 (2009), no. 1, 138-147. · Zbl 1168.20028
[32] W. Hodges, Model Theory, Encyclopedia Math. Appl. 42, Cambridge University Press, Cambridge, 1993. · Zbl 0789.03031
[33] F. Klein, A comparative review of recent researches in geometry, Bull. Amer. Math. Soc. 2 (1893), no. 10, 215-249. · JFM 25.0871.02
[34] F. Klein, Vergleichende Betrachtungen über neuere geometrische Forschungen, Math. Ann. 43 (1893), no. 1, 63-100. · JFM 25.0871.01
[35] B. Larose and P. Tesson, Universal algebra and hardness results for constraint satisfaction problems, Theoret. Comput. Sci. 410 (2009), no. 18, 1629-1647. · Zbl 1172.68024
[36] D. Lascar, Autour de la propriété du petit indice, Proc. Lond. Math. Soc. (3) 62 (1991), no. 1, 25-53. · Zbl 0683.03017
[37] D. Macpherson, A survey of homogeneous structures, Discrete Math. 311 (2011), no. 15, 1599-1634. · Zbl 1238.03032
[38] S. McCleary and M. Rubin, Locally moving groups and the reconstruction problem for chains and circles, preprint (2005), https://arxiv.org/abs/math/0510122.
[39] J. Melleray, Polish groups and Baire category methods, Confluentes Math. 8 (2016), no. 1, 89-164. · Zbl 1364.22002
[40] G. Paolini and S. Shelah, Reconstructing structures with the strong small index property up to bi-definability, Fund. Math. 247 (2019), no. 1, 25-35. · Zbl 1480.03015
[41] C. Pech and M. Pech, On automatic homeomorphicity for transformation monoids, Monatsh. Math. 179 (2016), no. 1, 129-148. · Zbl 1419.54040
[42] C. Pech and M. Pech, Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures, MLQ Math. Log. Q. 62 (2016), no. 1-2, 25-34. · Zbl 1360.03074
[43] C. Pech and M. Pech, Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity, Algebra Universalis 79 (2018), no. 2, Paper No. 35. · Zbl 1400.03059
[44] C. Pech and M. Pech, Reconstructing the topology of the elementary self-embedding monoids of countable saturated structures, Studia Logica 106 (2018), no. 3, 595-613. · Zbl 1437.03121
[45] H. P. Rosenthal and V. G. Troitsky, Strictly semi-transitive operator algebras, J. Operator Theory 53 (2005), no. 2, 315-329. · Zbl 1114.47060
[46] M. Rubin, On the reconstruction of \aleph_0-categorical structures from their automorphism groups, Proc. Lond. Math. Soc. (3) 69 (1994), no. 2, 225-249. · Zbl 0799.03037
[47] M. Rubin and J. Maissel, Reconstruction theorems for semigroups of functions which contain all transpositions of a set and for clones with the same property, preprint (2016), https://arxiv.org/abs/1606.06417.
[48] F. M. Schneider, A uniform Birkhoff theorem, Algebra Universalis 78 (2017), no. 3, 337-354. · Zbl 1421.03014
[49] J. K. Truss, Generic automorphisms of homogeneous structures, Proc. Lond. Math. Soc. (3) 65 (1992), no. 1, 121-141. · Zbl 0723.20001
[50] J. K. Truss and E. Vargas-García, Reconstructing the topology on monoids and polymorphism clones of reducts of the rationals, Contrib. Discrete Math. 16 (2021), no. 2, 1-22. · Zbl 1482.08001
[51] S. Willard, General Topology, Dover, Mineola, 2004. · Zbl 1052.54001
[52] D. Zhuk, A proof of CSP dichotomy conjecture, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Society, Los Alamitos (2017), 331-342.
[53] D. Zhuk, An algorithm for constraint satisfaction problem, 2017 IEEE 47th International Symposium on Multiple-Valued Logic—ISMVL 2017, IEEE Computer Society, Los Alamitos (2017), 1-6.
[54] D. Zhuk, A proof of the CSP dichotomy conjecture, J. ACM 67 (2020), no. 5, Article ID 30. · Zbl 1491.68128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.