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.
22.6 Completing Partial DFAs to Synchronizing DFAs
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.
22.8 From two-way to one-way transducers, revisited
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?
22.9 Constructive Zermelo's Problem
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)$?
22.10 The Parity Language
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$).
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$ ?
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 a set explicitly (called the universal Skolem set).
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.