|
VIDEO LIBRARY |
Adian 90: Conference on Mathematical Logic, Algebra, and Computation
|
|||
|
Primitive recursive and automatic structures N. A. Bazhenova, I. Sh. Kalimullinb a Sobolev Institute of Mathematics, Novosibirsk b Kazan (Volga Region) Federal University |
|||
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 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
|