[Journal] Existential and Universal Width of Alternating Finite Automata
Published:
Summary
Read the abstract.
Contribution
The existential and universal width are measures of nondeterminism of an AFA. We present decidability and complexity results for the existential and universal width for alternating finite automata.
Abstract
The existential width of an alternating finite automaton (AFA) A on a string w is, roughly speaking, the number of nondeterministic choices that A uses in an accepting computation on w that uses least nondeterminism. The universal width of A on string w is the least number of parallel branches an accepting computation of A on w uses. The existential or universal width of A is said to be finite if it is bounded for all accepted strings. We show that finiteness of existential and universal width of an AFA is decidable. Also we give hardness results and give an algorithm to decide whether the existential or universal width of an AFA is bounded by a given integer.
Recommended citation:
Yo-Sub Han, Sungmin Kim, Sang-Ki Ko, and Kai Salomaa. “Existential and Universal Width of Alternating Finite Automata.” Information and Computation (IC), 2025.