Consider the problem: given a matrix $M$ over integers, does there exist a natural number $n$ such that $M^n$ has only non-negative entries? Is this question as hard as ultimate positivity? Note that if you consider two matrices $M, N$ and ask if there exists $n$ such that $M^n+ N^n$ has only non-negative entries, that problem is indeed equivalent to ultimate positivity, but with a single matrix, we do not know. Note also that if we ask strict positivity of entries, the single matrix case becomes easy!
22.18 Learning sequences
The following is a problem inspired from quantitative program verification. It is more vague than ``Prove or disprove whether XYZ holds'', but in turn has real applications in probabilistic verification. I posed this problem several times to several different machine learning experts and none of them were able (or interested) to help me with this problem. I now hope that the automata (learning) experts can help me out.
22.19 Membership in Reversed Partially-Ordered Automata
Let $A$ be an automaton and write, for any word $w$, $f_w$ for the function that maps any state $q$ to the state reached by reaching $w$ from $q$.
The membership problem MEMB($V$) for a class $V$ of deterministic automata is the following:
- Given: An automaton $A \in V$ and a function $f\colon Q \to Q$ from states to states
- Question: Is there a word $w$ such that $f_w = f$?
In the late 1980s, Beaudry, together with McKenzie and Thérien, studied the problem for most natural classes $V$ (e.g., groups and aperiodic automata). Quoting Beaudry, McKenzie, Thérien, 1992:
"For each $V$ aperiodic, the computational complexity of MEMB($V$) turns out to look familiar. Only five possibilities occur as $V$ ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB($V$) is either PSPACE-complete, NP-complete, P-complete or in AC$⁰$."
20.9 Memory requirements for generalized reachability games
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).
20.10 Tighten the complexity of solving random-turn games
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.
20.11 The sequential flow problem
The sequential flow problem (SFP) is a simple and natural reachability problem which was initially formalized for solving questions related to population protocols, but has independent interest. We now know that SFP is PSPACE-hard, and in EXPSPACE, but its precise complexity remains open. The following poster gives more background.
20.12 Succinctness of GFG pushdown automata
Valiant showed that the succinctness gap between deterministic and nondeterministic pushdown automata (restricted to deterministic contextfree languages) is nonrecursive, i.e., there is no computable function $f$ with the following property: If the language of a pushdown automaton $A$ is deterministic contextfree, then there is a deterministic pushdown automaton of size $f(|A|)$ recognizing $L(A)$.
Recently, good-for-games pushdown automata have been introduced, whose expressive power is strictly between the deterministic contextfree and the contextfree languages.
20.8 Good games for good-for-games automata
Given an automaton $A$, consider the following two games:
Game I. At each turn $i$:
- Adam plays a letter $a_i$
- Eve plays a transition $r_i$ over $a_i$
A play is the infinite word $w=a_0a_1\ldots$ and the sequence of transitions $r=r_0r_1\ldots$ Eve wins if either $w$ is not in $L(A)$ or $r$ is an accepting run over $w$ in $A$.
Game II. At each turn turn $i$:
- Adam plays a letter $a_i$
- Eve plays a transition $r_i$ over $a_i$
- Adam plays a pair of transitions $s_i$ and $t_i$
A play is the triple of sequences of runs $r=r_0r_1\ldots, s=s_0s_1\ldots$ and $t=t_0t_1\ldots$ Eve wins if either $r$ is an accepting run of $A$ or both $s$ and $t$ are not accepting runs of $A$.
20.1 Universality of letter-bounded CFLs
- Input: a context-free grammar for a language $L \subseteq a_1^* \dots a_n^*$ ($n$ is part of the input)
- Question: Is $L = a_1^* \dots a_n^*$?
What is the complexity of the problem?
20.2 Deterministic separability of nondeterministic timed languages
- Input: two timed languages $L$, $M$ represented as nondeterministic timed automata.
- Question: decide whether there exists a deterministic timed automaton recognising a timed language $S$ which separates $L$, $M$, in the sense that $L$ is included in $S$ and $S$ is disjoint from $M$.
The version of the problem when we fix in advance the number of clocks of the separating deterministic timed automaton is decidable. The open problem is then when the number of clocks is not fixed (and thus quantified existentially).