{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:08:19Z","timestamp":1725552499211},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_20","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"208-221","source":"Crossref","is-referenced-by-count":12,"title":["Quotient Complexity of Ideal Languages"],"prefix":"10.1007","author":[{"given":"Janusz","family":"Brzozowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baiyu","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","first-page":"445","volume":"19","author":"T. Ang","year":"2009","unstructured":"Ang, T., Brzozowski, J.: Languages convex with respect to binary relations, and their closure properties. Acta Cybernet.\u00a019, 445\u2013464 (2009)","journal-title":"Acta Cybernet."},{"issue":"2","key":"20_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/122295.993136","volume":"22","author":"J.C. Birget","year":"1980","unstructured":"Birget, J.C.: Intersection of regular languages and state complexity. ACM SIGACT News\u00a022(2), 49 (1980)","journal-title":"ACM SIGACT News"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"3209","DOI":"10.1016\/j.tcs.2009.05.019","volume":"410","author":"H. Bordihn","year":"2009","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theoret. Comput. Sci.\u00a0410, 3209\u20133249 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J. Brzozowski","year":"1964","unstructured":"Brzozowski, J.: Derivatives of regular expressions. J. ACM\u00a011, 481\u2013494 (1964)","journal-title":"J. ACM"},{"key":"20_CR5","unstructured":"Brzozowski, J.: Quotient complexity of regular languages. In: Dassow, J., Pighizzini, G., Truthe, B. (eds.) 11th International Workshop on Descriptional Complexity of Formal Systems. pp. 25\u201342. Otto-von-Guericke-Universit\u00e4t, Magdeburg (2009), \n                  \n                    http:\/\/arxiv.org\/abs\/0907.4547"},{"key":"20_CR6","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B.: Quotient complexity of ideal languages, \n                  \n                    http:\/\/arxiv.org\/abs\/0908.2083"},{"key":"20_CR7","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Zou, C.: Quotient complexity of closed languages, \n                  \n                    http:\/\/arxiv.org\/abs\/0912.1034"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-00982-2_21","volume-title":"Language and Automata Theory and Applications","author":"J. Brzozowski","year":"2009","unstructured":"Brzozowski, J., Shallit, J., Xu, Z.: Decision procedures for convex languages. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 247\u2013258. Springer, Heidelberg (2009)"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"Automata Implementation","author":"C. C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Culik II, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol.\u00a02214, pp. 60\u201370. Springer, Heidelberg (2001)"},{"key":"20_CR10","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of Formal Languages","author":"M. Crochemore","year":"1997","unstructured":"Crochemore, M., Hancart, C.: Automata for matching patterns. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a02, pp. 399\u2013462. Springer, Heidelberg (1997)"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/S0021-9800(69)80111-0","volume":"6","author":"L.H. Haines","year":"1969","unstructured":"Haines, L.H.: On free monoids partially ordered by embedding. J. Combin. Theory\u00a06, 94\u201398 (1969)","journal-title":"J. Combin. Theory"},{"key":"20_CR12","doi-asserted-by":"publisher","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.\u00a0410, 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR13","first-page":"99","volume-title":"Automata, Formal Languages, and Related Topics","author":"Y.-S. Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: Automata, Formal Languages, and Related Topics, pp. 99\u2013115. University of Szeged, Hungary (2009)"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"E. Leiss","year":"1981","unstructured":"Leiss, E.: Succinct representation of regular languages by boolean automata. Theoret. Comput. Sci.\u00a013, 323\u2013330 (1981)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-1-4612-3352-7_20","volume-title":"Sequences","author":"A. Luca de","year":"1990","unstructured":"de Luca, A., Varricchio, S.: Some combinatorial properties of factorial languages. In: Capocelli, R. (ed.) Sequences, pp. 258\u2013266. Springer, Heidelberg (1990)"},{"key":"20_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59849-4","volume-title":"Finiteness and Regularity in Semigroups and Formal Languages","author":"A. Luca de","year":"1999","unstructured":"de Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Springer, Heidelberg (1999)"},{"key":"20_CR17","first-page":"1266","volume":"194","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266\u20131268 (1970) (in Russian); English translation: Soviet Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"20_CR18","unstructured":"Okhotin. A.: On the state complexity of scattered substrings and superstrings. Turku Centre for Computer Science Technical Report No.\u00a0849 (2007)"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1145\/321281.321292","volume":"12","author":"A. Paz","year":"1965","unstructured":"Paz, A., Peleg, B.: Ultimate-definite and symmetric-definite events and automata. J. ACM\u00a012(3), 399\u2013410 (1965)","journal-title":"J. ACM"},{"key":"20_CR20","first-page":"1","volume-title":"Handbook of Theoretical Computer Science","author":"D. Perrin","year":"1990","unstructured":"Perrin, D.: Finite automata. In: van Leewen (ed.) Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 1\u201357. Elsevier, Amsterdam (1990)"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S012905410200100X","volume":"13","author":"G. Pighizzini","year":"2002","unstructured":"Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal\u2019s function. Internat. J. Found. Comput. Sci.\u00a013, 145\u2013159 (2002)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop.\u00a03, 114\u2013129 (1959)","journal-title":"IBM J. Res. Develop."},{"key":"20_CR23","doi-asserted-by":"publisher","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.\u00a0320, 315\u2013329 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR24","volume-title":"Free Monoids and Languages","author":"H.J. Shyr","year":"2001","unstructured":"Shyr, H.J.: Free Monoids and Languages. Hon Min Book Co., Taiwan (2001)"},{"key":"20_CR25","first-page":"481","volume-title":"Automata, Languages and Programming","author":"G. Thierrin","year":"1973","unstructured":"Thierrin, G.: Convex languages. In: Nivat, M. (ed.) Automata, Languages and Programming, pp. 481\u2013492. North-Holland, Amsterdam (1973)"},{"key":"20_CR26","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41\u2013110. Springer, Heidelberg (1997)"},{"key":"20_CR27","first-page":"221","volume":"6","author":"S. Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb.\u00a06, 221\u2013234 (2001)","journal-title":"J. Autom. Lang. Comb."},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoret. Comput. Sci.\u00a0125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:05:33Z","timestamp":1619784333000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}