Standard

Computable Contact Algebras. / Bazhenov, Nikolay.

In: Fundamenta Informaticae, Vol. 167, No. 4, 01.01.2019, p. 257-269.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, N 2019, 'Computable Contact Algebras', Fundamenta Informaticae, vol. 167, no. 4, pp. 257-269. https://doi.org/10.3233/FI-2019-1817

APA

Bazhenov, N. (2019). Computable Contact Algebras. Fundamenta Informaticae, 167(4), 257-269. https://doi.org/10.3233/FI-2019-1817

Vancouver

Bazhenov N. Computable Contact Algebras. Fundamenta Informaticae. 2019 Jan 1;167(4):257-269. doi: 10.3233/FI-2019-1817

Author

Bazhenov, Nikolay. / Computable Contact Algebras. In: Fundamenta Informaticae. 2019 ; Vol. 167, No. 4. pp. 257-269.

BibTeX

@article{aea3607293f44c9782efd40403f53a8d,
title = "Computable Contact Algebras",
abstract = "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 ∏3-theory of contact algebras is hereditarily undecidable. This is a refinement of the result of Koppelberg, D{\"u}ntsch, and Winter [Algebra Univers., 68 (2012), 353-366].",
keywords = "Boolean algebra, computable dimension, computable structure, Contact algebra, contact relation, degree spectrum, elementary definability, hereditary undecidability, region-based theory of space, PROXIMITY APPROACH, DEGREE SPECTRA, SPACE, REGION-BASED THEORY",
author = "Nikolay Bazhenov",
year = "2019",
month = jan,
day = "1",
doi = "10.3233/FI-2019-1817",
language = "English",
volume = "167",
pages = "257--269",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "4",

}

RIS

TY - JOUR

T1 - Computable Contact Algebras

AU - Bazhenov, Nikolay

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 ∏3-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].

AB - 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 ∏3-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].

KW - Boolean algebra

KW - computable dimension

KW - computable structure

KW - Contact algebra

KW - contact relation

KW - degree spectrum

KW - elementary definability

KW - hereditary undecidability

KW - region-based theory of space

KW - PROXIMITY APPROACH

KW - DEGREE SPECTRA

KW - SPACE

KW - REGION-BASED THEORY

UR - http://www.scopus.com/inward/record.url?scp=85069232640&partnerID=8YFLogxK

U2 - 10.3233/FI-2019-1817

DO - 10.3233/FI-2019-1817

M3 - Article

AN - SCOPUS:85069232640

VL - 167

SP - 257

EP - 269

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -

ID: 20886402