Primitive recursive and automatic structures

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.