Automatic presentations for algebraic and combinatorial structures
 
 
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.
Date:  2013-03-20
Start Time:   15:00
Speaker:  Alan J. Cain (Univ. Porto)
Institution:  Universidade do Porto
Place:  Room 5.5 (DMUC)
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support