Skip to main content Skip to navigation

Publications on descriptional complexity

  • 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, 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, C. Haase. On the complexity of quantified integer programming. ICALP 2017. [DROPS]

    If some variables in integer programs are quantified universally instead of existentially, then the decision problem becomes complete for the k-th level of the polynomial hierarchy, assuming k quantifier blocks.

  • D. Chistikov, S. Iván, A. Lubiw, J. Shallit. Fractional coverings, greedy coverings, and rectifier networks. STACS 2017. [DROPS] [arXiv]

    LP relaxations of integer programs encoding set cover are useful for minimization of regular expressions and OR-circuits.

  • D. Chistikov, C. Haase. The taming of the semi-linear set. ICALP’16. [DROPS]

    To measure how semilinear sets “grow” under Boolean operations, we keep track of the maximum norm of generators.

  • D. Chistikov, R. Majumdar, F. Niksic. Hitting families of schedules for asynchronous programs. CAV’16. [arXiv]

    We propose a simple generalization of partial order dimension, with an application in software testing.

  • 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. 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.