{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:20:01Z","timestamp":1777105201640,"version":"3.51.4"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319602516","type":"print"},{"value":"9783319602523","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_3","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T14:59:13Z","timestamp":1496415553000},"page":"33-44","source":"Crossref","is-referenced-by-count":5,"title":["Descriptional Complexity and Operations \u2013 Two Non-classical Cases"],"prefix":"10.1007","author":[{"given":"J\u00fcrgen","family":"Dassow","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of ACM Symposium on Theory of Computing, pp. 202\u2013211 (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"3_CR2","unstructured":"Champarnaud, J.-M., Coulon, F.: B\u00fcchi automata reduction by means of left and right trace inclusion preorder. Manuscript (2004)"},{"key":"3_CR3","first-page":"55","volume":"21","author":"J Dassow","year":"2016","unstructured":"Dassow, J.: On the number of accepting states of finite automata. J. Automata Lang. Comb. 21, 55\u201367 (2016)","journal-title":"J. Automata Lang. Comb."},{"key":"3_CR4","first-page":"35","volume":"83","author":"J Dassow","year":"2008","unstructured":"Dassow, J., Stiebe, R.: Nonterminal complexity of some operations on context-free languages. Fundam. Inform. 83, 35\u201349 (2008)","journal-title":"Fundam. Inform."},{"key":"3_CR5","first-page":"123","volume":"17","author":"J Dassow","year":"2012","unstructured":"Dassow, J., Harbich, R.: Descriptional complexity of union and star on context-free languages. J. Automata Lang. Comb. 17, 123\u2013143 (2012)","journal-title":"J. Automata Lang. Comb."},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-319-23111-2_4","volume-title":"Machines, Computations, and Universality","author":"F Drewes","year":"2015","unstructured":"Drewes, F., Holzer, M., Jakobi, S., van der Merwe, B.: Tight bounds for cut-operations on deterministic finite automata. In: Durand-Lose, J., Nagy, B. (eds.) MCU 2015. LNCS, vol. 9288, pp. 45\u201360. Springer, Cham (2015). doi: 10.1007\/978-3-319-23111-2_4"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11691617_1","volume-title":"Model Checking Software","author":"S Edelkamp","year":"2006","unstructured":"Edelkamp, S., Jabbar, S.: Large-scale directed model checking LTL. In: Valmari, A. (ed.) SPIN 2006. LNCS, vol. 3925, pp. 1\u201318. Springer, Heidelberg (2006). doi: 10.1007\/11691617_1"},{"key":"3_CR8","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A review on state complexity of individual operations. Technical report series DCC-2011-08, Version 1.1, University of Porto, Faculty of Sciences, Department of Computer Science (2012), September 2012"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.3233\/FI-2011-533","volume":"110","author":"Y Gao","year":"2011","unstructured":"Gao, Y., Salomaa, K., Yu, S.: Transition complexity of incomplete DFAs. Fundam. Inform. 110, 143\u2013158 (2011)","journal-title":"Fundam. Inform."},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/S0019-9958(69)90055-2","volume":"14","author":"J Gruska","year":"1969","unstructured":"Gruska, J.: Some classifications of context-free languages. Inf. Control 14, 152\u2013179 (1969)","journal-title":"Inf. Control"},{"key":"3_CR11","first-page":"213","volume":"8","author":"J Gruska","year":"1972","unstructured":"Gruska, J.: On the size of context free grammars. Kybernetika 8, 213\u2013218 (1972)","journal-title":"Kybernetika"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"2537","DOI":"10.1016\/j.tcs.2008.12.054","volume":"410","author":"Y-S Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoret. Comput. Sci. 410, 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR13","unstructured":"Harbich, R.: Regel- und Symbolkomplexit\u00e4t kontextfreier Sprachen unter ausgew\u00e4hlten Operationen. Dissertation (2018)"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-44977-9_14","volume-title":"Implementation and Application of Automata","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148\u2013157. Springer, Heidelberg (2003). doi: 10.1007\/3-540-44977-9_14"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1142\/S0129054109006747","volume":"20","author":"M Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata - recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci. 20, 563\u2013580 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR16","unstructured":"Hricko, M., Jir\u00e1skov\u00e1, G., Szabari, A.: Union and intersection of regular languages and descriptional complexity. In: Mereghetti, C., Palano, B., Pighizzini, G., Wotschke, D. (eds.) Proceedings of 7th International Workshop of Descriptional Complexity of Formal Systems, University of Milano, pp. 170\u2013181 (2005)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-85780-8_34","volume-title":"Developments in Language Theory","author":"G Jir\u00e1skov\u00e1","year":"2008","unstructured":"Jir\u00e1skov\u00e1, G.: On the state complexity of complements, stars, and reversals of regular languages. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 431\u2013442. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85780-8_34"},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"197","DOI":"10.4204\/EPTCS.31.22","volume":"31","author":"G Jir\u00e1skov\u00e1","year":"2010","unstructured":"Jir\u00e1skov\u00e1, G., Krausov\u00e1, M.: Complexity in prefix-free regular languages. Electron. Proc. Theor. Comput. Sci. 31, 197\u2013204 (2010)","journal-title":"Electron. Proc. Theor. Comput. Sci."},{"key":"3_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2015.08.004","volume":"244","author":"E Maia","year":"2015","unstructured":"Maia, E., Moreira, N., Reis, R.: Incomplete operational transition complexity of regular languages. Inf. Comput. 244, 1\u201322 (2015)","journal-title":"Inf. Comput."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.jcss.2017.02.001","volume":"86","author":"A Okhotin","year":"2017","unstructured":"Okhotin, A., Salomaa, K.: State complexity of operations on input-driven pushdown automata. J. Comput. Syst. Sci. 86, 207\u2013228 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1016\/j.tcs.2009.05.002","volume":"410","author":"X Piao","year":"2009","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci. 410, 3250\u20133260 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.tcs.2011.12.048","volume":"429","author":"X Piao","year":"2012","unstructured":"Piao, X., Salomaa, K.: State complexity of the concatenation of regular tree automata. Theoret. Comput. Sci. 429, 273\u2013281 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-642-31623-4_22","volume-title":"Descriptional Complexity of Formal Systems","author":"X Piao","year":"2012","unstructured":"Piao, X., Salomaa, K.: State complexity of projection and quotient on unranked trees. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 280\u2013293. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31623-4_22"},{"key":"3_CR24","volume-title":"Handbook of Formal Languages","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. I\u2013III. Springer, Berlin (1997)"},{"key":"3_CR25","first-page":"221","volume":"6","author":"S Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Automata Lang. Comb. 6, 221\u2013234 (2001)","journal-title":"J. Automata Lang. Comb."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60252-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,9]],"date-time":"2020-10-09T09:31:35Z","timestamp":1602235895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}