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