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

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