Decision Problems for Reversible and Permutation Automata

For different kinds of reversible finite automata, the complexity of decision problems, such as emptiness, universality, equivalence and inclusion, is investigated. For permutation automata, they are all L-complete. For permutation automata with multiple initial states, emptiness is L-complete and the rest are co-NP-complete. For sweeping permutation automata, all are co-NP-complete, whereas length-bounded emptiness is PSPACE-complete. For reversible automata, the results are similar to deterministic automata, but universality is easier: L-complete for one initial state (cf. NL-complete for DFA), co-NP-complete for multiple initial states (cf. PSPACE-complete for multiple-entry DFA) and co-NP-complete in the sweeping case (cf. PSPACE-complete for two-way DFA). The minimality problem and the unary case are also investigated.