LFCS Seminar: Anthony Widjaja Lin
Tractability Results for Automata on (Vectors of) Numbers with Applications
What 


When 
Jan 27, 2012 from 02:00 PM to 03:00 PM 
Where  IF 4.3133 
Add event to calendar 
vCal iCal 
Automata theory usually deals with automata on objects with ordering (e.g. words, trees). In 1961, Parikh proposed a setting to study automata on vectors of numbers by forgetting the ordering in the original objects (i.e. only keeping track of letter counts). These are now commonly known as Parikh's images of (languages) of words/trees. Parikh showed that the picture on the expressive power of wellknown automata models is completely different than the case with ordering (albeit still pleasing). He proved a fundamental theorem (a.k.a. Parikh's Theorem) stating that the Parikh images of contextfree languages and regular languages coincide with semilinear sets.
In this talk, I will give results concerning descriptional and computational complexity of Parikh's Theorem. We will show that
Parikh images of contextfree languages are exponentially more succinct than Parikh images of languages of finite automata. We will also prove a normal form theorem for Parikh images of regular languages, which is obtained via convex geometry. This normal form theorem gives a kind of tractability results in the case when the alphabet size is fixed. Finally, we will discuss applications of this result in several different areas of theoretical computer science (e.g. integer programming, verification, and graph databases).