Maximal Existential and Universal Width – Facultatea de Informatică

Published in Volume XXXIII, Issue 1, 2023, pages 53-77, doi: 10.7561/SACS.2023.1.53

Authors: C. Keeler, K. Salomaa

Abstract

The tree width of an alternating finite automaton (AFA) measures the parallelism in all computations of the AFA on a given input. The maximal existential (respectively, universal) width of an AFA A on string w measures the maximal number of existential choices (respectively, of parallel universal branches) in one computation of A on w.

We give polynomial time algorithms deciding finiteness of an AFA’s tree width and maximal universal width. Also we give a polynomial time algorithm that for an AFA A with finite maximal universal width decides whether or not the maximal existential width of A is finite. Finiteness of maximal existential width is decidable in the general case but the algorithm uses exponential time. Additionally, we establish necessary and sufficient conditions for an AFA to have exponential tree width growth rate, as well as sufficient conditions for an AFA to have exponential maximal existential width or exponential maximal universal width.

Full Text (PDF)

References

[1] Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114–133, 1981. doi:10.1145/322234.322243.

[2] Viliam Geffert. An alternating hierarchy for finite automata. Theoretical Computer Science, 445:1–24, 2012. doi:10.1016/j.tcs.2012.04.044.

[3] Jonathan Goldstine, Martin Kappes, Chandra M. R. Kintala, Hing Leung, Andreas Malcher, and Detlef Wotschke. Descriptional complexity of machines with limited resources. Journal of Universal Computer Science, 8(2):193–234, 2002. doi:10.3217/jucs-008-02-0193.

[4] Jonathan Goldstine, Chandra M. R. Kintala, and Detlef Wotschke. On measuring nondeterminism in regular languages. Information and Computation, 86:179–194, 1990. doi:10.1016/0890-5401(90)90053-K.

[5] Yo-Sub Han, Sungmin Kim, Sang-Ki Ko, and Kai Salomaa. Existential and universal width of alternating finite automata. In 25th International Conference on Descriptional Complexity of Formal Systems, DCFS 2023, Lecture Notes in Computer Science. Springer, 2023 (to appear).

[6] Yo-Sub Han, Arto Salomaa, and Kai Salomaa. Ambiguity, nondeterminism and state complexity of finite automata. Acta Cybernetica, 23:141–157, 2017. doi:10.14232/actacyb.23.1.2017.9.

[7] Markus Holzer and Martin Kutrib. Descriptional and computational complexity of finite automata – a survey. Information and Computation, 209(3):456–470, 2011. doi:10.1016/j.ic.2010.11.013.

[8] Juraj Hromkovic, Sebastian Seibert, Juhani Karhumäki, Hartmut Klauck, and Georg Schnitger. Communication complexity method for measuring nondeterminism in finite automata. Information and Computation, 172(2):202–217, 2002. doi:10.1006/inco.2001.3069.

[9] Chris Keeler. Finite Automata with Restricted Nondeterminism and Universality. PhD thesis, Queen’s University, 2021.

[10] Chris Keeler and Kai Salomaa. Combining limited parallelism and nondeterminism in alternating finite automata. In Galina Jirásková and Giovanni Pighizzini, editors, 22nd International Conference on Descriptional Complexity of Formal Systems, DCFS 2020, volume 12442 of Lecture Notes in Computer Science, pages 91–103. Springer, 2020. doi:10.1007/978-3-030-62536-8\_8.

[11] Chris Keeler and Kai Salomaa. Structural properties of NFAs and growth rates of nondeterminism measures. Information and Computation, 284:article 104690, 2022. doi:10.1016/j.ic.2021.104690.

[12] Chandra M. R. Kintala and Detlef Wotschke. Amounts of nondeterminism in finite automata. Acta Informatica, 13(2):199–204, 1980. doi:10.1007/BF00263994.

[13] Richard E. Ladner, Richard J. Lipton, and Larry J. Stockmeyer. Alternating pushdown and stack automata. SIAM Journal of Computing, 13(1):135–155, 1984. doi:10.1137/0213010.

[14] Ernst L. Leiss. Succinct representation of regular languages by Boolean automata. Theoretical Computer Science, 13:323–330, 1981. doi:10.1016/S0304-3975(81)80005-9.

[15] Hing Leung. Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM Journal of Computing, 27(4):1073–1082, 1998. doi:10.1137/S0097539793252092.

[16] Alexandros Palioudakis, Kai Salomaa, and Selim G. Akl. State complexity of finite tree width NFAs. Journal of Automata, Languages and Combinatorics, 17(2-4):245–264, 2012. doi:10.25596/jalc-2012-245.

[17] Bala Ravikumar and Oscar H. Ibarra. Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM Journal of Computing, 18(6):1263–1282, 1989. doi:10.1137/0218083.

[18] Jeffrey O. Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2008. doi:10.1017/CBO9780511808876.

[19] Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325–349, 1991. doi:10.1016/0304-3975(91)90381-B.

Bibtex

@article{sacscuza:keeler23meuw,
  title={Maximal Existential and Universal Width},
  author={Casey Keeler, Kai Salomaa},
  journal={Scientific Annals of Computer Science},
  volume={33},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2023},
  pages={53-77},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2023.1.53}
}