Computably separable models

N. Kh. Kasymov ; F. N. Ibragimov

Contemporary Mathematics. Fundamental Directions, Contemporary problems in mathematics and physics, Tome 64 (2018) no. 4, pp. 682-705.

Résumé

We state fundamental results of structural theory of computably separable models and consider applications of this theory to solution of some actual problems of the theory of effective linear orders and theoretical informatics.

Bibliographie

[1] S. S. Goncharov, “Data models and languages for their description”, Comput. Syst. Proc. Inst. Math. Sib. Branch Acad. Sci. USSR, 107, 1985, 52–70 (in Russian) | Zbl

[2] S. S. Goncharov, Yu. L. Ershov, Constructive Models, Nauchnaya kniga, Novosibirsk, 1999 (in Russian)

[3] Yu. L. Ershov, Numeration Theory, Nauka, Moscow, 1977 (in Russian)

[4] Yu. L. Ershov, “Solvability Problems and Constructive Models”, Nauka, Moscow, 1980 (in Russian)

[5] N. Kh. Kasymov, “On algebras with finitely approximable positively representable enrichments”, Algebra Logic, 26:6 (1987), 715–730 (in Russian) | MR | Zbl

[6] N. Kh. Kasymov, “Positive algebras with congruences of finite index”, Algebra Logic, 30:3 (1991), 293–305 (in Russian) | MR | Zbl

[7] N. Kh. Kasymov, “Positive algebras with countable congruence lattices”, Algebra Logic, 31:1 (1992), 21–37 (in Russian) | MR | Zbl

[8] N. Kh. Kasymov, “Positive algebras with Noetherian congruence lattices”, Siberian Math. J., 33:2 (1992), 181–185 (in Russian) | MR | Zbl

[9] N. Kh. Kasymov, “On the number of congruences of algebras over simple sets”, Math. Notes, 52:2 (1992), 150–152 (in Russian) | MR | Zbl

[10] N. Kh. Kasymov, “Homomorphisms onto negative algebras”, Algebra Logic, 31:2 (1992), 132–144 (in Russian) | MR | Zbl

[11] N. Kh. Kasymov, “Separation axioms and partitions of the set of natural numbers”, Siberian Math. J., 34:3 (1993), 81–85 (in Russian) | MR | Zbl

[12] N. Kh. Kasymov, “Enumerated algebras with uniformly recursive-separable classes”, Siberian Math. J., 34:5 (1993), 85–102 (in Russian) | MR | Zbl

[13] N. Kh. Kasymov, “Algebras over negative equivalences”, Algebra Logic, 33:1 (1994), 76–80 (in Russian) | MR | Zbl

[14] N. Kh. Kasymov, “Recursively separable enumerated algebras”, Progr. Math. Sci., 51:3 (1996), 145–176 (in Russian) | DOI | MR | Zbl

[15] N. Kh. Kasymov, “On computability of negative representations of the Goncharov standard model of arithmetics”, Int. Conf. “Algebra, Analysis and Quantum Probability”, Proc., Tashkent, 2015, 117–119 (in Russian)

[16] N. Kh. Kasymov, “Homomorphisms onto effectively separable algebras”, Siberian Math. J., 57:1 (2016), 47–66 (in Russian) | DOI | MR | Zbl

[17] N. Kh. Kasymov, R. N. Dadazhanov, “Negative dense linear orders”, Siberian Math. J., 58:6 (2017), 1306–1331 (in Russian) | DOI | MR | Zbl

[18] N. Kh. Kasymov, F. N. Ibragimov, “Structure characterization of the recursively separable models”, Rep. Acad. Sci. Resp. Uzbekistan, 1998, no. 11, 14–16 (in Russian)

[19] N. Kh. Kasymov, A. S. Morozov, “Definability of linear orders over negative equivalences”, Algebra Logic, 55:1 (2016), 37–57 (in Russian) | DOI | MR | Zbl

[20] A. I. Mal'tsev, “To general theory of algebraic systems”, Math. Digest, 35(77):1 (1954), 3–20 (in Russian) | MR | Zbl

[21] A. I. Mal'tsev, “Constructive algebras. I”, Progr. Math. Sci., 16:3 (1961), 3–60 (in Russian) | MR | Zbl

[22] A. I. Mal'tsev, “Positive and negative numerations”, Rep. Acad. Sci. USSR, 160:2 (1965), 278–280 (in Russian) | MR | Zbl

[23] A. I. Mal'tsev, “Algebraic Systems”, Nauka, Moscow, 1970 (in Russian)

[24] A. I. Mal'tsev, “Algorithms and Recursive Functions”, Nauka, Moscow, 1986 (in Russian)

[25] P. Martin-Lef, Sketches on Constructive Mathematics, Mir, Moscow, 1975 (in Russian)

[26] V. A. Uspenskiy, “On computable operations”, Rep. Acad. Sci. USSR, 103:5 (1955), 773–776 (in Russian)

[27] V. A. Uspenskiy, “Systems of countable sets and their numerations”, Rep. Acad. Sci. USSR, 105:6 (1955), 1155–1158 (in Russian)

[28] Baur W., “Rekursive algebren mit kettenbedingungen”, Z. Math. Logik Grundl. Math., 20 (1974), 37–46 | DOI | MR | Zbl

[29] Baur W., “Uber recursive strukturen”, Invent. Math., 23:2 (1974), 89–95 | DOI | MR | Zbl

[30] Bergstra J. A., Tucker J. V., “A characterization of computable data types by means of a finite, equational specification method”, Lecture Notes in Comput. Sci., 85, 1980, 76–90 | DOI | MR | Zbl

[31] Broy M., Dosch W., Partsch H., Pepper P., Wirsing M., “Existential quantifiers in abstract data types”, Lecture Notes in Comput. Sci., 71, 1979, 73–81 | DOI | MR

[32] Feiner L., “Hierarchies of Boolean algebras”, J. Symb. Logic, 35:2 (1970), 365–373 | DOI | MR

[33] Fokina E. B., Khoussainov B., Semukhin P. D., “Linear orders realized by C. E. equivalence relations”, J. Symb. Logic, 81:2 (2016), 463–482 | DOI | MR | Zbl

[34] Kamin S., “Some definitions for algebraic data type specifications”, SIGPLAN Notes, 14:3 (1979), 28–37 | DOI

[35] Khoussainov B., Slaman T., Semukhin P., “$\prod_1^0$-presentasions of algebras”, Arch. Math. Logic, 45:6 (2006), 769–781 | DOI | MR | Zbl

[36] Morozov A. S., Truss J. K., “On computable automorphisms of the rational numbers”, J. Symb. Logic, 66:3 (2001), 1458–1470 | DOI | MR | Zbl

[37] Nerode A., “General topology and partial recursive functionals”, Talks Cornell Summ. Inst. Symb. Log., Cornell, 1957, 247–251