Existential and Universal Width of Alternating Finite Automata

Yo Sub Han; Sungmin Kim; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-031-34326-1_4

Existential and Universal Width of Alternating Finite Automata

Yo Sub Han, Sungmin Kim, Sang Ki Ko, Kai Salomaa

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings
Editors	Henning Bordihn, Nicholas Tran, György Vaszil
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	51-64
Number of pages	14
ISBN (Print)	9783031343254
DOIs	https://doi.org/10.1007/978-3-031-34326-1_4
Publication status	Published - 2023
Event	25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023 - Potsdam, Germany Duration: 2023 Jul 4 → 2023 Jul 6

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13918 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023
Country/Territory	Germany
City	Potsdam
Period	23/7/4 → 23/7/6

Bibliographical note

Publisher Copyright:
© 2023, IFIP International Federation for Information Processing.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-34326-1_4

Cite this

Han, Y. S., Kim, S., Ko, S. K., & Salomaa, K. (2023). Existential and Universal Width of Alternating Finite Automata. In H. Bordihn, N. Tran, & G. Vaszil (Eds.), Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings (pp. 51-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13918 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-34326-1_4

Han, Yo Sub ; Kim, Sungmin ; Ko, Sang Ki et al. / Existential and Universal Width of Alternating Finite Automata. Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings. editor / Henning Bordihn ; Nicholas Tran ; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2023. pp. 51-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e18a1e0a77df41aabe19121742989849,

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",

}

Han, YS, Kim, S, Ko, SK & Salomaa, K 2023, Existential and Universal Width of Alternating Finite Automata. in H Bordihn, N Tran & G Vaszil (eds), Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13918 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 51-64, 25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023, Potsdam, Germany, 23/7/4. https://doi.org/10.1007/978-3-031-34326-1_4

Existential and Universal Width of Alternating Finite Automata. / Han, Yo Sub; Kim, Sungmin; Ko, Sang Ki et al.
Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings. ed. / Henning Bordihn; Nicholas Tran; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2023. p. 51-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13918 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Existential and Universal Width of Alternating Finite Automata

AU - Han, Yo Sub

AU - Kim, Sungmin

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - alternating finite automaton

KW - decidability

KW - measure of nondeterminism

KW - space complexity

KW - universal and existential choices

UR - http://www.scopus.com/inward/record.url?scp=85162790428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85162790428&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-34326-1_4

DO - 10.1007/978-3-031-34326-1_4

M3 - Conference contribution

AN - SCOPUS:85162790428

SN - 9783031343254

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 64

BT - Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings

A2 - Bordihn, Henning

A2 - Tran, Nicholas

A2 - Vaszil, György

PB - Springer Science and Business Media Deutschland GmbH

T2 - 25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023

Y2 - 4 July 2023 through 6 July 2023

ER -

Han YS, Kim S, Ko SK, Salomaa K. Existential and Universal Width of Alternating Finite Automata. In Bordihn H, Tran N, Vaszil G, editors, Descriptional Complexity of Formal Systems - 25th IFIP WG 1.02 International Conference, DCFS 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 51-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-34326-1_4