{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T08:01:49Z","timestamp":1768809709810,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00236-021-00399-6","type":"journal-article","created":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T09:05:06Z","timestamp":1626685506000},"page":"357-375","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the size of partial derivatives and the word membership problem"],"prefix":"10.1007","volume":"58","author":[{"given":"Stavros","family":"Konstantinidis","sequence":"first","affiliation":[]},{"given":"Ant\u00f3nio","family":"Machiavelo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-0105","authenticated-orcid":false,"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"399_CR1","doi-asserted-by":"publisher","unstructured":"Adams, M.D., Hollenbeck, C., Might, M.: On the complexity and performance of parsing with derivatives. In: Krintz, C., Berger, E. (eds.) Proceedings of the 37th ACM SIGPLAN PLDI, pp. 224\u2013236. ACM (2016). https:\/\/doi.org\/10.1145\/2908080.2908128","DOI":"10.1145\/2908080.2908128"},{"issue":"2","key":"399_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"VM Antimirov","year":"1996","unstructured":"Antimirov, V.M.: Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155(2), 291\u2013319 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"399_CR3","doi-asserted-by":"publisher","unstructured":"Backurs, A., Indyk, P.: Which regular expression patterns are hard to match? In: Dinur, I. (ed.) Proceedings of the 57th FOCS, pp. 457\u2013466. IEEE Computer Society (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.56","DOI":"10.1109\/FOCS.2016.56"},{"key":"399_CR4","doi-asserted-by":"publisher","unstructured":"Bille, P., Thorup, M.: Faster regular expression matching. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Proceedings of the 36th ICALP, Part I, LNCS, vol. 5555, pp. 171\u2013182. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_16","DOI":"10.1007\/978-3-642-02927-1_16"},{"key":"399_CR5","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Gr\u00f8nlund, A., Larsen, K.G.: A dichotomy for regular expression membership testing. In: Umans, C. (ed.) Proceedings of the 58th FOCS, pp. 307\u2013318. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.36","DOI":"10.1109\/FOCS.2017.36"},{"key":"399_CR6","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ic.2019.01.003","volume":"265","author":"S Broda","year":"2019","unstructured":"Broda, S., Holzer, M., Maia, E., Moreira, N., Reis, R.: Mesh of automata. Inf. Comput. 265, 94\u2013111 (2019). https:\/\/doi.org\/10.1016\/j.ic.2019.01.003","journal-title":"Inf. Comput."},{"issue":"7","key":"399_CR7","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1142\/S0129054111008908","volume":"22","author":"S Broda","year":"2011","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative automata: an analytic combinatorics approach. Int. J. Found. Comput. Sci. 22(7), 1593\u20131606 (2011). https:\/\/doi.org\/10.1142\/S0129054111008908","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"399_CR8","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1142\/S0129054112400400","volume":"23","author":"S Broda","year":"2012","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average size of Glushkov and partial derivative automata. Int. J. Found. Comput. Sci. 23(5), 969\u2013984 (2012). https:\/\/doi.org\/10.1142\/S0129054112400400","journal-title":"Int. J. Found. Comput. Sci."},{"key":"399_CR9","doi-asserted-by":"crossref","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: A Hitchhiker\u2019s guide to descriptional complexity through analytic combinatorics. Theoret. Comput. Sci. 528, 85\u2013100 (2014)","DOI":"10.1016\/j.tcs.2014.02.013"},{"issue":"6\u20137","key":"399_CR10","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1142\/S0129054119400227","volume":"30","author":"S Broda","year":"2019","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On average behaviour of regular expressions in strong star normal form. Int. J. Found. Comput. Sci. 30(6\u20137), 899\u2013920 (2019). https:\/\/doi.org\/10.1142\/S0129054119400227","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"399_CR11","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/3388392.3388400","volume":"51","author":"S Broda","year":"2020","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Analytic combinatorics and descriptional complexity of regular languages on average. ACM SIGACT News 51(1), 38\u201356 (2020). https:\/\/doi.org\/10.1145\/3388392.3388400","journal-title":"ACM SIGACT News"},{"key":"399_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"48","author":"A Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theoret. Comput. Sci. 48, 197\u2013213 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"399_CR13","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1142\/S0218196701000772","volume":"11","author":"J Champarnaud","year":"2001","unstructured":"Champarnaud, J., Ziadi, D.: From c-continuations to new quadratic algorithms for automaton synthesis. Int. J. Alg. Comput. 11(6), 707\u2013736 (2001). https:\/\/doi.org\/10.1142\/S0218196701000772","journal-title":"Int. J. Alg. Comput."},{"issue":"1","key":"399_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1142\/S021819670700355X","volume":"17","author":"JM Champarnaud","year":"2007","unstructured":"Champarnaud, J.M., Ouardi, F., Ziadi, D.: Normalized expressions and finite automata. Int. J. Algebra Comput. 17(1), 141\u2013154 (2007). https:\/\/doi.org\/10.1142\/S021819670700355X","journal-title":"Int. J. Algebra Comput."},{"key":"399_CR15","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inform. 45(3), 195\u2013205 (2001)"},{"key":"399_CR16","volume-title":"Sampling Techniques","author":"WG Cochran","year":"1977","unstructured":"Cochran, W.G.: Sampling Techniques, 3rd edn. Wiley, New York (1977)","edition":"3"},{"key":"399_CR17","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2008","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. CUP, Cambridge (2008)"},{"key":"399_CR18","unstructured":"Gulan, S.: On the relative descriptional complexity of regular expressions and finite automata. Ph.D. thesis, Universit\u00e4t Trier (2011)"},{"key":"399_CR19","doi-asserted-by":"crossref","unstructured":"Hille, E.: Analytic Function Theory, vol.\u00a02. Blaisdell Publishing Company (1962)","DOI":"10.1063\/1.3057867"},{"issue":"3","key":"399_CR20","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.jda.2007.10.003","volume":"6","author":"A Khorsi","year":"2008","unstructured":"Khorsi, A., Ouardi, F., Ziadi, D.: Fast equation automaton computation. J. Discrete Algorithms 6(3), 433\u2013448 (2008). https:\/\/doi.org\/10.1016\/j.jda.2007.10.003","journal-title":"J. Discrete Algorithms"},{"key":"399_CR21","doi-asserted-by":"publisher","unstructured":"Konstantinidis, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative transducers. In: Chatzigeorgiou, A., Dondi, R., Herodotou, H., Kapoutsis, C.A., Manolopoulos, Y., Papadopoulos, G.A., Sikora, F. (eds.) Proceedings of the SOFSEM 2020, LNCS, vol. 12011, pp. 174\u2013186. Springer, Berlin (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_15","DOI":"10.1007\/978-3-030-38919-2_15"},{"key":"399_CR22","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"399_CR23","first-page":"51","volume":"5","author":"BG Mirkin","year":"1966","unstructured":"Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 51\u201357 (1966)","journal-title":"Eng. Cybern."},{"issue":"2","key":"399_CR24","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"EW Myers","year":"1992","unstructured":"Myers, E.W.: A four Russians algorithm for regular expression pattern matching. J. ACM 39(2), 430\u2013448 (1992). https:\/\/doi.org\/10.1145\/128749.128755","journal-title":"J. ACM"},{"key":"399_CR25","doi-asserted-by":"crossref","unstructured":"Nicaud, C.: On the average size of Glushkov\u2019s automata. In: Dediu, A., Ionescu, A.M., Vide, C.M. (eds.) Proceedings of the 3rd LATA, LNCS, vol. 5457, pp. 626\u2013637. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-00982-2_53"},{"key":"399_CR26","unstructured":"Project\u00a0FAdo: tools for formal languages manipulation. http:\/\/fado.dcc.fc.up.pt. Accessed date 1 Jan 2021"},{"issue":"6","key":"399_CR27","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Regular expression search algorithm. CACM 11(6), 410\u2013422 (1968)","journal-title":"CACM"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00399-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00399-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00399-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T21:45:58Z","timestamp":1672868758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00399-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["399"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00399-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"5 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}