22.15 Universal Positivity Set

By Edon Kelmendi

Can one construct an infinite recursively enumerable set \(S\subset \mathbb{N}\), for which one can decide: given any linear recurrence sequence \((u_n)\), whether \(\exists n\in S\), s.t. \(u_n<0\) ? < p>

In other words: is there a set of indices for which the positivity problem is decidable?

The analogous question where \(u_n<0\) is replaced by \(u_n="0\)" has a positive answer for simple sequences; luca, ouaknine and worrell have constructed such set explicitly (called the universal skolem set). < p>

22.16 Is Markov reachability problem Skolem-Hard for Ergodic Markov chains?

By S. Akshay

Given a Markov chain \(M\), an initial distribution \(u\) and target distribution \(v\), and a rational number \(r\), consider the problem of checking if there exists an \(n\) such that \(u M^n v =r\). This problem is known to be as hard as the Skolem problem of LRS. However, the reduction requires the Markov chain to be non-ergodic, in particular it is reducible and periodic. If we now assume the Markov chain to be irreducible and aperiodic (a natural assumption that is often used since forever!), does it remain hard?! Both yes or no answers would be very interesting and have consequences to model checking of probabilistic linear dynamical systems.

22.17 Eventual non-negativity of Matrices

By S. Akshay

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

By Benjamin Kaminski

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.

Continue Reading →

22.19 Membership in Reversed Partially-Ordered Automata

By Michaël Cadilhac

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\(⁰\)."

Continue Reading →

22.10 The Parity Language

By Corentin Barloy

We study a combinatorial property of the Parity language (the set of binary words with an even number of 1s). Let \(n\) be a word size, \(\textit{Parity}_n\) be the subset of Parity of words of length \(n\), \(\overline{\textit{Parity}}_n\) be the subset of the complement of Parity of words of length \(n\).

For two subset \(A\) and \(B\), we say that \(B\) has a limit in \(A\) if there is a word \(u\in A\) such that for every position \(i\) there exists a word \(v\) in \(B\) that matches \(u\) on that position (ie. \(u_i = v_i\)).

Continue Reading →

22.9 Constructive Zermelo's Problem

By Vincent Michielini

A choice function over a set \(E\) is a function \(f\) that assigns to every non-empty subset of \(E\) one of its elements (of the subset). If \(E\) is in fact a $Σ$-structure, we say that \(f\) is regular if it can be defined by an MSO[\(\Sigma\)] formula \(\varphi(X,x)\), where the first variable \(X\) refers to subsets, and the second variable \(x\) i.e. refers to elements.
Naturally, if a $Σ$-structure admits a well-order which can be defined by an MSO[\(\Sigma\)] formula \(\psi(x,y)\), then one can define such a choice function \(\varphi(X,x)\) that says "I take the least element of X with respect to \(\psi\)".

The problem, originally stated in my PhD, asks if the reciprocal is true: if a $Σ$-structure \(E\) admits a regular choice function \(\varphi(X,x)\), does it necessarily also admit a regular well order \(\psi(x,y)\)?

Continue Reading →

22.8 From two-way to one-way transducers, revisited

By Nguyễn Lê Thành Dũng

A string-to-string function is said to be rational (resp. regular) when it is computed by a functional nondeterministic one-way finite-state transducer (resp. a deterministic two-way transducer). Filiot et al. [arXiv:1301.5197] have shown that it is decidable whether a given regular function is rational (the converse is always true); it was later shown that the problem is EXPSPACE-complete [Unpublished result by Ismaël Jecker, obtained by combining arXiv:1701.02502 arXiv:2101.05895].

(1) Is there a "simple" effective characterization in terms of local behaviors of two-way transducers that compute rational functions?

(2) Is it possible to extend this to infinite words?

Continue Reading →

20.10 Tighten the complexity of solving random-turn games

By Guy Avni

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

By Pierre Ohlmann

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.

Continue Reading →