Computable embedding of classes of algebraic structures with congruence relation

S. Vatev^a, H. Ganchev^a, I.Sh. Kalimullin^b∗

^aSofia University St. Kliment Ohridski, Sofia, 1504 Bulgaria

^bKazan Federal University, Kazan, 420008 Russia

E-mail: ^∗ikalimul@gmail.com

Received September 11, 2018

Full text PDF

Abstract

It has been shown in the paper that there is an intermediate notion of embedding, which is based on the use of non-injective presentations of algebraic structures, between the computable embedding of classes of algebraic structures based on the enumeration operators and the Turing computable embedding. The problem of equivalence of this notion to the injective computable embedding is related to the problem of effective factorization by enumeration operators.

Keywords: enumeration operator, Turing operator, algebraic structure, atomic diagram

Acknowledgments. The study was supported by the Russian Foundation for Basic Research and the National Science Fund of Bulgaria (project no. 17-51-18083). I.Sh. Kalimullin’s research was funded within the framework of the state assignment in the sphere of scientific activities (project no. 1.451.2016/1.4).

References

1. Calvert W., Cummins D., Knight J.F., Miller S. Comparing classes of finite structures. Algebra Logic, 2004, vol. 43, no. 6, pp. 374–392. doi: 10.1023/B:ALLO.0000048827.30718.2c.
2. Knight J.F., Miller S., Boom M.V. Turing computable embeddings. J. Symb. Logic, 2007, vol. 72, no. 3, pp. 901–918.
3. Rossegger D. On functors enumerating structures. Sib. Elektron. Mat. Izv., 2017, vol. 14, pp. 690–702. doi: 10.17377/semi.2017.14.059.
4. Ocasio-Gonzalez V.A. Turing computable embeddings and coding families of sets. In: Cooper S.B., Dawar A., Lowe B. (Eds.) How the World Computes. CiE 2012. Lecture Notes in Computer Science. Vol. 7318. Berlin, Heidelberg, Springer, 2012, pp. 539– 548. doi: 10.1007/978-3-642-30870-3 54.
5. Andrews U., Dushenin D.I., Hill C., Knight J.F., Melnikov A.G. Comparing classes of finite sums. Algebra Logic, 2016, vol. 54, no. 6, pp. 489–501. doi: 10.1007/s10469-0169368-7.
6. Bazhenov N. Turing computable embeddings, computable infinitary equivalence, and linear orders. In: Kari J., Manea F., Petre I. (Eds.) Unveiling Dynamics and Complexity. CiE 2017. Lecture Notes in Computer Science. Vol. 10307. Cham, Springer, 2017, pp. 141–151. doi: 10.1007/978-3-319-58741-7 15.
7. Kalimullin I.Sh. Computable embeddings of classes of structures under enumeration and turing operators. Lobachevskii J. Math., 2018, vol. 39, no. 1, pp. 84–88. doi: 10.1134/S1995080218010146.

For citation: Vatev S., Ganchev H., Kalimullin I.Sh. Computable embedding of classes of algebraic structures with congruence relation. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 4, pp. 731–737. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.