Re-pairing brackets

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can \emph{pair} any opening bracket with any closing bracket to its right, \emph{erasing} them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its \emph{width:} the maximum number of nonempty segments of symbols (separated by blank space) seen during the play. For various initial sequences, we prove upper and lower bounds on the minimum width sufficient for re-pairing. (In particular, the sequence associated with the complete binary tree of height admits a strategy of width sub-exponential in .) Our two key contributions are (1) lower bounds on the width and (2) their application in automata theory: quasi-polynomial lower bounds on the translation from one-counter automata to Parikh-equivalent nondeterministic finite automata. The latter result answers a question by Atig et al. (LICS 2016). Joint work with Mikhail Vyalyi (Higher School of Economics, Moscow, Russia).

Authors

• Dmitry Chistikov.

Keywords

No keywords are indexed for this paper.