Is the following problem decidable: Given \(A\), a weighted automaton (WA) over the \((\min,+)\) semiring, answer whether \(A\) has an equivalent deterministic WA?

Remarks: The problem is equivalent when considering only automata with weights in \(\{0,1\}\) (a.k.a. distance automata). The problem is known to be decidable for polynomially-ambiguous WA. For the general case of exponentially-ambiguous WA, we don't even have any interesting examples where determinization incurs a significant state explosion.

First postulated by Hoffmann-Ostenhof (approx. 2010).

Prove the following conjecture: Every connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching.

Recently [arXiv:2206.09619], an approach for analyzing Büchi automata using graph neural networks (GNN) was proposed. The experimental analysis revealed that this GNN-based approach can predict basic properties on independent test automata quite well. Further, it seems to be able to generalize from training data in a meaningful way, as the predictions were successful on instances much larger than those provided in the training data.

Thus far, the analysis has been limited to the emptiness problem and simple properties like "does the automaton accept a word containing at least one/infinitely many \(b\) ?". My immediate question was what the limits of learning-based approaches are and whether one can identify certain properties which cannot be learned GNNs.

For every \(n \in \mathbb{N}\), the full transformation monoid \(T_n\) is the set of (total) functions from \(\{1,2,\ldots,n\}\) to \(\{1,2,\ldots,n\}\), equipped with the standard function composition. The symmetric group \(S_n\) is the subroup of \(T_n\) composed of all the permutations. What is the complexity of the following decision problems with respect to the parameter \(n\):

Problem 1: Given a submonoid \(\langle s_1,s_2\rangle \subseteq T_n\) generated by two elements, does there exist an integer \(m\) smaller than \(n\) such that \(\langle s_1,s_2\rangle\) can be embedded in \(T_m\)?

Problem 2: Given a subgroup \(\langle g_1,g_2\rangle \subseteq S_n\) generated by two elements, does there exist an integer \(m\) smaller than \(n\) such that \(\langle g_1,g_2\rangle\) can be embedded in \(S_m\)?

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>

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.

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!