RUS  ENG
Full version
SEMINARS

Seminars "Proof Theory" and "Logic Online Seminar"
April 8, 2024 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 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



Abstract: 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.

Language: English
Series of reports


© Steklov Math. Inst. of RAS, 2024