Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Anthony Widjaja Lin

LFCS Seminar: Anthony Widjaja Lin

— filed under:

Tractability Results for Automata on (Vectors of) Numbers with Applications

What
  • LFCS Seminar
When Jan 27, 2012
from 02:00 PM to 03:00 PM
Where IF 4.31-33
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 well-known 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 context-free 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 context-free 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).

Document Actions