Existential and universal width of alternating finite automata
Yo-Sub Han, Sungmin Kim, Sang-Ki Ko and Kai Salomaa.
Published in Information and Computation, 2025.
Published in Information and Computation, 2025.
Definitions
Alternating finite automaton (AFA):
a finite state automaton with two types of states: existential and universal.
Existential and universal width:
the existential width of an AFA is the supremum of the number of existential choices over all accepting strings and their accepting computation trees.
The universal width of an AFA is the supremum of
the number of leaves over all accepting strings and their accepting computation trees.
Summary of results
- Decidability for the finiteness of existential and universal width of an AFA
- PSPACE-completeness for the finiteness of existential width of an NFA (the case when there are no universal states)
- PSPACE-completeness for the finiteness of universal width of a UFA (the case when there are no existential states)
- EXPSPACE algorithms for decidng whether or not the existential and universal width of an AFA is less than some given integer $k$
Keywords
alternating finite automaton, nondeterminism, algorithmic complexity