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.
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$?
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]$?
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$?
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) |
Memory | Bound |
$N+1$ | $N$ |
$2$ | $2N-1$ |
$1$ | $\infty$ |
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
Idea: play $K$ copies of the previous game with different timelines