[Journal] Existential and Universal Width of Alternating Finite Automata

Summary

Read the abstract.

Contribution

This is the journalized version of the DCFS’23 paper “Existential and Universal Width of 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, 2025, To appear.