Workshop Speakers:

A seminal Schuetzenberger theorem says that for word languages definability in first-order logic is the same as being recognised by an aperiodic semigroup. This beautiful logic-algebra connection has inspired much research. One particularly fascinating -- but also hard -- direction is the generalisation to trees. In my talk, I will discuss some of the progress that has been made in this direction, including work by Zoltan. Some of the big problems, however, remain open, including the question: is there an algorithm that decides if a regular tree language can be defined in first-order logic?

As a complementary chapter to Zoltan Esik's fundamental work on (algebraic) iteration theories we review results and problems on a very natural logic that captures iteration: Monadic transitive closure logic (MTC). MTC is the extension of first-order logic by the rule that one can proceed from a formula F(z,z') to F*(x,y) which expresses that a sequence exists from x to y such that each step is in accordance with F. So MTC is a very natural framework for expressing reachability properties. First we recall the expressive equivalence between MTC and regular expressions on finite words, a result that has attracted less attention than the corresponding fact on monadic second-order logic MSO; as an addendum we discuss the relation between quantifiers and algebraic operations such as concatenation. Then we address the much more difficult issue of the expressive power of MTC over trees (where MTC is known to be strictly weaker than MSO) and over graphs (where some intriguing questions remain open).

I will talk about results obtained jointly with Zoltan Esik (published in 2005 and 2010) on an algebraic framework for recognizing languages of finite trees, and its applications to the characterization of first-order definability. This algebraic framework draws on universal algebra as well as on classical algebraic automata theory. The objective, to show that one can decide first-order definability, was not reached (and remains open to this date), but I hope that my presentation will show one direction of the inspiration that Zoltan brought to research.

Organisers