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\(⁰\)."

The open case is with \(V\) defined in any of the following equivalent ways:

- The set of minimal automata such that the reverse language is recognized by a partially-ordered automaton (i.e., the transition function induces a partial order).
- The set of minimal automata in which for every word \(w\), if \(f_w = f_{ww}\) then \(f_w = f_{aw}\) for any letter \(a\) of \(w\).
- The set of minimal automata of $\mathcal{L}$-trivial languages.

*Question:* Is the membership problem for that class in NP or PSPACE-hard?
(These are the two possibilities.)