Videolibrary
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Video Library
Archive
Most viewed videos

Search
RSS
New in collection






Adian 90: Conference on Mathematical Logic, Algebra, and Computation
July 7, 2021 11:30–12:15, Moscow, Steklov Mathematical Institute of RAS (Moscow) and online in Zoom
 


Primitive recursive and automatic structures

N. A. Bazhenova, I. Sh. Kalimullinb

a Sobolev Institute of Mathematics, Novosibirsk
b Kazan (Volga Region) Federal University
Video records:
MP4 858.5 Mb

Number of views:
This page:189
Video files:38



Abstract: We will discuss the recent progress in the studies of sub-recursive presentations for algebraic structures. The key notion in these developments is the notion of a punctual structure, introduced in [1]. A countably infinite structure $S$ is punctual if the domain of $S$ is the set of natural numbers, and the signature functions and relations of $S$ are uniformly primitive recursive.
The theory of punctual structures blends feasible computations with the methods of constructive model theory. The developed techniques can be used to derive interesting unexpected results. In particular, in a joint work with Harrison-Trainor, Melnikov, and Ng [2], we prove that the class of automata-presentable structures (in the sense of Khoussainov and Nerode) does not admit a simple syntactic characterization. A similar result holds for the structures with a polynomial-time computable presentation. We will discuss in detail these and other results.

Language: English

References
  1. I. Kalimullin, A. Melnikov, and K. M. Ng, “Algebraic structures computable without delay”, Theor. Comput. Sci., 674 (2017), 73–98
  2. N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, and K. M. Ng, “Automatic and polynomial-time algebraic structures”, J. Symb. Log., 84:4 (2019), 1630–1669
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024