{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:49:54Z","timestamp":1764841794791,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319202969"},{"type":"electronic","value":"9783319202976"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20297-6_16","type":"book-chapter","created":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T01:55:05Z","timestamp":1434938105000},"page":"231-261","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Operations on Self-Verifying Finite Automata"],"prefix":"10.1007","author":[{"given":"Jozef \u0160tefan","family":"Jir\u00e1sek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Szabari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1051\/ita:2007017","volume":"41","author":"I Assent","year":"2007","unstructured":"Assent, I., Seibert, S.: An upper bound for transforming self-verifying automata into deterministic ones. Theor. Inform. Appl. 41, 261\u2013265 (2007)","journal-title":"Theor. Inform. Appl."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"JC Birget","year":"1993","unstructured":"Birget, J.C.: Partial orders on words, minimal elements of regular languages, and state complexity. Theoret. Comput. Sci. 119, 267\u2013291 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR3","first-page":"71","volume":"15","author":"JA Brzozowski","year":"2010","unstructured":"Brzozowski, J.A.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15, 71\u201389 (2010)","journal-title":"J. Autom. Lang. Comb."},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"STACS 97","author":"P \u010euri\u0161","year":"1997","unstructured":"\u010euri\u0161, P., Hromkovi\u010d, J., Rolim, J., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117\u2013128. Springer, Heidelberg (1997)"},{"key":"16_CR5","doi-asserted-by":"publisher","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. Inform. Process. Lett. 59, 75\u201377 (1996)","journal-title":"Inform. Process. Lett."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1142\/S0129054103002199","volume":"14","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Internat. J. Found. Comput. Sci. 14, 1087\u20131102 (2003)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inform. Comput. 169, 284\u2013296 (2001)","journal-title":"Inform. Comput."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.tcs.2004.04.011","volume":"330","author":"G Jir\u00e1skov\u00e1","year":"2005","unstructured":"Jir\u00e1skov\u00e1, G.: State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330, 287\u2013298 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/j.ic.2010.11.017","volume":"209","author":"G Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G., Pighizzini, G.: Optimal simulation of self-verifying automata by deterministic automata. Inform. Comput. 209, 528\u2013535 (2011)","journal-title":"Inform. Comput."},{"key":"16_CR10","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. 13, 323\u2013330 (1981)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR11","first-page":"321","volume":"9","author":"OB Lupanov","year":"1963","unstructured":"Lupanov, O.B.: A comparison of two types of finite automata. Problemy Kibernetiki 9, 321\u2013326 (1963). (in Russian)","journal-title":"Problemy Kibernetiki"},{"key":"16_CR12","first-page":"1373","volume":"11","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Doklady 11, 1373\u20131375 (1970)","journal-title":"Soviet Math. Doklady"},{"key":"16_CR13","first-page":"7","volume":"2","author":"BG Mirkin","year":"1966","unstructured":"Mirkin, B.G.: On dual automata. Kibernetika (Kiev) 2, 7\u201310 (1966). (in Russian). English translation: Cybernetics 2, 6\u20139 (1966)","journal-title":"Kibernetika (Kiev)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C\u201320","author":"F Moore","year":"1971","unstructured":"Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. C\u201320, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"16_CR15","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. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Develop."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Sakoda, W. J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings 10th Annual ACM STOC, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"16_CR17","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)"},{"key":"16_CR18","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 complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-642-39310-5_26","volume-title":"Descriptional Complexity of Formal Systems","author":"K \u010cevorov\u00e1","year":"2013","unstructured":"\u010cevorov\u00e1, K.: Kleene star on unary regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 277\u2013288. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Computer Science -- Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20297-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:46:12Z","timestamp":1676637972000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20297-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319202969","9783319202976"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20297-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}