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

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?

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