Dr. Anthony W. Lin

"Parikh Images of Regular Languages: Complexity and Applications"

30 min

Abstract:

Parikh's Theorem is a well-known result in automata theory that semilinear sets are effectively equivalent with the sets of letter-counts (a.k.a. Parikh images) of regular languages and those of context-free languages. In this talk, we are going to look at the computational and descriptional complexity aspects of Parikh's Theorem. More precisely, we will show a kind of fixed-parameter tractability results for computing Parikh images of nondeterministic finite-state automata (NFA) --- a result which doesn't hold for context-free grammars (CFG). Intuitively, the result can be construed as CFG are exponentially more succinct than NFA for describing Parikh images, even over fixed-size alphabets. The proof exploits some connections to convex geometry. The tractability result has been applied to derive tractability results in other domains: integer programming, graph databases, verification of counter systems, verification of multithreaded programs, PAC-learnability of semilinear sets, etc. I will describe some of these in the talk. (The talk is based on my LICS'10 paper).

BIOGRAPHY:

Anthony W. Lin received his PhD from University of Edinburgh's School

of Informatics in 2010 under the supervision of Leonid Libkin and the

co-supervision of Richard Mayr. His PhD thesis concerns generic and

specific techniques for infinite-state model checking. He is currently

an EPSRC Postdoctoral Research Fellow at Oxford University Department

of Computer Science. His main interests lie in developing

theoretically sound and practically applicable techniques in formal

verification (especially with applications in program analysis and more recently on language-based security),

utilizing techniques from logic and automata. He was awarded LICS 2010

Kleene Best Student Paper Award for his paper titled "Parikh Images of

Grammars: Complexity and Applications".