Algebra and Logic Seminar - 8/10/2014

Wednesday, 8 October 2014, 3:30 p.m.

Lecturer: Alan Cain (CMA/FCT-UNL)

Title: "Automatic presentations for algebraic and relational structures"

Local: Room 1.13, Edifício VII
Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: An automatic presentation (also called an FA-presentation) is a description of a relational structure using regular languages. The concept an FA-presentation arose in computer science, to fulfil a 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, with particular attention to connections with decidability and logic. I will then discuss work with Nik Ruskuc (Univ. of St Andrews, UK) and Richard Thomas (Univ. of Leicester, UK) on algebraic and combinatorial structures that admit automatic presentations or unary automatic presentations. The main focus will be on results that characterize the structures of some type (for example, groups, trees, or partially ordered sets) that admit automatic presentations.