# Publications on automata with pushdown, counter, etc.

**D. Chistikov, R. Majumdar, P. Schepper. Subcubic certificates for CFL reachability.**POPL 2022. [doi]We show certificates of size

*O*(*n*^{2}), with subcubic verification algorithms, for language emptiness and non-emptiness of pushdown automata on*n*states. As a consequence, fine-grained reductions from SAT are unlikely to explain the cubic bottleneck for CFL reachability.

**D. Chistikov, M. Vyalyi. Re-pairing brackets.**LICS 2020. [WRAP] [arXiv]Conversion from OCA to Parikh-equivalent NFA requires a quasi-polynomial growth in description size. To prove this, we define and study a one-player game akin to pebbling.

**D. Chistikov, M. Cadilhac, G. Zetzsche. Rational subsets of Baumslag-Solitar groups.**ICALP 2020. [DROPS] [arXiv]Imagine a “blind” Turing machine that cannot read bits written on the tape, but can increment a decrement them. The content of the tape is interpreted as the binary expansion of a rational number, and increments and decrements simply add and subtract (possibly negative) powers of two. What sets of numbers do these machines accept?

**D. Chistikov, W. Czerwiński, P. Hofman, Mi. Pilipczuk, M. Wehar. Shortest paths in one-counter systems.**Logical Methods in Computer Science (2019). Extended version of the FoSSaCS’16 paper. [doi]Every one-counter automaton with

*n*states accepts a word of length at most*14n*^{2}, unless its language is empty.

**D. Chistikov, P. Martyugin, M. Shirmohammadi. Synchronizing automata over nested words.**Journal of Automata, Languages and Combinatorics (2019). Extended version of the FoSSaCS’16 paper. [WRAP]We propose a definition of synchronizing words for nested word automata.

**D. Chistikov, C. Haase, S. Halfon. Context-free commutative grammars with integer counters and resets.**Theoretical Computer Science (2018). Special issue for RP’14. [WRAP] [arXiv]What happens with reachability and coverability sets of VASS where counters can go negative and support reset? Also, a Π

_{2}P lower bound on the inclusion problem for linear sets.

**M. F. Atig, D. Chistikov, P. Hofman, K. Narayan Kumar, P. Saivasan, G. Zetzsche. The complexity of regular abstractions of one-counter languages.**LICS’16. [arXiv]The downward and upward closure of one-counter languages have small NFA. So does the Parikh image if the alphabet has fixed size.

**D. Chistikov, W. Czerwiński, P. Hofman, Mi. Pilipczuk, M. Wehar. Shortest paths in one-counter systems.**FoSSaCS’16. Extended version in Logical Methods in Computer Science (2019).

**D. Chistikov, P. Martyugin, M. Shirmohammadi. Synchronizing automata over nested words.**FoSSaCS’16. Extended version in Journal of Automata, Languages and Combinatorics (2019).

**D. Chistikov. Notes on counting with finite machines.**FSTTCS’14. [DROPS]How many states does a {OCA, DPDA, Turing machine} need to have in order to accept the singleton language {

*a*} ?^{n}

**D. Chistikov, R. Majumdar. Unary pushdown automata and straight-line programs.**ICALP’14. [arXiv]DPDA equivalence is in P for unary (singleton) input alphabet. This relies on algorithmics for grammar-compressed strings. Also, deciding if a CFG generates words of all lengths is Π

_{2}P-complete.

**D. Chistikov, R. Majumdar. A uniformization theorem for nested word to word transductions.**CIAA 2013.Schützenberger’s construction for the uniformization of rational relations extends to nested words.