{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:58:49Z","timestamp":1743127129386,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411132"},{"type":"electronic","value":"9783319411149"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41114-9_4","type":"book-chapter","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T10:05:14Z","timestamp":1467021914000},"page":"45-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection"],"prefix":"10.1007","author":[{"given":"Rafaela","family":"Bastos","sequence":"first","affiliation":[]},{"given":"Sabine","family":"Broda","sequence":"additional","affiliation":[]},{"given":"Ant\u00f3nio","family":"Machiavelo","sequence":"additional","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V Antimirov","year":"1996","unstructured":"Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155(2), 291\u2013319 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Antimirov, V.M., Mosses, P.D.: Rewriting extended regular expressions. In: Rozenberg, G., Salomaa, A. (eds.) 1st DLT. pp. 195\u2013209. World Scientific (1994)","DOI":"10.1016\/0304-3975(95)80024-4"},{"key":"4_CR3","unstructured":"Bastos, R.: Manipulation of Extended Regular Expressions with Derivatives. Master\u2019s thesis, Faculdade de Ci\u00eancias da Universidade do Porto (2015)"},{"issue":"7","key":"4_CR4","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. Int. J. Found. Comput. Sci. 22(7), 1593\u20131606 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"4_CR5","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)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2014.02.013","volume":"528","author":"S Broda","year":"2014","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)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-319-19225-3_2","volume-title":"Descriptional Complexity of Formal Systems","author":"S Broda","year":"2015","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Partial derivative automaton for regular expressions with shuffle. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 21\u201332. Springer, Heidelberg (2015)"},{"issue":"4","key":"4_CR8","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"JA Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. JACM 11(4), 481\u2013494 (1964)","journal-title":"JACM"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-21254-3_13","volume-title":"Language and Automata Theory and Applications","author":"P Caron","year":"2011","unstructured":"Caron, P., Champarnaud, J.-M., Mignot, L.: Partial derivatives of an extended regular expression. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 179\u2013191. Springer, Heidelberg (2011)"},{"issue":"3","key":"4_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1051\/ita\/2014010","volume":"48","author":"P Caron","year":"2014","unstructured":"Caron, P., Champarnaud, J., Mignot, L.: A general framework for the derivation of regular expressions. RAIRO - Theor. Inf. Appl. 48(3), 281\u2013305 (2014)","journal-title":"RAIRO - Theor. Inf. Appl."},{"issue":"3","key":"4_CR11","first-page":"195","volume":"45","author":"JM Champarnaud","year":"2001","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inform. 45(3), 195\u2013205 (2001)","journal-title":"Fundam. Inform."},{"key":"4_CR12","volume-title":"Programming Perl","author":"T Christiansen","year":"2012","unstructured":"Christiansen, T., Foy, B.D., Wall, L., Orwant, J.: Programming Perl, 4th edn. O\u2019Reilly Media, Sebastopol (2012)","edition":"4"},{"key":"4_CR13","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2008","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. CUP, Cambridge (2008)"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-10003-2_74","volume-title":"Automata, Languages and Programming","author":"M F\u00fcrer","year":"1980","unstructured":"F\u00fcrer, M.: The complexity of the inequivalence problem for regular expressions with intersection. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 234\u2013245. Springer, Heidelberg (1980)"},{"issue":"31\u201333","key":"4_CR15","doi-asserted-by":"publisher","first-page":"2987","DOI":"10.1016\/j.tcs.2010.04.036","volume":"411","author":"W Gelade","year":"2010","unstructured":"Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. Theoret. Comput. Sci. 411(31\u201333), 2987\u20132998 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR16","series-title":"LIPIcs","first-page":"325","volume-title":"25th STACS","author":"W Gelade","year":"2008","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) 25th STACS. LIPIcs, vol. 1, pp. 325\u2013336. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2008)"},{"key":"4_CR17","unstructured":"Gruber, H.: On the descriptional and algorithmic complexity of regular languages. Ph.D. thesis, Justus Liebig University Giessen (2010)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-70583-3_4","volume-title":"Automata, Languages and Programming","author":"H Gruber","year":"2008","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 39\u201350. Springer, Heidelberg (2008)"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","volume":"40","author":"T Jiang","year":"1991","unstructured":"Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Inf. Process. Lett. 40(1), 25\u201331 (1991)","journal-title":"Inf. Process. Lett."},{"key":"4_CR20","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."},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/3-540-45841-7_42","volume-title":"STACS 2002","author":"H Petersen","year":"2002","unstructured":"Petersen, H.: The membership problem for regular expressions with intersection is complete in LOGCFL. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 513\u2013522. Springer, Heidelberg (2002)"},{"key":"4_CR22","first-page":"231","volume":"89","author":"K Sen","year":"2003","unstructured":"Sen, K., Rosu, G.: Generating optimal monitors for extended regular expressions. Electr. Notes Theor. Comput. Sci. 89, 231\u2013250 (2003)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"4_CR23","volume-title":"RELAX NG","author":"E van der Vlist","year":"2003","unstructured":"van der Vlist, E.: RELAX NG. O\u2019Reilly Media, Cambridge (2003)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41114-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T06:48:58Z","timestamp":1656744538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41114-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411132","9783319411149"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41114-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}