Description: |
An automatic presentation (also called an FA-presentation) is a description of a relational structures using regular languages. The concept of FA-presentations arose from computer scientists' need to extend finite model theory to infinite structures. Informally, an FA-presentation consists of a regular language of abstract representatives for the elements of the structure, such that each relation (of arity $n$, say) can be recognized by a synchronous $n$-tape automaton. An FA-presentation is unary if the language of representatives is over a 1-letter alphabet. In this talk, I will introduce and survey automatic presentations, and then discuss recent work with Nik Ruskuc on algebraic and combinatorial structures that admit FA-presentations or unary FA-presentations. In particular, I will describe a new diagrammatic technique for reasoning about unary FA-presentations, and then discuss applications to (1) new results on the closure and non-closure of certain classes of FA-presentable algebras under forming finitely generated subalgebras, and (2) new classification results for unary FA-presentable combinatorial structures of certain types, such as trees, quasi-orders, and partial orders.
|