Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
8 апреля 2024 г. 18:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
 


Punctual structures, automatic structures and index sets. Part 2

N. A. Bazhenova, I. Sh. Kalimullinb

a Novosibirsk State University
b Kazan (Volga Region) Federal University
Видеозаписи:
MP4 1,242.1 Mb
MP4 772.8 Mb
Дополнительные материалы:
Adobe PDF 170.6 Kb

Количество просмотров:
Эта страница:137
Видеофайлы:66
Материалы:14



Аннотация: A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. An interrelated notion is punctual structures where domain, functions, and relations belong to some fixed subrecursive class. In the first part we will give a sketch of the proof showing that the index set of punctually presentable computable structures is $\Sigma^1_1$ complete. In the second part we will show how to expand the idea for the $\Sigma^1_1$ completeness of the index set of automatically presentable computable structures. It follows from the last result that there is no natural way to tell whether a structure has, or does not have, an automatic presentation, answering the question of Khoussainov and Nerode.

Дополнительные материалы: 2024_04_08_bazhenov_kalimullin.pdf (170.6 Kb)

Язык доклада: английский
Цикл докладов
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024