Computable Contact Algebras

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование


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].

Язык оригиналаанглийский
Страницы (с-по)257-269
Число страниц13
ЖурналFundamenta Informaticae
Номер выпуска4
СостояниеОпубликовано - 1 янв 2019


Подробные сведения о темах исследования «Computable Contact Algebras». Вместе они формируют уникальный семантический отпечаток (fingerprint).