Аннотация
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 |