Abstract
We introduce the existential width measure (respectively, the maximal existential width), which, roughly speaking, for an alternating finite automaton (AFA), counts the number of branches which do not need to be traversed in an accepting computation (respectively, the maximum number of branches which can be ignored in any computation tree of the AFA). We also define the combined width (respectively, the maximal combined width), by combining this new measure with an existing measure, the universal width (respectively, the maximal universal width), which counts the minimum number of branches of a computation tree which must be traversed for an AFA to accept a computation (respectively, the maximum number of branches which can be traversed in any computation tree of the AFA). We give a polynomial algorithm to decide whether the (maximal) combined width is bounded, and a construction showing that an AFA with finite combined width can be simulated by an NFA with only a polynomial blow-up in the number of states. We also improve the upper bound for deciding finiteness of an m-state NFA’s tree width from \(O(m^3)\) to \(O(m^2)\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114–133 (1981)
Geffert, V.: An alternating hierarchy for finite automata. Theor. Comput. Sci. 445, 1–24 (2012)
Holzer, M.: On emptiness and counting for alternating finite automata. In: Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17–21 July 1995, pp. 88–97 (1995)
Hospodár, M., Jirásková, G., Krajňáková, I.: Operations on Boolean and alternating finite automata. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 181–193. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90530-3_16
Hromkovič, J., Seibert, S., Karhumäki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inform. Comput 172(2), 202–217 (2002)
Hromkovic, J.: On the power of alternation in automata theory. J. Comput. Syst. Sci. 31(1), 28–39 (1985)
Keeler, C., Salomaa, K.: Alternating finite automata with limited universal branching. In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) LATA 2020. LNCS, vol. 12038, pp. 196–207. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40608-0_13
King, K.N.: Alternating multihead finite automata (extended abstract). In: Automata, Languages and Programming, 8th Colloquium, Acre (Akko), Israel, July 13–17, 1981, Proceedings, pp. 506–520 (1981)
Moriya, E.: A grammatical characterization of alternating pushdown automata. Theor. Comput. Sci. 67(1), 75–85 (1989)
Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity of finite tree width NFAs. J. Autom. Lang. Comb. 17(2–4), 245–264 (2012)
Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18(6), 1263–1282 (1989)
Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 21(2), 218–235 (1980)
Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoret. Comput. Sci. 88(2), 325–349 (1991)
Acknowledgements
Research supported by NSERC grant OGP0147224.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Keeler, C., Salomaa, K. (2020). Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)