Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
April 1, 2024 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + Zoom
 


Punctual structures, automatic structures and index sets. Part 1

N. A. Bazhenova, I. Sh. Kalimullinb

a Novosibirsk State University
b Kazan (Volga Region) Federal University
Video records:
MP4 706.1 Mb
MP4 1,093.1 Mb
Supplementary materials:
Adobe PDF 298.0 Kb

Number of views:
This page:107
Video files:42
Materials:12



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.

Supplementary materials: 2024_04_01_bazhenov_kalimullin.pdf (298.0 Kb)

Language: English
Series of reports
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024