Speaker
Description
In the talk we consider subrecursive algebraic structures. One of the key notions in this direction is the notion of a punctual structure introduced by Kalimullin, Melnikov, and Ng (2017). An infinite algebraic structure S is punctual if the domain of S is equal to the set of natural numbers, and the signature functions and relations of the structure S are primitive recursive. The methods of punctual structure theory found their applications not only in the classical constructive model theory, but also in other areas of mathematical logic and theoretical computer science. In particular, the paper "Automatic and polynomial-time algebraic structures" (2019) proves that the class of automatic structures (in the sense of Khoussainov and Nerode) does not admit a simple syntactic characterization (even within the framework of infinitary logic). In the talk, we discuss recent results on punctual structure theory, and its applications to the theory of numberings and equivalence relations. The talk is based on joint works with Harrison-Trainor, Kalimullin, Melnikov, and Ng.
