{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:10:24Z","timestamp":1771024224675,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T00:00:00Z","timestamp":1583971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2020,3,12]]},"abstract":"<jats:p>Average-case complexity results provide important information about computational models and methods, as worst-case scenarios usually occur for a negligible amount of cases. The framework of analytic combinatorics provides an elegant tool for that analysis, completely avoiding the use of statistical methods, by relating combinatorial objects to algebraic properties of complex analytic generating functions. We have previously used this framework to study the average size of di erent nondeterministic nite automata simulations of regular expressions. In some cases it was not feasible to obtain explicit expressions for the generating functions involved, and we had to resort to Puiseux expansions. This is particularly important when dealing with families of generating functions indexed by a parameter, e.g. the size of underlying alphabets, and when the corresponding generating functions are obtained by algebraic curves of degree higher than two. In this paper we expound our approach in a tutorial pace, providing sufficient details to make it available to the reader.<\/jats:p>","DOI":"10.1145\/3388392.3388401","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T22:34:37Z","timestamp":1584052477000},"page":"38-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Guest Column"],"prefix":"10.1145","volume":"51","author":[{"given":"Sabine","family":"Broda","sequence":"first","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ciencias da Universidade do Porto, Rua do Campo Alegre, Porto, Portugal"}]},{"given":"Antonio","family":"Machiavelo","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ciencias da Universidade do Porto, Rua do Campo Alegre, Porto, Portugal"}]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ciencias da Universidade do Porto, Rua do Campo Alegre, Porto, Portugal"}]},{"given":"Rogerio","family":"Reis","sequence":"additional","affiliation":[{"name":"CMUP &amp; DM-DCC, Faculdade de Ciencias da Universidade do Porto, Rua do Campo Alegre, Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2020,3,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[ABR] J. Abbott A. M. Bigatti and L. Robbiano. CoCoA: a system for doing Computations in Commutative Algebra. Available at http:\/\/cocoa.dima.unige.it.  [ABR] J. Abbott A. M. Bigatti and L. Robbiano. CoCoA: a system for doing Computations in Commutative Algebra. Available at http:\/\/cocoa.dima.unige.it."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.029"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005930"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_2_1_5_1","volume-title":"On the average complexity of partial derivative automata for semi-extended expressions. Journal of Automata, Languages and Combinatorics, 22(1{3):5{28","author":"Bastos Rafaela","year":"2017","unstructured":"[BBM+17] Rafaela Bastos , Sabine Broda , Ant_onio Machiavelo, Nelma Moreira , and Rog_erio Reis. On the average complexity of partial derivative automata for semi-extended expressions. Journal of Automata, Languages and Combinatorics, 22(1{3):5{28 , 2017 . [BBM+17] Rafaela Bastos, Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. On the average complexity of partial derivative automata for semi-extended expressions. Journal of Automata, Languages and Combinatorics, 22(1{3):5{28, 2017."},{"key":"e_1_2_1_6_1","volume-title":"Average case analysis of Moore's state minimization algorithm. Algorithmica, 63(1--2):509{531","author":"David Julien","year":"2012","unstructured":"[BDN12] Fr_ed_erique Bassino, Julien David , and Cyril Nicaud . Average case analysis of Moore's state minimization algorithm. Algorithmica, 63(1--2):509{531 , 2012 . [BDN12] Fr_ed_erique Bassino, Julien David, and Cyril Nicaud. Average case analysis of Moore's state minimization algorithm. Algorithmica, 63(1--2):509{531, 2012."},{"key":"e_1_2_1_7_1","unstructured":"[BDS12] Fr_ed_erique Bassino Julien\n      David and \n      Andrea\n      Sportiello\n    .\n  Asymptotic enumeration of minimal automata\n  . In Christoph Durr and Thomas Wilke editors 29th STACS \n  2012 Paris France volume \n  14\n   of \n  LIPIcs pages 88{\n  99\n  . Schloss Dagstuhl { Leibniz-Zentrum fur Informatik 2012.  [BDS12] Fr_ed_erique Bassino Julien David and Andrea Sportiello. Asymptotic enumeration of minimal automata. In Christoph Durr and Thomas Wilke editors 29th STACS 2012 Paris France volume 14 of LIPIcs pages 88{99. Schloss Dagstuhl { Leibniz-Zentrum fur Informatik 2012."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.01.003"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008908"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112400400"},{"issue":"0","key":"e_1_2_1_12_1","first-page":"100","article-title":"guide to descriptional complexity through analytic combinatorics","volume":"528","author":"Broda Sabine","year":"2014","unstructured":"[BMMR14] Sabine Broda , Ant_onio Machiavelo, Nelma Moreira , and Rog_erio Reis. A hitchhiker's guide to descriptional complexity through analytic combinatorics . Theoret. Comput. Sci. , 528 ( 0 ):85 { 100 , 2014 . [BMMR15] Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. Average size of automata constructions from regular expressions. Bulletin of the European Asso- ciation for Theoretical Computer Science, 116:167{192, June 2015. [BMMR14] Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. A hitchhiker's guide to descriptional complexity through analytic combinatorics. Theoret. Comput. Sci., 528(0):85 { 100, 2014. [BMMR15] Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. Average size of automata constructions from regular expressions. Bulletin of the European Asso- ciation for Theoretical Computer Science, 116:167{192, June 2015.","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"e_1_2_1_13_1","first-page":"173","article-title":"Automata for regular expressions with shu_e","volume":"259","author":"Broda Sabine","year":"2018","unstructured":"[BMMR18a] Sabine Broda , Ant_onio Machiavelo, Nelma Moreira , and Rog_erio Reis . Automata for regular expressions with shu_e . Inf. Comput. , 259 ( 2 ):162{ 173 , 2018 . [BMMR18a] Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. Automata for regular expressions with shu_e. Inf. Comput., 259(2):162{173, 2018.","journal-title":"Inf. Comput."},{"key":"e_1_2_1_14_1","volume-title":"Position automata for semi-extended expressions. Journal of Automata, Languages and Combi- natorics, 23(1{3):39{65","author":"Broda Sabine","year":"2018","unstructured":"[BMMR18b] Sabine Broda , Ant_onio Machiavelo, Nelma Moreira , and Rog_erio Reis. Position automata for semi-extended expressions. Journal of Automata, Languages and Combi- natorics, 23(1{3):39{65 , 2018 . [BMMR18b] Sabine Broda, Ant_onio Machiavelo, Nelma Moreira, and Rog_erio Reis. Position automata for semi-extended expressions. Journal of Automata, Languages and Combi- natorics, 23(1{3):39{65, 2018."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054119400227"},{"key":"e_1_2_1_16_1","volume-title":"Enumeration and random generation of accessible automata. Theoret. Comput. Sci., 381(1--3):86{104","author":"Bassino F.","year":"2007","unstructured":"[BN07] F. Bassino and C. Nicaud . Enumeration and random generation of accessible automata. Theoret. Comput. Sci., 381(1--3):86{104 , 2007 . [BN07] F. Bassino and C. Nicaud. Enumeration and random generation of accessible automata. Theoret. Comput. Sci., 381(1--3):86{104, 2007."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00267-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.10.011"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"[FMR18] \n      Miguel\n      Ferreira Nelma\n      Moreira and Rog_erio Reis.\n  Forward injective _nite automata: Exact and random generation of nonisomorphic NFAs\n  . In Stavros Konstantinidis and Giovanni Pighizzini editors 20th DCFS \n  2018 Halifax NS Canada volume \n  10952\n   of \n  LNCS pages 88{\n  100\n  . Springer 2018.  [FMR18] Miguel Ferreira Nelma Moreira and Rog_erio Reis. Forward injective _nite automata: Exact and random generation of nonisomorphic NFAs. In Stavros Konstantinidis and Giovanni Pighizzini editors 20th DCFS 2018 Halifax NS Canada volume 10952 of LNCS pages 88{100. Springer 2018.","DOI":"10.1007\/978-3-319-94631-3_8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"[FN13] \n      Sven De\n      Felice\n     and \n      Cyril\n      Nicaud\n    .\n  Random generation of deterministic acyclic automata using the recursive method\n  . In Andrei A. Bulatov and Arseny M. Shur editors 8th CSR \n  2013 Ekaterinburg Russia volume \n  7913\n   of \n  LNCS pages 88{\n  99\n  . Springer 2013.  [FN13] Sven De Felice and Cyril Nicaud. Random generation of deterministic acyclic automata using the recursive method. In Andrei A. Bulatov and Arseny M. Shur editors 8th CSR 2013 Ekaterinburg Russia volume 7913 of LNCS pages 88{99. Springer 2013.","DOI":"10.1007\/978-3-642-38536-0_8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"[FS08] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. CUP 2008.  [FS08] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. CUP 2008.","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_24"},{"key":"e_1_2_1_23_1","volume-title":"A singular mathematical promenade. ENS _Editions","author":"Ghys Etienne","year":"2017","unstructured":"[Ghy17] _ Etienne Ghys . A singular mathematical promenade. ENS _Editions , 2017 . [Ghy17] _Etienne Ghys. A singular mathematical promenade. ENS _Editions, 2017."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_26_1","volume-title":"Analytic Function Theory","author":"Hille Einer","year":"1962","unstructured":"[Hil62] Einer Hille . Analytic Function Theory , volume 2 . Blaisdell Publishing Company , 1962 . [Hil62] Einer Hille. Analytic Function Theory, volume 2. Blaisdell Publishing Company, 1962."},{"key":"e_1_2_1_27_1","series-title":"LNCS","first-page":"152","volume-title":"Proc. 20th CIAA","author":"Jean-Luc Joly Pierre-Cyrille","unstructured":"[HJ15] Pierre-Cyrille H_eam and Jean-Luc Joly . On the uniform random generation of non deterministic automata up to isomorphism . In Frank Drewes, editor, Proc. 20th CIAA , volume 9223 of LNCS , pages 140{ 152 . Springer, 2015. [HJ15] Pierre-Cyrille H_eam and Jean-Luc Joly. On the uniform random generation of non deterministic automata up to isomorphism. In Frank Drewes, editor, Proc. 20th CIAA, volume 9223 of LNCS, pages 140{152. Springer, 2015."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1748"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38919-2_15"},{"key":"e_1_2_1_31_1","unstructured":"[Lan01] \n      Serge\n      Lang\n    . Algebra volume \n  211\n   of \n  Grad\n  . Texts Math. \n  Springer 3\n  rd edition 2001\n  .  [Lan01] Serge Lang. Algebra volume 211 of Grad. Texts Math. Springer 3rd edition 2001."},{"key":"e_1_2_1_32_1","series-title":"LNCS","first-page":"267","volume-title":"Mariya Soskova and Victor Mitrana","author":"Maia Eva","unstructured":"[MMR15] Eva Maia , Nelma Moreira , and Rog_erio Reis. Pre_x and right-partial derivative automata. In Mariya Soskova and Victor Mitrana , editors, 11th CiE , volume 9136 of LNCS , pages 258{ 267 . Springer, 2015. [MMR15] Eva Maia, Nelma Moreira, and Rog_erio Reis. Pre_x and right-partial derivative automata. In Mariya Soskova and Victor Mitrana, editors, 11th CiE, volume 9136 of LNCS, pages 258{267. Springer, 2015."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"e_1_2_1_34_1","unstructured":"[Nic00] Cyril Nicaud. _ Etude du comportement en moyenne des automates _nis et des langages rationnels. PhD thesis Universit_e de Paris 7 2000.  [Nic00] Cyril Nicaud. _ Etude du comportement en moyenne des automates _nis et des langages rationnels. PhD thesis Universit_e de Paris 7 2000."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00982-2_53"},{"key":"e_1_2_1_36_1","series-title":"LNCS","first-page":"23","volume-title":"Erzs_ebet Csuhaj-Varj_u, Martin Dietzfelbinger, and Zolt_an _Esik","author":"Nicaud Cyril","unstructured":"[Nic14] Cyril Nicaud . Random deterministic automata . In Erzs_ebet Csuhaj-Varj_u, Martin Dietzfelbinger, and Zolt_an _Esik , editors, MFCS , volume 8634 of LNCS , pages 5{ 23 . Springer, 2014. [Nic14] Cyril Nicaud. Random deterministic automata. In Erzs_ebet Csuhaj-Varj_u, Martin Dietzfelbinger, and Zolt_an _Esik, editors, MFCS, volume 8634 of LNCS, pages 5{23. Springer, 2014."},{"key":"e_1_2_1_37_1","volume-title":"The _Cern_y conjecture holds with high probability. Journal of Automata, Languages and Combinatorics, 24(2--4):343{365","author":"Nicaud Cyril","year":"2019","unstructured":"[Nic19] Cyril Nicaud . The _Cern_y conjecture holds with high probability. Journal of Automata, Languages and Combinatorics, 24(2--4):343{365 , 2019 . [Nic19] Cyril Nicaud. The _Cern_y conjecture holds with high probability. Journal of Automata, Languages and Combinatorics, 24(2--4):343{365, 2019."},{"key":"e_1_2_1_38_1","volume-title":"Addision-Wesley","author":"Sedgewick R.","year":"1996","unstructured":"[SF96] R. Sedgewick and P. Flajolet . Analysis of Algorithms . Addision-Wesley , 1996 . [SF96] R. Sedgewick and P. Flajolet. Analysis of Algorithms. Addision-Wesley, 1996."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_40_1","volume-title":"Princeton University Press","author":"Walker Robert J.","year":"1950","unstructured":"[Wal50] Robert J. Walker . Algebraic Curves . Princeton University Press , 1950 . [Wal50] Robert J. Walker. Algebraic Curves. Princeton University Press, 1950."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511617560"},{"key":"e_1_2_1_42_1","unstructured":"[Yam14] \n      Hiroaki\n      Yamamoto\n    .\n  A new _nite automaton construction for regular expressions\n  . In Suna Bensch Rudolf Freund and Friedrich Otto editors 6th \n  NCMA volume \n  304\n   of \n  books@ocg\n  .at pages 249{\n  264\n  . Osterreichische Computer Gesellschaft 2014.  [Yam14] Hiroaki Yamamoto. A new _nite automaton construction for regular expressions. In Suna Bensch Rudolf Freund and Friedrich Otto editors 6th NCMA volume 304 of books@ocg.at pages 249{264. Osterreichische Computer Gesellschaft 2014."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3388392.3388401","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3388392.3388401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:20Z","timestamp":1750197680000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3388392.3388401"}},"subtitle":["Analytic Combinatorics and Descriptional Complexity of Regular Languages on Average"],"short-title":[],"issued":{"date-parts":[[2020,3,12]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,12]]}},"alternative-id":["10.1145\/3388392.3388401"],"URL":"https:\/\/doi.org\/10.1145\/3388392.3388401","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3,12]]},"assertion":[{"value":"2020-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}