Geodesic
HKSS-completeness of modal algebras
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 2, pp. 923-930.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper studies computability-theoretic properties of countable modal algebras. We prove that the class of modal algebras is complete in the sense of the work of Hirschfeldt, Khoussainov, Shore, and Slinko. This answers an open question of Bazhenov [Stud. Log., 104 (2016), 1083–1097]. The result implies that every degree spectrum and every categoricity spectrum can be realized by a suitable modal algebra.
Keywords: computable structure, Boolean algebra with operators, degree spectrum, categoricity spectrum, first-order definability.
Mots-clés : modal algebra, computable dimension 
@article{SEMR_2021_18_2_a5,
     author = {N. Bazhenov},
     title = {HKSS-completeness of modal algebras},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {923--930},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_2_a5/}
}
TY  - JOUR
AU  - N. Bazhenov
TI  - HKSS-completeness of modal algebras
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 923
EP  - 930
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_2_a5/
LA  - en
ID  - SEMR_2021_18_2_a5
ER  - 
%0 Journal Article
%A N. Bazhenov
%T HKSS-completeness of modal algebras
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 923-930
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_2_a5/
%G en
%F SEMR_2021_18_2_a5
N. Bazhenov. HKSS-completeness of modal algebras. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 2, pp. 923-930. http://geodesic.mathdoc.fr/item/SEMR_2021_18_2_a5/

[1] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[2] A. Montalbán, “Computability theoretic classifications for classes of structures”, Proceedings of the International Congress of Mathematicians (Seoul, 2014), v. II, eds. S. Y. Jang, Y. R. Kim, D.-W. Lee, I. Yie, Kyung Moon Sa, Seoul, 2014, 79–101 | MR | Zbl

[3] M. Harrison-Trainor, A. Melnikov, R. Miller, A. Montalbán, “Computable functors and effective interpretability”, J. Symb. Log., 82:1 (2017), 77–97 | DOI | MR | Zbl

[4] R. Miller, B. Poonen, H. Schoutens, A. Shlapentokh, “A computable functor from graphs to fields”, J. Symb. Log., 83:1 (2018), 326–348 | DOI | MR | Zbl

[5] N. T. Kogabaev, “The theory of projective planes is complete with respect to degree spectra and effective dimensions”, Algebra Logic, 54:5 (2015), 387–407 | DOI | MR | Zbl

[6] D. A. Tussupov, “Isomorphisms and algorithmic properties of structures with two equivalences”, Algebra Logic, 55:1 (2016), 50–57 | DOI | MR | Zbl

[7] M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra Logic, 55:4 (2016), 306–314 | DOI | MR | Zbl

[8] N. Bazhenov, “Computable contact algebras”, Fundam. Inform., 167:4 (2019), 257–269 | DOI | MR | Zbl

[9] S. S. Goncharov, V. D. Dzgoev, “Autostability of models”, Algebra Logic, 19:1 (1980), 28–37 | DOI | MR | Zbl

[10] B. Khoussainov, T. Kowalski, “Computable isomorphisms of Boolean algebras with operators”, Stud. Log., 100:3 (2012), 481–496 | DOI | MR | Zbl

[11] N. Bazhenov, “Categoricity spectra for polymodal algebras”, Stud. Log., 104:6 (2016), 1083–1097 | DOI | MR | Zbl

[12] E. B. Fokina, I. Kalimullin, R. Miller, “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67 | DOI | MR | Zbl

[13] C. J. Ash, J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Logic Found. Math., 144, Elsevier Science B. V., Amsterdam, 2000 | MR | Zbl

[14] Yu. L. Ershov, S. S. Goncharov, Constructive models, Consultants Bureau, New York, 2000 | MR | Zbl

[15] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51:4 (1986), 1034–1042 | DOI | Zbl

[16] M. Kracht, F. Wolter, “Normal monomodal logics can simulate all others”, J. Symb. Log., 64:1 (1999), 99–138 | DOI | MR | Zbl

[17] R. G. Downey, A. M. Kach, S. Lempp, A. E. M. Lewis-Pye, A. Montalbán, D. D. Turetsky, “The complexity of computable categoricity”, Adv. Math., 268 (2015), 423–466 | DOI | MR | Zbl