← All problems
Unverified

Membership in Reversed Partially-Ordered Automata

Let AA be an automaton and write, for any word ww, fwf_w for the function that maps any state qq to the state reached by reaching ww from qq. The membership problem MEMB(VV) for a class VV of deterministic automata is the following: Given: An automaton A∈VA \in V and a function f ⁣:Q→Qf\colon Q \to Q from states to states Question: Is there a word ww such that fw=ff_w = f? In the late 1980s, Beaudry, together with McKenzie and Thérien, studied the problem for most natural classes VV (e.g., groups and aperiodic automata). Quoting Beaudry, McKenzie, Thérien, 1992: "For each VV aperiodic, the computational complexity of MEMB(VV) turns out to look familiar. Only five possibilities occur as VV ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB(VV) is either PSPACE-complete, NP-complete, P-complete or in AC0^0." The open case is with VV 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 ww, if fw=fwwf_w = f_{ww} then fw=fawf_w = f_{aw} for any letter aa of ww. The set of minimal automata of L\mathcal{L}-trivial languages. Question: Is the membership problem for that class in NP or PSPACE-hard? (These are the two possibilities.)

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu