Skip to main content

Unary pushdown automata and grammar compression

Dmitry Chistikov ( Max Planck Institute for Software Systems, Kaiserslautern, Germany )

I am going to talk about decision problems for deterministic pushdown automata over the unary alphabet (UDPDA, for short).  UDPDA are a simple computation model; they accept exactly the unary regular languages, but can be exponentially more succinct than finite-state automata.

In the talk, I am going to explain how to complete the complexity landscape for UDPDA by showing that language emptiness (and thus universality) is P-hard, equivalence and compressed memberships are P-complete, and inclusion is coNP-complete.

Several of these results use a new translation theorem between UDPDA and straight-line programs (SLPs) over the binary alphabet.  Such SLPs - essentially context-free grammars - are a form of word compression closely related to the well-known Lempel-Ziv compression, LZ77.

Joint work with Rupak Majumdar.

Speaker biography

Dmitry Chistikov is a postdoctoral researcher at the Max Planck Institute for Software Systems in Germany, working with Rupak Majumdar.  He obtained his Candidate of Sciences (equivalent to PhD) degree at the Department of Computational Mathematics and Cybernetics of Moscow State University, where he worked with Andrey Voronenko.

The general area of his research is theoretical computer science.  In particular, he is interested in problem settings in the flavour of discrete mathematics and combinatorics.  His current research is mainly focused on automata theory and its algorithmic aspects, but he is interested in other discrete objects as well.  For instance, he is invariably attracted to matters related to Boolean functions and their representations, in the spirit of questions asked by computational learning theory and sometimes computational complexity.

Share this: