TY - JOUR

T1 - Decision problems for reversible and permutation automata

AU - Радионова, Мария Алексеевна

AU - Охотин, Александр Сергеевич

PY - 2026/9/1

Y1 - 2026/9/1

N2 - For different kinds of reversible finite automata, the complexity of decision problems, such as emptiness, universality, equivalence and inclusion, is investigated. For permutation automata, all these problems are 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. 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 complexity of all the same problems is also determined in the case of a unary alphabet, where some problems become easier. Some partial results on testing minimality of these automata are obtained. Finally, length-bounded emptiness problems for several cases of permutation automata are proved to be PSPACE-complete, which is harder than the emptiness problem without the length bound.

AB - For different kinds of reversible finite automata, the complexity of decision problems, such as emptiness, universality, equivalence and inclusion, is investigated. For permutation automata, all these problems are 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. 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 complexity of all the same problems is also determined in the case of a unary alphabet, where some problems become easier. Some partial results on testing minimality of these automata are obtained. Finally, length-bounded emptiness problems for several cases of permutation automata are proved to be PSPACE-complete, which is harder than the emptiness problem without the length bound.

KW - Emptiness problem

KW - Equivalence problem

KW - Multiple-entry automata

KW - Permutation automata

KW - Reversible automata

KW - Sweeping automata

KW - Two-way automata

KW - Universality problem

UR - https://www.mendeley.com/catalogue/693232c6-8baf-35cc-8c46-f4538c1b4439/

U2 - 10.1016/j.ic.2026.105488

DO - 10.1016/j.ic.2026.105488

M3 - Article

VL - 312

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105488

ER -