Computable Contact Algebras

• Autorzy: Bazhenov Nikolay

Identyfikatory

DOI

10.3233/FI-2019-1817

• Języki publikacji: EN

Abstrakty

EN

We investigate computability-theoretic properties of contact algebras. These structures were introduced by Dimov and Vakarelov in [Fundam. Inform. 74 (2006), 209-249] as an axiomatization for the region-based theory of space. We prove that the class of countable contact algebras is complete with respect to degree spectra of nontrivial structures, effective dimensions, expansion by constants, and degree spectra of relations. This means that the class of contact algebras is very rich from the computability-theoretic point of view. As an application of our result, we show that the Π₃-theory of contact algebras is hereditarily undecidable. This is a refinement of the result of Koppelberg, Düntsch, and Winter [Algebra Univers., 68 (2012), 353-366].

Słowa kluczowe

EN

contact algebra; computable structure; Boolean algebra; degree spectrum; computable dimension; contact relations; region-based theory of space; elementary definability; hereditary undecidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 4
• Strony: 257--269
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Bazhenov Nikolay

• Sobolev Institute of Mathematics, Novosibirsk, Russia and Novosibirsk State University, Novosibirsk, Russia

Bibliografia

• [1] Dimov G, Vakarelov D. Contact Algebras and Region-Based Theory of Space: A Proximity Approach-I. Fundamenta Informaticae, 2006. 74(2-3):209-249.
• [2] Dimov G, Vakarelov D. Contact Algebras and Region-Based Theory of Space: Proximity Approach - II. Fundamenta Informaticae, 2006. 74(2-3):251-282.
• [3] Khoussainov B, Kowalski T. Computable Isomorphisms of Boolean Algebras with Operators. Studia Logica, 2012. 100(3):481-496. doi:10.1007/s11225-012-9411-1.
• [4] Hirschfeldt DR, Khoussainov B, Shore RA, Slinko AM. Degree Spectra and Computable Dimensions in Algebraic Structures. Annals of Pure and Applied Logic, 2002. 115(1-3):71-113. doi:10.1016/S0168-0072(01)00087-2.
• [5] Calvert W, Cummins D, Knight JF, Miller S. Comparing Classes of Finite Structures. Algebra and Logic, 2004. 43(6):374-392. doi:10.1023/B:ALLO.0000048827.30718.2c.
• [6] Fokina EB, Friedman SD. On Σ 11 Equivalence Relations over the Natural Numbers. Mathematical Logic Quarterly, 2012. 58(1-2):113-124. doi:10.1002/malq.201020063.
• [7] Andrews U, Dushenin DI, Hill C, Knight JF, Melnikov AG. Comparing Classes of Finite Sums. Algebra and Logic, 2016. 54(6):489-501. doi:10.1007/s10469-016-9368-7.
• [8] Goncharov SS, Dzgoev VD. Autostability of Models. Algebra and Logic, 1980. 19(1):28-37. doi:10.1007/BF01669102.
• [9] Koppelberg S, Düntsch I, Winter M. Remarks on Contact Relations on Boolean Algebras. Algebra Universalis, 2012. 68(3):353-366. doi:10.1007/s00012-012-0211-2.
• [10] Ash CJ, Knight JF. Computable Structures and the Hyperarithmetical Hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. Elsevier Science B.V., Amsterdam, 2000. ISBN 0444500723.
• [11] Ershov YL, Goncharov SS. Constructive Models. Siberian School of Algebra and Logic. Kluwer Academic/Plenum Publishers, New York, 2000. ISBN 9780306110665.
• [12] Knight JF. Degrees Coded in Jumps of Orderings. The Journal of Symbolic Logic, 1986. 51(4):1034-1042. doi:10.2307/2273915.
• [13] Miller R, Poonen B, Schoutens H, Shlapentokh A. A Computable Functor from Graphs to Fields. The Journal of Symbolic Logic, 2018. 83(1):326-348. doi:10.1017/jsl.2017.50.
• [14] Kogabaev NT. The Theory of Projective Planes is Complete with Respect to Degree Spectra and Effective Dimensions. Algebra and Logic, 2015. 54(5):387-407. doi:10.1007/s10469-015-9360-7.
• [15] Tussupov DA. Isomorphisms and Algorithmic Properties of Structures with Two Equivalences. Algebra and Logic, 2016. 55(1):50-57. doi:10.1007/s10469-016-9375-8.
• [16] Marchuk MI. Index Set of Structures with Two Equivalence Relations That Are Autostable Relative to Strong Constructivizations. Algebra and Logic, 2016. 55(4):306-314. doi:10.1007/s10469-016-9400-y.
• [17] Bazhenov N. Categoricity Spectra for Polymodal Algebras. Studia Logica, 2016. 104(6):1083-1097. doi:10.1007/s11225-016-9667-y.
• [18] Goncharov SS. Countable Boolean Algebras and Decidability. Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997. ISBN 9780306110610.
• [19] Düntsch I, Li S. On the Homogeneous Countable Boolean Contact Algebra. Logic and Logical Philosophy, 2013. 22(2):213-251. doi:10.12775/LLP.2013.012.
• [20] Ershov YL. Problems of Decidability and Constructive Models. Nauka, Moscow, 1980. In Russian.
• [21] Speranski SO. A Note on Hereditarily Π01- and Σ01-Complete Sets of Sentences. Journal of Logic and Computation, 2016. 26(5):1729-1741. doi:10.1093/logcom/exu066.
• [22] Odifreddi P. Classical Recursion Theory, volume 125 of Studies in Logic and the Foundations of Mathematics. Elsevier Science B.V., Amsterdam, 1992. ISBN 0444872957.
• [23] Ershov YL, Lavrov IA, Taimanov AD, Taitslin MA. Elementary Theories. Russian Mathematical Surveys, 1965. 20(4):35-105. doi:10.1070/RM1965v020n04ABEH001188.
• [24] Nies A. Undecidable Fragments of Elementary Theories. Algebra Universalis, 1996. 35(1):8-33. doi:10.1007/BF01190967.
• [25] Bazhenov NA, Tukhbatullina RR. Constructivizability of the Boolean Algebra B(ω) with a Distinguished Automorphism. Algebra and Logic, 2012. 51(5):384-403. doi:10.1007/s10469-012-9199-0.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).