Existential and Universal Width of Alternating Finite Automata
Published:
Contribution
This is my first shot at solving problems related to alternating finite automata. The paper is another result of the visiting research in Canada.
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.” International Conference on Descriptional Complexity of Formal Systems (DCFS), 2023.