Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1007/978-3-540-70844-5_1guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Nondeterministic Finite Automata--Recent Results on the Descriptional and Computational Complexity

Published: 21 July 2008 Publication History

Abstract

Nondeterministic finite automata (NFAs) were introduced in [67], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

References

[1]
Adorna, H.N.: 3-party message complexity is better than 2-party ones for proving lower bounds on the size of minimal nondeterministic finite automata. J. Autom. Lang. Comb. 7, 419-432 (2002).
[2]
Adorna, H.N.: Some descriptional complexity problems in finite automata theory. In: Philippine Computing Science Congress, pp. 27-32. Computing Society of the Philippines (2005).
[3]
Amilhastre, J., Janssen, P., Vilarem, M.C.: FA minimisation heuristics for a class of finite languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 1-12. Springer, Heidelberg (2001).
[4]
Berman, P., Lingas, A.: On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences (1977).
[5]
Birget, J.C.: Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43, 185-190 (1992).
[6]
Birget, J.C.: Partial orders on words, minimal elements of regular languages and state complexity. Theoret. Comput. Sci. 119, 267-291 (1993).
[7]
Birget, J.C.: Erratum: Partial orders on words, minimal elements of regular languages and state complexity (2002), http://clam.rutgers.edu/~birget/papers.html
[8]
Birget, J.C.: State-complexity of finite-state devices, state compressibility and incompressibility. Math. Systems Theory 26, 237-269 (1993).
[9]
Björklund, H., Martens, W.: The tractability frontier for NFA minimization. In: International Colloqium on Automata, Languages and Propgramming (ICALP 2008). LNCS. Springer, Heidelberg (to appear, 2008).
[10]
Bordihn, H., Holzer, M., Kutrib, M.: State complexity of NFA to DFA conversion for subregular language families (submitted for publication 2008).
[11]
Câmpeanu, C., Čulik, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., Jürgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60-70. Springer, Heidelberg (2001).
[12]
Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47, 149-158 (1986).
[13]
Chrobak, M.: Errata to finite automata and unary languages. Theoret. Comput. Sci. 302, 497-498 (2003).
[14]
Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 315-326. Springer, Heidelberg (2006).
[15]
Domaratzki, M., Salomaa, K.: Transition complexity of language operations. Theoret. Comput. Sci. 387, 147-154 (2007).
[16]
Domaratzki, M., Okhotin, A.: State complexity of power. TUCS Technical Report 845, Turku Centre for Computer Science (2008).
[17]
Ellul, K.: Descriptional complexity measures of regular languages. Master's thesis, University of Waterloo (2002).
[18]
Geffert, V. (Non)determinism and the size of one-way finite automata. In: Descriptional Complexity of Formal Systems (DCFS 2005). Rapporto Tecnico 06-05, Università degli Studi di Milano, pp. 23-37 (2005).
[19]
Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205, 1652-1670 (2007).
[20]
Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59, 75-77 (1996).
[21]
Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS 8, 193-234 (2002).
[22]
Gramlich, G.: Probabilistic and nondeterministic unary automata. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 460-469. Springer, Heidelberg (2003).
[23]
Gramlich, G.: Über die algorithmische Komplexität regulärer Sprachen. Doctoral Dissertation, Johann Wolfgang-Goethe-Univeristät, Frankfurt am Main (2007).
[24]
Gramlich, G., Schnitger, G.: Minimizing NFA's and regular expressions. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 399-411. Springer, Heidelberg (2005).
[25]
Gruber, H., Holzer, M.: A note on the number of transitions of nondeterministic finite automata. In: Theorietag "Automaten und Formale Sprachen". Universität Tübingen, pp. 24-25 (2005).
[26]
Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 363-374. Springer, Heidelberg (2006).
[27]
Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: Language and Automata Theory and Applications (LATA), pp. 261-272. Universitat Rovira i Virgili, Tarragona (2007).
[28]
Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P ≠ NP. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 205-216. Springer, Heidelberg (2007).
[29]
Gruber, H., Holzer, M.: Results on the average state and transition complexity of finite automata accepting finite languages. Theoret. Comput. Sci. 387, 155-166 (2007).
[30]
Hagenah, C., Muscholl, A.: Computing Ɛ-free NFA from regular expressions in O ( n log 2 n ) time. RAIRO Inform. Théor. 34, 257-277 (2000).
[31]
Han, Y.S., Salomaa, K.: State complexity of union and intersection of finite languages. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 217-228. Springer, Heidelberg (2007).
[32]
Havel, I.M.: The theory of regular events II. Kybernetica 6, 520-544 (1969).
[33]
Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Autom., Lang. Comb. 6, 453-466 (2001).
[34]
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14, 1087-1102 (2003).
[35]
Hopcroft, J.E.: An n log n algorithm for minimizing the state in a finite automaton. In: The Theory of Machines and Computations, pp. 189-196. Academic Press, London (1971).
[36]
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979).
[37]
Hromkovič, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997).
[38]
Hromkovič, J.: Descriptional complexity of finite automata: Concepts and open problems. J. Autom., Lang. Comb. 7, 519-531 (2002).
[39]
Hromkovič, J., Seibert, S., Karhumäki, J., Klauck, H., Schnitger, G.: Communication Complexity Method for Measuring Nondeterminism in Finite Automata. Inform. Comput. 172, 201-217 (2002).
[40]
Hromkovič, J., Schnitger, G.: Comparing the size of NFAs with and without Ɛ-transitions. Theoret. Comput. Sci. 380, 100-114 (2007).
[41]
Hromkovič, J., Seibert, S., Wilke, T.: Translating regular expressions in small-free nondeterministic finite automata. J. Comput. System Sci. 62, 565-588 (2001).
[42]
Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to n -state NFAs. Theoret. Comput. Sci. 237, 485-494 (2000).
[43]
Iwama, K., Matsuura, A., Paterson, M.: A family of NFAs which need 2 n - α deterministic states. Theoret. Comput. Sci. 301, 451-462 (2003).
[44]
Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over a unary alphabet. Int. J. Found. Comput. Sci. 2, 163-182 (1991).
[45]
Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22, 1117-1141 (1993).
[46]
Jirásek, J., Jirásková, G., Szabari, A.: State Complexity of Concatenation and Complementation. Int. J. Found. Comput. Sci. 16, 511-529 (2005).
[47]
Jirásek, J., Jirásková, G., Szabari, A.: Deterministic blow-ups of minimial nondeterministic finite automata over a fixed alphabet. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 254-265. Springer, Heidelberg (2007).
[48]
Jirásková, G.: Note on minimal finite automata. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 421-431. Springer, Heidelberg (2001).
[49]
Jirásková, G.: Note on minimal automata and uniform communication protocols. In: Grammars and Automata for String Processing, pp. 163-170. Taylor and Francis, Abington (2003).
[50]
Jirásková, G.: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 287-298 (2005).
[51]
Jirásková, G., Okhotin, A.: State complexity of cyclic shift. RAIRO Inform. Théor. 42, 335-360 (2008).
[52]
Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Trans. Comput. C-19, 617-627 (1970).
[53]
Kapoutsis, C.A.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 544- 555. Springer, Heidelberg (2005).
[54]
Kari, J.: Personal communication (2006).
[55]
Landau, E.: Über die Maximalordnung der Permutationen gegebenen Grades. Archiv der Math. und Phys. 3, 92-103 (1903).
[56]
Landau, E.: Handbuch der Lehre von der Verteilung der Primzahlen. Teubner (1909).
[57]
Leiss, E.: Succinct representation of regular languages by Boolean automata. Theoret. Comput. Sci. 13, 323-330 (1981).
[58]
Lifshits, Y.: A lower bound on the size of Ɛ-free NFA corresponding to a regular expression. Inform. Process. Lett. 85, 293-299 (2003).
[59]
Malcher, A.: Minimizing finite automata is computationally hard. Theoret. Comput. Sci. 327, 375-390 (2004)}.
[60]
Mandl, R.: Precise bounds associated with the subset construction on various classes of nondeterministic finite automata. In: Princeton Conference on Information and System Sciences, pp. 263-267 (1973).
[61]
Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata. Theoret. Comput. Sci. 330, 349-360 (2005).
[62]
Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30, 1976-1992 (2001).
[63]
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: IEEE Symposium on Switching and Automata Theory (SWAT 1971), pp. 188-191. IEEE Press, Los Alamitos (1971).
[64]
Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20, 1211-1214 (1971).
[65]
Nicaud, C.: Average state complexity of operations on unary automata. In: Kutyłowski, M., Wierzbicki, T., Pacholski, L. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 231-240. Springer, Heidelberg (1999).
[66]
Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal's function. Int. J. Found. Comput. Sci. 13, 145-159 (2002).
[67]
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114-125 (1959).
[68]
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Symposium on Theory of Computing (STOC 1978), pp. 275-286. ACM Press, New York (1978).
[69]
Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320, 315-329 (2004).
[70]
Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets. J. Autom., Lang. Comb. 2, 177-186 (1997).
[71]
Schnitger, G.: Regular expressions and NFAs without Ɛ-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 432-443. Springer, Heidelberg (2006).
[72]
Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3, 198-200 (1959).
[73]
Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. System Sci. 21, 195-202 (1980).
[74]
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Symposium on Theory of Computing (STOC 1973), pp. 1-9. ACM Press, New York (1973).
[75]
Tamm, H.: On transition minimality of bideterministic automata. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 411-421. Springer, Heidelberg (2007).
[76]
Yu, S.: Regular languages. In: Handbook of Formal Languages, vol. 1, pp. 41-110. Springer, Heidelberg (1997).
[77]
Yu, S.: State complexity of regular languages. J. Autom., Lang. Comb. 6, 221-234 (2001).
[78]
Yu, S.: State complexity of finite and infinite regular languages. Bull. EATCS 76, 142-152 (2002).
[79]
Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315-328 (1994).

