# 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*14n*^{2}, 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 {

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