An automatic presentation or FA-presentation is a description of a relational structure using regula
An automatic presentation or FA-presentation is a description of a relational structure using regular languages. Informally, in an FA-presentation, elements of the structure are represented by a regular language of abstract representatives, and each relation (of arity $n$, say) can be recognized by a synchronous $n$-tape automaton. The concept arose from computer scientists' need to extend finite model theory to infinite structures. A particular research problem has been to try to characterize the structures of some species (say, groups, rings, or boolean algebras) that admit FA-presentations.
Since any FA-presentable structure admits an FA-presentation where the regular language of representatives is over a 2-letter alphabet, a related problem is to characterize the structures that admit FA-presentations over a 1-letter alphabet, so-called `unary'
FA-presentations.
This talk will describe a new diagrammatic method for reasoning about unary FA-presentations, and how it can be applied to characterize unary FA-presentable binary relations, quasi-orders, partial orders, tournaments, directed trees and forests, undirected trees and forests, and the orbit structures of unary FA-presentable mappings, injections, surjections, and bijections. This is joint work with Nik Ruskuc.
Date and Venue
Start Date
Venue
Room M007 of the Mathematics Department, FCUP
Speaker
Alan Cain
(CMUP)
(CMUP)
Area
Semigroups, Automata and Languages