Cited By

View all
  • (2011)Descriptional complexity of unambiguous nested word automataProceedings of the 5th international conference on Language and automata theory and applications10.5555/2022896.2022931(414-426)Online publication date: 26-May-2011
  • (2011)Limitations of lower bound methods for deterministic nested word automataInformation and Computation10.1016/j.ic.2010.11.021209:3(580-589)Online publication date: 1-Mar-2011
  • (2009)Operational state complexity of nested word automataTheoretical Computer Science10.1016/j.tcs.2009.05.002410:35(3290-3302)Online publication date: 1-Aug-2009
  1. Nondeterministic Finite Automata--Recent Results on the Descriptional and Computational Complexity

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata
    July 2008
    287 pages
    ISBN:9783540708438

    Publisher

    Springer-Verlag

    Berlin, Heidelberg

    Publication History

    Published: 21 July 2008

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 30 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2011)Descriptional complexity of unambiguous nested word automataProceedings of the 5th international conference on Language and automata theory and applications10.5555/2022896.2022931(414-426)Online publication date: 26-May-2011
    • (2011)Limitations of lower bound methods for deterministic nested word automataInformation and Computation10.1016/j.ic.2010.11.021209:3(580-589)Online publication date: 1-Mar-2011
    • (2009)Operational state complexity of nested word automataTheoretical Computer Science10.1016/j.tcs.2009.05.002410:35(3290-3302)Online publication date: 1-Aug-2009

    View Options

    View options

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media