Abstract
We examine operational complexity assuming that the arguments are given as nondeterministic finite automata and the resulting language is represented by a deterministic finite automaton. We show that the known upper bounds for Boolean operations and concatenation are met by ternary languages, and we prove that they are asymptotically tight in the binary case. For the cut and square operations, we get tight upper bounds \(2^{m-1}(2^n+1)\) and \(\frac{3}{4}2^{2n}\), respectively. Our witnesses are described over a four-letter alphabet for cut, and a ten-letter alphabet for square. We also show that the tight upper bound on the syntactic complexity of a language given by an n-state NFA is \(2^{n^2}\). For the square root operation, we provide a lower bound \(2^{n^2-n}\) and an upper bound \(2^{n^2}\).
M. Hospodár—This publication was supported by the Operational Programme Integrated Infrastructure (OPII) for the project 313011BWH2: “InoCHF - Research and development in the field of innovative technologies in the management of patients with CHF”, co-financed by the European Regional Development Fund.
M. Hospodár and G. Jirásková—Supported by the Slovak Grant Agency for Science (VEGA) under contract 2/0096/23 “Automata and Formal Languages: Descriptional and Computational Complexity”.
J. Jirásek and J. Šebej—Supported by the Slovak Grant Agency for Science (VEGA) under contract 1/0177/21 “Descriptional and Computational Complexity of Automata and Algorithms”.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Berglund, M., Björklund, H., Drewes, F., van der Merwe, B., Watson, B.W.: Cuts in regular expressions. In: Béal, M., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 70–81. Springer (2013). https://doi.org/10.1007/978-3-642-38771-5_8
Brzozowski, J.A.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1/2), 71–89 (2010). https://doi.org/10.25596/jalc-2010-071
Brzozowski, J.A., Szykuła, M., Ye, Y.: Syntactic complexity of regular ideals. Theory Comput. Syst. 62(5), 1175–1202 (2017). https://doi.org/10.1007/s00224-017-9803-8
Câmpeanu, C., Salomaa, K., Yu, S.: Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb. 7(3), 303–310 (2002). https://doi.org/10.25596/jalc-2002-303
Caron, P., Hamel-De le Court, E., Luque, J.G., Patrou, B.: New tools for state complexity. Discret. Math. Theor. Comput. Sci. 22(1) (2020). https://doi.org/10.23638/DMTCS-22-1-9
Drewes, F., Holzer, M., Jakobi, S., van der Merwe, B.: Tight bounds for cut-operations on deterministic finite automata. Fundam. Inform. 155(1–2), 89–110 (2017). https://doi.org/10.3233/FI-2017-1577
Holzer, M., Hospodár, M.: The range of state complexities of languages resulting from the cut operation. In: Martín-Vide, C., Okhotin, A., Shapira, D. (eds.) LATA 2019. LNCS, vol. 11417, pp. 190–202. Springer (2019). https://doi.org/10.1007/978-3-030-13435-8_14
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14(6), 1087–1102 (2003). https://doi.org/10.1142/S0129054103002199
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory. Addison-Wesley, Languages and Computation (1979)
Hospodár, M., Olejár, V.: The cut operation in subclasses of convex languages (extended abstract). In: Caron, P., Mignot, L. (eds.) CIAA 2022. LNCS, vol. 13266, pp. 152–164. Springer (2022). https://doi.org/10.1007/978-3-031-07469-1_12
Jirásek, J.Š., Jirásková, G., Szabari, A.: Operations on self-verifying finite automata. In: Beklemishev, L.D., Musatov, D.V. (eds.) CSR 2015. LNCS, vol. 9139, pp. 231–261. Springer (2015). https://doi.org/10.1007/978-3-319-20297-6_16
Jirásek, J., Jr., Jirásková, G., Šebej, J.: Operations on unambiguous finite automata. Int. J. Found. Comput. Sci. 29(5), 861–876 (2018). https://doi.org/10.1142/S012905411842008X
Jirásková, G., Krajňáková, I.: NFA-to-DFA trade-off for regular operations. In: Hospodár, M., Jirásková, G., Konstantinidis, S. (eds.) DCFS 2019. LNCS, vol. 11612, pp. 184–196. Springer (2019). https://doi.org/10.1007/978-3-030-23247-4_14
Jirásková, G., Okhotin, A.: On the state complexity of operations on two-way finite automata. Inf. Comput. 253, 36–63 (2017). https://doi.org/10.1016/j.ic.2016.12.007
Jirásková, G., Šebej, J.: Reversal of binary regular languages. Theoret. Comput. Sci. 449, 85–92 (2012). https://doi.org/10.1016/j.tcs.2012.05.008
Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Doklady 11, 1373–1375 (1970)
Myhill, J.: Finite automata and representation of events. Wright Air Development Center Technical Report, pp. 57–624 (1957)
Rampersad, N.: The state complexity of \({L}^2\) and \({L}^k\). Inf. Process. Lett. 98(6), 231–234 (2006). https://doi.org/10.1016/j.ipl.2005.06.011
Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theor. Comput. Sci. 383(2–3), 140–152 (2007). https://doi.org/10.1016/j.tcs.2007.04.015
Sipser, M.: Introduction to the theory of computation. Cengage Learning (2012)
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1: Word, Language, Grammar, pp. 41–110. Springer (1997). https://doi.org/10.1007/978-3-642-59136-5_2
Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994). https://doi.org/10.1016/0304-3975(92)00011-F
Acknowledgment
We would like to thank Ivana Krajňáková for her wide and long-term contribution to some parts of this research.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 IFIP International Federation for Information Processing
About this paper
Cite this paper
Hospodár, M., Jirásek, J., Jirásková, G., Šebej, J. (2023). Operational Complexity: NFA-to-DFA Trade-Off. In: Bordihn, H., Tran, N., Vaszil, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2023. Lecture Notes in Computer Science, vol 13918. Springer, Cham. https://doi.org/10.1007/978-3-031-34326-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-34326-1_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34325-4
Online ISBN: 978-3-031-34326-1
eBook Packages: Computer ScienceComputer Science (R0)