22.19 Membership in Reversed Partially-Ordered Automata

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 →

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

Continue Reading →

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

Continue Reading →

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?

Continue Reading →

20.10 Tighten the complexity of solving random-turn games

A random-turn game is a graph game which is parameterized by a ratio \(p\). In each turn, we throw a coin with bias \(p\) to determine which player moves the token. Formally, random-turn games are a special case of stochastic games. We are interested in finding, for each vertex, the "value" of the game, which is the optimal probability with which Player 1 can guarantee winning. Stated as a decision problem: decide whether the value is greater than 0.5. The problem is known to be in NP and coNP (again, a special case of stochastic games), but not known to be in P nor to be as hard as stochastic games (or any other problem in NP and coNP).

My interest in random-turn games stems from the fact that they are equivalent to bidding games: a solution to a random-turn game can be used to construct optimal bidding strategies in a bidding game. Moreover, random-turn games have been extensively studied in the combinatorics community.

20.11 The sequential flow problem

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 →

20.12 Succinctness of GFG pushdown automata

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 →

20.9 Memory requirements for generalized reachability games

Given a regular language \(L\) (on finite words), we consider the condition over omega-words "having a prefix in \(L\)". We want to characterize the optimal memory requirements for this condition over finite arenas. The memory requirements for the opponent were characterized by Colcombet, Fijalkow and Horn in the 2012 paper "Playing Safe" (that also holds for infinite arenas).

20.8 Good games for good-for-games automata

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 →