{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:46Z","timestamp":1759638466451,"version":"3.41.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319537320"},{"type":"electronic","value":"9783319537337"}],"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-53733-7_19","type":"book-chapter","created":{"date-parts":[[2017,2,15]],"date-time":"2017-02-15T10:39:21Z","timestamp":1487155161000},"page":"261-272","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited"],"prefix":"10.1007","author":[{"given":"Hellis","family":"Tamm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brink","family":"van der Merwe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,16]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"JC Birget","year":"1992","unstructured":"Birget, J.C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43, 185\u2013190 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"19_CR2","doi-asserted-by":"crossref","first-page":"293","DOI":"10.14232\/actacyb.22.2.2015.4","volume":"22","author":"J Brzozowski","year":"2015","unstructured":"Brzozowski, J., Davies, S.: Quotient complexities of atoms in regular ideal languages. Acta Cybernetica 22(2), 293\u2013311 (2015)","journal-title":"Acta Cybernetica"},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.016","volume":"539","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Tamm, H.: Theory of \u00e1tomata. Theoret. Comput. Sci. 539, 13\u201327 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"339","DOI":"10.3233\/FUN-2002-51402","volume":"51","author":"F Denis","year":"2002","unstructured":"Denis, F., Lemay, A., Terlutte, A.: Residual finite state automata. Fundamenta Informaticae 51, 339\u2013368 (2002)","journal-title":"Fundamenta Informaticae"},{"key":"19_CR5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0020-0190(96)00095-6","volume":"59","author":"I Glaister","year":"1996","unstructured":"Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata. Inf. Process. Lett. 59, 75\u201377 (1996)","journal-title":"Inf. Process. Lett."},{"key":"19_CR6","unstructured":"Gruber, H.: On the descriptional and algorithmic complexity of regular languages. Ph.D. thesis, Gie\u00dfener dissertation, Fachbereich Mathematik und Informatik, Physik, Geographie, Justus-Liebig-Universit\u00e4t Gie\u00dfen (D26) (2009)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/11779148_33","volume-title":"Developments in Language Theory","author":"H Gruber","year":"2006","unstructured":"Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 363\u2013374. Springer, Heidelberg (2006). doi: 10.1007\/11779148_33"},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.ipl.2016.01.003","volume":"116","author":"S Iv\u00e1n","year":"2016","unstructured":"Iv\u00e1n, S.: Complexity of atoms, combinatorially. Inf. Process. Lett. 116, 356\u2013360 (2016)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"19_CR9","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1142\/S012905419100011X","volume":"2","author":"T Jiang","year":"1991","unstructured":"Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFA\u2019s over a unary alphabet. Int. J. Found. Comput. Sci. 2(2), 163\u2013182 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"7","key":"19_CR10","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1109\/T-C.1970.222994","volume":"C\u201319","author":"T Kameda","year":"1970","unstructured":"Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Trans. Comput. C\u201319(7), 617\u2013627 (1970)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"19_CR11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1051\/ita:2008022","volume":"43","author":"M Latteux","year":"2009","unstructured":"Latteux, M., Roos, Y., Terlutte, A.: Minimal NFA and biRFSA languages. RAIRO\u00a0- Theoret. Inform. Appl. 43(2), 221\u2013237 (2009)","journal-title":"RAIRO\u00a0- Theoret. Inform. Appl."},{"key":"19_CR12","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc. 9, 541\u2013544 (1958)","journal-title":"Proc. Am. Math. Soc."},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tcs.2004.02.032","volume":"320","author":"A Salomaa","year":"2004","unstructured":"Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theoret. Comput. Sci. 320, 315\u2013329 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.3233\/FI-2012-681","volume":"116","author":"A Salomaa","year":"2012","unstructured":"Salomaa, A.: Mirror images and schemes for the maximal complexity of nondeterminism. Fundamenta Informaticae 116, 237\u2013249 (2012)","journal-title":"Fundamenta Informaticae"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/978-3-642-13089-2_48","volume-title":"Language and Automata Theory and Applications","author":"H Tamm","year":"2010","unstructured":"Tamm, H.: Some minimality results on biresidual and biseparable automata. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 573\u2013584. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13089-2_48"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-319-19225-3_23","volume-title":"Descriptional Complexity of Formal Systems","author":"H Tamm","year":"2015","unstructured":"Tamm, H.: Generalization of the double-reversal method of finding a canonical residual finite state automaton. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 268\u2013279. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-19225-3_23"},{"key":"19_CR17","unstructured":"Tamm, H.: New interpretation and generalization of the Kameda-Weiner method. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 116:1\u2013116:12. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2016)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53733-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T11:16:50Z","timestamp":1749986210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53733-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319537320","9783319537337"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53733-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}