Structures Computable in Polynomial Time. II

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

8 Цитирования (Scopus)


We consider a new approach to investigating categoricity of structures computable in polynomial time. The approach is based on studying polynomially computable stable relations. It is shown that this categoricity is equivalent to the usual computable categoricity for computable Boolean algebras with computable set of atoms, and for computable linear orderings with computable set of adjacent pairs. Examples are constructed which show that this does not always hold. We establish a connection between dimensions based on computable and polynomially computable stable relations.

Язык оригиналаанглийский
Страницы (с-по)429-442
Число страниц14
ЖурналAlgebra and Logic
Номер выпуска6
СостояниеОпубликовано - 1 янв 2018

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