22.1 Complexity of fixed VAS reachability

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

22.2 Paired Counter Automata

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?

22.3 Universal coverability for Orthant VAS

An orthant is a region in \(\mathbb{R}^d\) in which every vector in the orthant has the same sign in each dimension. In a vector addition system sum vectors taken non-deterministically from a given set, providing the sum remains in the positive orthant (all vectors positive). Z-VAS can visit all orthants, but the set of vectors that can be applied is the same in every orthant.

An orthant VAS has a different set of vectors for each orthant. Any vector from the set of the current orthant can be applied, the result of which may be in the same orthant, or another orthant.

Continue Reading →

22.4 Reconfigurable broadcast networks (RBN)

Reconfigurable broadcast networks (RBN) are networks consisting of finite-state, anonymous agents that communicate by broadcast. An agent broadcasts a message which is received by its neighbors (one step is a broadcast plus multiple simultaneous receives). The neighbor topology can change (reconfigure) between any step.

Continue Reading →

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