Membership in Reversed Partially-Ordered Automata
Let be an automaton and write, for any word , for the function that maps any state to the state reached by reaching from . The membership problem MEMB() for a class of deterministic automata is the following: Given: An automaton and a function from states to states Question: Is there a word such that ? In the late 1980s, Beaudry, together with McKenzie and Thérien, studied the problem for most natural classes (e.g., groups and aperiodic automata). Quoting Beaudry, McKenzie, Thérien, 1992: "For each aperiodic, the computational complexity of MEMB() turns out to look familiar. Only five possibilities occur as ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB() is either PSPACE-complete, NP-complete, P-complete or in AC." The open case is with 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 , if then for any letter of . The set of minimal automata of -trivial languages. Question: Is the membership problem for that class in NP or PSPACE-hard? (These are the two possibilities.)
