@inproceedings{74ae8ae9eaa8481ebd33e8998e631172,
title = "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.",
keywords = "alternating finite automaton, decidability, measure of nondeterminism, space complexity, universal and existential choices",
author = "Han, {Yo Sub} and Sungmin Kim and Ko, {Sang Ki} and Kai Salomaa",
note = "Publisher Copyright: {\textcopyright} 2023, IFIP International Federation for Information Processing.; 25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023 ; Conference date: 04-07-2023 Through 06-07-2023",
year = "2023",
doi = "10.1007/978-3-031-34326-1_4",
language = "English",
isbn = "9783031343254",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "51--64",
editor = "Henning Bordihn and Nicholas Tran and Gy{\"o}rgy Vaszil",
booktitle = "Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings",
address = "Germany",
}