Consider a DFA $A$ together with $d$ pairs off counters $(x_1,y_1),\dots,(x_d,y_d)$. Each transition of $A$ is labelled with an update function for all counters. The update functions for the x-counters are $id:n\rightarrow n$ and $++ : n\rightarrow n+1$. The update function for the y-counters are $id:n\rightarrow n$, $\times 2:n\rightarrow 2n$ and $\times 2+1:n\rightarrow 2n+1$. An accepting configuration is a configuration in which we are in an accepting state and all the counter pairs have the same value, i.e. $x_1=y_1,\dots,x_d=y_d$.

Question: is the emptiness problem for this class of automata decidable?

A vector addition system is a finite set of vectors $V = \{ v_1,v_2,\ldots,v_n \} \in \mathbb{Z}^d$ with $d \in \mathbb{N}$. Given two positions $s,t \in \mathbb{N}^d$, a run of $V$ from $s$ to $t$ is a sequence $s = c_0, c_1, c_2, \ldots, c_m = t$ of positions $c_i \in \mathbb{N}^d$ where each position is obtained by adding an element of $V$ to the previous one: $c_{i} - c_{i-1} \in V$ for every $1 \leq i \leq m$. Is the following statement correct:

Conjecture: For every vector addition system $V$, there exists a constant $C_V$ such that for every pair of positions $s$ and $t$, if there exists at least one run of $V$ from $s$ to $t$, one of these runs has a length smaller than $C_V \cdot \big(||s|| + ||t|| \big)$.

A random-turn game is a graph game which is parameterized by a ratio $p$. In each turn, we throw a coin with bias $p$ to determine which player moves the token. Formally, random-turn games are a special case of stochastic games. We are interested in finding, for each vertex, the "value" of the game, which is the optimal probability with which Player 1 can guarantee winning. Stated as a decision problem: decide whether the value is greater than 0.5. The problem is known to be in NP and coNP (again, a special case of stochastic games), but not known to be in P nor to be as hard as stochastic games (or any other problem in NP and coNP).

My interest in random-turn games stems from the fact that they are equivalent to bidding games: a solution to a random-turn game can be used to construct optimal bidding strategies in a bidding game. Moreover, random-turn games have been extensively studied in the combinatorics community.

Given a regular language $L$ (on finite words), we consider the condition over omega-words "having a prefix in $L$". We want to characterize the optimal memory requirements for this condition over finite arenas. The memory requirements for the opponent were characterized by Colcombet, Fijalkow and Horn in the 2012 paper "Playing Safe" (that also holds for infinite arenas).

Consider the model introduced in this problem. It is mentioned therein that equivalence is undecidable for that model. We ask what further restrictions we can impose on that model to make equivalence decidable.

If the $\min$ operation is removed, then this is known to lead to decidability [Alur et al.'13]. But as soon as we have $\min$, we don't know of a model with decidable equivalence.

We conjecture that it is decidable is the CRA is ordered; this means that the registers can be ordered, say $x_1, x_2, \ldots, x_n$, such that for all updates, $x_i$ is only updated with registers $x_j$ for $j \geq i$.