Towards weak bases of minimal relational clones on all finite sets
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
Summer School on General Algebra and Ordered Sets 2023
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
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.
[1] M. Behrisch, M. Hermann, S. Mengel, G. Salzer. Minimal distance of propositional models, Theory Comput. Syst. 63(6) 1131?1184(2019). DOI 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). DOI 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
[4] M. Behrisch. Weak bases for maximal clones, in IEEE 53rd ISMVL 2023, Matsue, Japan, May 22?24, 2023, 128?133(2023). DOI 10.1109/ISMVL57333.2023.00034
[5] M. Couceiro, L. Haddad, V. Lagerkvist. Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: a survey, in IEEE 49th ISMVL 2019, Fredericton, Canada, May 21?23, 2019, 170?175(2019). DOI 10.1109/ISMVL.2019.00037
[6] P. Jonsson, V. Lagerkvist, G. Nordh, B. Zanuttini. Strong partial clones and the time complexity of SAT problems, J. Comput. System Sci. 84 52?78(2017). DOI 10.1016/j.jcss.2016.07.008
[7] V. Lagerkvist. Weak bases of Boolean co-clones, Inform. Process. Lett. 114(9) 462?468(2014). DOI 10.1016/j.ipl.2014.03.011
[8] V. Lagerkvist, B. Roy. Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, J. Comput. System Sci. 117 23?39(2021). DOI 10.1016/j.jcss.2020.10.004
Sprache der Kurzfassung:
Englisch
Englischer Vortragstitel:
Towards weak bases of minimal relational clones on all finite sets
Forschungs-