16 citations · 35 across the 16 of their papers we have counts for
Showing 2019 · cs.FLShow all
2 papers · 2 filters
cs.FL2019
Re-pairing brackets
Dmitry Chistikov, Mikhail Vyalyi
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can pair any opening bracket with any closing bracket to…
cs.FL2019★ 1 cited
An application of communication complexity, Kolmogorov complexity and extremal combinatorics to parity games
Alexander Kozachinskiy, Mikhail Vyalyi
So-called separation automata are in the core of several recently invented quasi-polynomial time algorithms for parity games. An explicit -state separation automaton implies an…