×

A hitchhiker’s guide to descriptional complexity through analytic combinatorics. (English) Zbl 1308.68070

Summary: Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several \(\varepsilon\)-NFA constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the \(\varepsilon\)-NFA constructions approaches the corresponding \(\varepsilon\)-free NFA construction, asymptotically and on average.

MSC:

68Q45 Formal languages and automata
68R05 Combinatorics in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison Wesley · Zbl 0326.68005
[2] Almeida, M.; Moreira, N.; Reis, R., Enumeration and generation with a string automata representation, Special issue “Selected Papers of DCFS 2006”. Special issue “Selected Papers of DCFS 2006”, Theoret. Comput. Sci., 387, 2, 93-102 (2007) · Zbl 1143.68031
[3] Bassino, F.; David, J.; Nicaud, C., Average case analysis of Moore’s state minimization algorithm, Algorithmica, 63, 1-2, 509-531 (2012) · Zbl 1291.68176
[4] Bassino, F.; Giambruno, L.; Nicaud, C., The average state complexity of rational operations on finite languages, Internat. J. Found. Comput. Sci., 21, 4, 495-516 (2010) · Zbl 1205.68189
[5] Bassino, F.; Nicaud, C., Enumeration and random generation of accessible automata, Theoret. Comput. Sci., 381, 1-3, 86-104 (2007) · Zbl 1188.68168
[6] Broda, S.; Machiavelo, A.; Moreira, N.; Reis, R., On the average state complexity of partial derivative automata, Internat. J. Found. Comput. Sci., 22, 7, 1593-1606 (2011) · Zbl 1252.68166
[7] Broda, S.; Machiavelo, A.; Moreira, N.; Reis, R., On the average size of Glushkov and partial derivative automata, Internat. J. Found. Comput. Sci., 23, 5, 969-984 (2012) · Zbl 1262.68085
[8] Brzozowski, J., In search of most complex regular languages, (Moreira, N.; Reis, R., Proceedings of the 17th International Conference on Implementation and Application of Automata, CIAA 2012. Proceedings of the 17th International Conference on Implementation and Application of Automata, CIAA 2012, LNCS, vol. 7381 (2012), Springer: Springer Porto, Portugal), 5-24 · Zbl 1297.68108
[9] Brzozowski, J. A., Quotient complexity of regular languages, J. Autom. Lang. Comb., 15, 1/2, 71-89 (2010) · Zbl 1345.68200
[10] Domaratzki, M., State complexity of proportional removals, J. Autom. Lang. Comb., 7, 4, 455-468 (2002) · Zbl 1095.68605
[11] Domaratzki, M.; Kisman, D.; Shallit, J., On the number of distinct languages accepted by finite automata with \(n\) states, J. Autom. Lang. Comb., 7, 4, 469-486 (2002) · Zbl 1137.68421
[12] Ellul, K.; Krawetz, B.; Shallit, J.; Wang, M.-W., Regular expressions: New results and open problems, J. Autom. Lang. Comb., 10, 4, 407-437 (2005) · Zbl 1143.68434
[13] Felice, S. D.; Nicaud, C., Brzozowski algorithm is generically super-polynomial for deterministic automata, (Béal, M.-P.; Carton, O., Proceedings of the 17th International Conference on Developments in Language Theory, DLT 2013. Proceedings of the 17th International Conference on Developments in Language Theory, DLT 2013, LNCS, vol. 7907 (2013), Springer: Springer Marne-la-Vallée, France), 179-190 · Zbl 1381.68113
[14] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2008), Cambridge University Press
[15] Goldstine, J.; Kappes, M.; Kintala, C. M.R.; Leung, H.; Malcher, A.; Wotschke, D., Descriptional complexity of machines with limited resources, J. UCS, 8, 2, 193-234 (2002) · Zbl 1258.68058
[16] Gruber, H.; Gulan, S., Simplifying regular expressions, (Dediu, A. H.; Fernau, H.; Martín-Vide, C., Proceedings of the 4th International Conference on Language and Automata Theory and Applications, LATA 2010. Proceedings of the 4th International Conference on Language and Automata Theory and Applications, LATA 2010, LNCS, vol. 6031 (2010), Springer: Springer Trier, Germany), 285-296 · Zbl 1284.68351
[17] Gruber, H.; Holzer, M., On the average state and transition complexity of finite languages, Theoret. Comput. Sci., 387, 2, 155-166 (2007) · Zbl 1148.68030
[18] Gruber, H.; Lee, J.; Shallit, J., Enumerating regular expressions and their languages · Zbl 1115.68444
[19] Gulan, S.; Fernau, H., An optimal construction of finite automata from regular expressions, (Hariharan, R.; Mukund, M.; Vinay, V., IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, LIPIcs, vol. 2 (2008), Schloss Dagstuhl, Leibniz-Zentrum für Informatik), 211-222 · Zbl 1248.68297
[20] Holzer, M.; Kutrib, M., The complexity of regular(-like) expressions, (Gao, Y.; Lu, H.; Seki, S.; Yu, S., Proceedings of the 14th International Conference on Developments in Language Theory, DLT 2010. Proceedings of the 14th International Conference on Developments in Language Theory, DLT 2010, LNCS, vol. 6224 (2010), Springer: Springer London, Ontario, CA), 16-30 · Zbl 1250.68160
[21] Holzer, M.; Kutrib, M., Descriptional complexity - An introductory survey, (Martín-Vide, C., Scientific Applications of Language Methods (2010), World Scientific), 1-58 · Zbl 1227.68033
[22] Holzer, M.; Kutrib, M., The complexity of regular(-like) expressions, Internat. J. Found. Comput. Sci., 7, 22, 1533-1548 (2011) · Zbl 1252.68174
[23] Holzer, M.; Kutrib, M., Descriptional and computational complexity of finite automata - A survey, Inform. and Comput., 209, 3, 456-470 (2011) · Zbl 1217.68130
[24] Hromkovic, J., Descriptional complexity of finite automata: Concepts and open problems, J. Autom. Lang. Comb., 7, 4, 519-531 (2002) · Zbl 1094.68576
[25] Ilie, L.; Yu, S., Follow automata, Inform. and Comput., 186, 1, 140-162 (2003) · Zbl 1059.68063
[26] Knuth, D. E., The Art of Computer Programming, vol. I: Fundamental Algorithms (1973), Addison Wesley
[27] Knuth, D. E., The Art of Computer Programming, vol. III: Sorting and Searching (1973), Addison Wesley · Zbl 0302.68010
[28] Knuth, D. E., The Art of Computer Programming, vol. II: Seminumerical Algorithms (1981), Addison Wesley · Zbl 0477.65002
[29] Nicaud, C., Average state complexity of operations on unary automata, (Kurylowski, M.; Pacholski, L.; Wierzbicki, T., Proceedings of the 24th Symposium, Mathematical Foundations of Computer Science, MFCS 1999. Proceedings of the 24th Symposium, Mathematical Foundations of Computer Science, MFCS 1999, LNCS, vol. 1672 (1999), Springer), 231-240 · Zbl 0955.68068
[30] Nicaud, C., On the average size of Glushkov’s automata, (Dediu, A. H.; Ionescu, A.-M.; Martín-Vide, C., Proceedings of the 3rd International Conference on Language and Automata Theory and Applications, LATA 2009. Proceedings of the 3rd International Conference on Language and Automata Theory and Applications, LATA 2009, LNCS, vol. 5457 (2009), Springer), 626-637 · Zbl 1234.68232
[31] Sedgewick, R.; Flajolet, P., Analysis of Algorithms (1996), Addison Wesley
[32] Sippu, S.; Soisalon-Soininen, E., Parsing Theory, vol. II: (LR \((k)\) and LL \((k)\), Parsing of EATCS Monographs on Theoretical Computer Science (1990), Springer · Zbl 0703.68071
[33] Thompson, K., Regular expression search algorithm, Commun. ACM, 11, 6, 410-422 (1968) · Zbl 0164.46205
[34] Yu, S., State complexity: Recent results and open problems, Fund. Inform., 64, 1-4, 471-480 (2005) · Zbl 1102.68076
[35] Yu, S.; Gao, Y., State complexity research and approximation, (Mauri, G.; Leporati, A., Proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011. Proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011, Milano, Italy. Proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011. Proceedings of the 15th International Conference on Developments in Language Theory, DLT 2011, Milano, Italy, LNCS, vol. 6795 (2011)), 46-57 · Zbl 1221.68151
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.