22.5 Decidability of $(\min,+)$-weighted automata determinization

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.

22.6 Completing Partial DFAs to Synchronizing DFAs

Problem Definition: Let \(A = (Q, \Sigma, \delta)\) be a (complete) deterministic finite automaton (DFA) where \(Q\) is a finite set of states, \(\Sigma\) is a finite alphabet and \(\delta \colon Q \times \Sigma \to Q\) is a (totally defined) transition function (we neglect start and final states). We generalize \(\delta\) to words \(w= w_1w_2 \dots w_n\), \(w_i \in \Sigma\) by setting \(\delta(q, w) = \delta(\delta(q, w_1)w_2\dots w_n)\). We further generalize it to sets \(S\) of states by \(\delta(S, w) = \cup_{q\in S}\{\delta(q, w)\}\). We say that a word \(w\in \Sigma^*\) is synchronizing for \(A\) if \(|\delta(Q, w)| = 1\), i.e., regardless from which state we read \(w\), we end up in the same state.

Continue Reading →

22.7 Equivalent k-HD-TA for a given 1-NTA

Question: Given a non-deterministic timed automata with 1 clock(1-NTA) and reachability acceptance condition, decide whether there exists an equivalent history deterministic timed automata with k clocks ($k$-HDTA), where \(k\) can be fixed or arbitrary?

Motivation: The classes of 1-NTA, deterministic timed automata (DTA), history-deterministic timed automata (HDTA) all have decidable language inclusion problems, though the complexity of inclusion for 1-NTA is non-primitive recursive. However, the class 1-NTA is incomparable to DTA and HDTA.

Continue Reading →

22.12 3-decomposition Conjecture

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.

22.13 Büchi automata using graph neural networks

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.

22.14 Transformation monoid minimisation

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\)?

22.15 Universal Positivity Set

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?

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

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.

Continue Reading →