Computable Contact Algebras

Research output: Contribution to journalArticlepeer-review

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üntsch, and Winter [Algebra Univers., 68 (2012), 353-366].

Original languageEnglish
Pages (from-to)257-269
Number of pages13
JournalFundamenta Informaticae
Volume167
Issue number4
DOIs
Publication statusPublished - 1 Jan 2019

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

Fingerprint

Dive into the research topics of 'Computable Contact Algebras'. Together they form a unique fingerprint.

Cite this