Skip to main content Skip to navigation

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(n2), 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 14n2, 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 Π2P 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 {an} ?

  • 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 Π2P-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.