Trading Bounds for Memory in Games with Counters

Nathanaël Fijalkow, Florian Horn, Denis Kuperberg and Michał Skrzypczak

ICALP'2015, Kyoto

The LoCo Conjecture

History and implications

Star-height Problem

Parity Index Problem

reduces to (Hashiguchi) reduces to (Colcombet and Loeding)

Boundedness of Automata with Counters (finite words)

Boundedness of Automata with Counters (infinite trees)

decidable (Hashiguchi) open! (LoCo conjecture)

Input: a regular language $L$ over finite words and $k \in \mathbb{N}$

Output: does there exist a regular expression denoting $L$ with at most $k$ nesting of stars?

$(a b^*)^* c^*$ nests two stars.

History and implications

Star-height Problem

Parity Index Problem

reduces to (Hashiguchi) reduces to (Colcombet and Loeding)

Boundedness of Automata with Counters (finite words)

Boundedness of Automata with Counters (infinite trees)

decidable (Hashiguchi) open! (LoCo conjecture)

Input: an automaton with counters $\mathcal{A}$ over finite words defining $[\mathcal{A}] : A^* \to \mathbb{N}$

Output: does there exist $N \in \mathbb{N}$ such that for all words $w \in A^*$, we have $[\mathcal{A}](w) \le N$?

History and implications

Star-height Problem

Parity Index Problem

reduces to (Hashiguchi) reduces to (Colcombet and Loeding)

Boundedness of Automata with Counters (finite words)

Boundedness of Automata with Counters (infinite trees)

decidable (Hashiguchi) open! (LoCo conjecture)

Input: a regular language $L$ over infinite trees and $[i,\ldots,j] \subseteq \mathbb{N}$

Output: does there exist a parity automaton recognizing $L$ using priorities in $[i,\ldots,j]$?

History and implications

Star-height Problem

Parity Index Problem

reduces to (Hashiguchi) reduces to (Colcombet and Loeding)

Boundedness of Automata with Counters (finite words)

Boundedness of Automata with Counters (infinite trees)

decidable (Hashiguchi) open! (LoCo conjecture)

Input: an automaton with counters $\mathcal{A}$ over infinite trees

Output: does there exist $N \in \mathbb{N}$ such that for all trees $t$, we have $[\mathcal{A}](t) \le N$?

History and implications

Star-height Problem

Parity Index Problem

reduces to (Hashiguchi) reduces to (Colcombet and Loeding)

Boundedness of Automata with Counters (finite words)

Boundedness of Automata with Counters (infinite trees)

decidable (Hashiguchi) open! (LoCo conjecture)

The LoCo Conjecture

Example: $B(N) \cap \mathrm{Buechi}(F)$

Memory Bound
$N+1$ $N$
$2$ $2N-1$
$1$ $\infty$

(Simplified) statement

There exists a trade-off function $\alpha : \mathbb{N} \to \mathbb{N}$ and a constant $m \in \mathbb{N}$ such that:

for all games,

if Eve has a strategy to ensure $B(N) \cap \mathrm{Parity}$,

then she has a strategy to ensure $B(\alpha(N)) \cap \mathrm{Parity}$ using $m$ memory states

The LoCo Conjecture

Theorem: The LoCo conjecture does not hold!

Idea: play $K$ copies of the previous game with different timelines

The LoCo Conjecture

Theorem: The LoCo conjecture holds for games played over thin tree arenas