Automatic structures among computable structures

The aim of this project is to study the algorithmic properties of structures presentable by various types of automata. In each case such structures form a subclass of computable structures. We intend to study differences and similarities that arise when comparing the behavior of automatically presentable structures with that of all computable structures. Computable presentations of a structure illustrate the approach to represent infinite structures in a finite manner. Finite presentations of infinite structures play an important role in logic and computer science. In such cases one often requires effective semantics for structures. To achieve this one may use presentations of structures by various types of finite automata. In the first part of the proposed research project we deal with structures presentable by finite automata. The questions we pose may be considered as analogues of the corresponding questions from computable model theory. Namely, we state questions about the complexity of descriptions of classes of structures presentable by finite automata, and of various equivalence relations on classes of such structures. We also formulate questions on properties of automatically presentable structures with various important model-theoretic properties (prime, saturated, countably categorical, uncountably categorical). Furthermore, we suggest a new definition of structures presentable by pushdown automata. We state some problems that arise in this field (mostly, motivated by similar questions in computable model theory). Among others: complexity of the theory of a structure presentable by a pushdown automaton, complexity of other models of such a theory. We also aim to find a characterization of pushdown automatically presentable structures with particular algebraic and model-theoretic properties.

Many objects studied in Mathematics can be seen as structures consisting of a set and relations between elements of this set, and/or functions on the set. In this project we consider effectively given infinite structures. It mean, that there is an algorithm, or a program for a computer, which step by step outputs a larger and large piece of the structure and the corresponding relations and functions on the revealed elements. We investigate how algorithmic properties of such infinite but effectively given objects depend on their mathematical (algebraic, structural) properties.