Behrisch, M. (2023, September 3). Towards weak bases of minimal relational clones on all finite sets [Presentation]. Summer School on General Algebra and Ordered Sets 2023, Stará Lesná, Slovakia. https://doi.org/10.34726/4846
Weak bases of relational clones have been used in the past as a theoretical tool to establish more fine-grained complexity analyses of computational problems, see, e.g., [6, 1, 5, 8, 3]. For the Boolean case weak bases have been determined by Lagerkvist in [7], see also the discussion in [2]. The quest for weak bases on sets of larger size was begun in [4] with a study of weak bases for maximal clones, resulting in a complete description for all maximal clones on a three-element set. We shall report on extending this work to all maximal clones on any finite set.
References:
[1] M. Behrisch, M. Hermann, S. Mengel, and G. Salzer. Minimal distance of propositional models, Theory Comput. Syst. 63(6) 1131–1184 (2019).
Available from https://doi.org/10.1007/s00224-018-9896-8
[2] M. Behrisch. Weak bases for Boolean relational clones revisited, in IEEE 52nd ISMVL 2022, Dallas, TX, May 18–20, 2022, 68–73 (2022).
Available from https://doi.org/10.1109/ISMVL52857.2022.00017
[3] M. Behrisch. On weak bases for Boolean relational clones and reductions for computational problems, To appear in Journal of Applied Logics – IfCoLog Journal (2023).
[4] M. Behrisch. Weak bases for maximal clones, in IEEE 53rd ISMVL 2023, Matsue, Shimane, Japan, May 22–24, 2023, 128–133 (2023).
Available from https://doi.org/10.1109/ISMVL57333.2023.00034
[5] M. Couceiro, L. Haddad, and V. Lagerkvist. Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: a survey, in IEEE 49th ISMVL 2019, Fredericton, New Brunswick, Canada, May 21–23, 2019, 170–175 (2019).
Available from https://doi.org/10.1109/ISMVL.2019.00037
[6] P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. Strong partial clones and the time complexity of SAT problems, J. Comput. System Sci. 84 52–78 (2017).
Available from https://doi.org/10.1016/j.jcss.2016.07.008
[7] V. Lagerkvist. Weak bases of Boolean co-clones, Inform. Process. Lett. 114(9) 462–468 (2014).
Available from https://doi.org/10.1016/j.ipl.2014.03.011
[8] V. Lagerkvist and B. Roy. Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, J. Comput. System Sci. 117 23–39 (2021).
Available from https://doi.org/10.1016/j.jcss.2020.10.004
en
Project (external):
Austrian Science Fund (FWF)
-
Project ID:
P 33878
-
Research Areas:
Logic and Computation: 60% Computer Science Foundations: 40%