Structures Computable in Polynomial Time. I

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

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

Аннотация

It is proved that every computable locally finite structure with finitely many functions has a presentation computable in polynomial time. Furthermore, a structure computable in polynomial time is polynomially categorical iff it is finite. If a structure is computable in polynomial time and locally finite then it is weakly polynomially categorical (i.e., categorical with respect to primitive recursive isomorphisms) iff it is finite.

Язык оригиналаанглийский
Страницы (с-по)421-435
Число страниц15
ЖурналAlgebra and Logic
Том55
Номер выпуска6
DOI
СостояниеОпубликовано - 1 янв 2017

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

Цитировать