Let \(A\) be an automaton and write, for any word \(w\), \(f_w\) for the function that maps any state \(q\) to the state reached by reaching \(w\) from \(q\).

The membership problem MEMB(\(V\)) for a class \(V\) of deterministic automata is the following:

• Given: An automaton \(A \in V\) and a function \(f\colon Q \to Q\) from states to states
• Question: Is there a word \(w\) such that \(f_w = f\)?

In the late 1980s, Beaudry, together with McKenzie and Thérien, studied the problem for most natural classes \(V\) (e.g., groups and aperiodic automata). Quoting Beaudry, McKenzie, Thérien, 1992:

"For each \(V\) aperiodic, the computational complexity of MEMB(\(V\)) turns out to look familiar. Only five possibilities occur as \(V\) ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB(\(V\)) is either PSPACE-complete, NP-complete, P-complete or in AC\(⁰\)."

Continue Reading →

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

Continue Reading →

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

Continue Reading →

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?

Continue Reading →

The sequential flow problem (SFP) is a simple and natural reachability problem which was initially formalized for solving questions related to population protocols, but has independent interest. We now know that SFP is PSPACE-hard, and in EXPSPACE, but its precise complexity remains open. The following poster gives more background.

Continue Reading →

Valiant showed that the succinctness gap between deterministic and nondeterministic pushdown automata (restricted to deterministic contextfree languages) is nonrecursive, i.e., there is no computable function \(f\) with the following property: If the language of a pushdown automaton \(A\) is deterministic contextfree, then there is a deterministic pushdown automaton of size \(f(|A|)\) recognizing \(L(A)\).

Recently, good-for-games pushdown automata have been introduced, whose expressive power is strictly between the deterministic contextfree and the contextfree languages.

Continue Reading →

Given an automaton \(A\), consider the following two games:

Game I. At each turn \(i\):

• Adam plays a letter \(a_i\)
• Eve plays a transition \(r_i\) over \(a_i\)

A play is the infinite word \(w=a_0a_1\ldots\) and the sequence of transitions \(r=r_0r_1\ldots\) Eve wins if either \(w\) is not in \(L(A)\) or \(r\) is an accepting run over \(w\) in \(A\).

Game II. At each turn turn \(i\):

• Adam plays a letter \(a_i\)
• Eve plays a transition \(r_i\) over \(a_i\)
• Adam plays a pair of transitions \(s_i\) and \(t_i\)

A play is the triple of sequences of runs \(r=r_0r_1\ldots, s=s_0s_1\ldots\) and \(t=t_0t_1\ldots\) Eve wins if either \(r\) is an accepting run of \(A\) or both \(s\) and \(t\) are not accepting runs of \(A\).

Continue Reading →