{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:13:48Z","timestamp":1743110028440,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"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_3","type":"book-chapter","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T10:05:14Z","timestamp":1467021914000},"page":"29-44","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Self-Verifying Finite Automata and Descriptional Complexity"],"prefix":"10.1007","author":[{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"key":"3_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. Inf. Appl. 41, 261\u2013265 (2007)","journal-title":"Theor. Inf. Appl."},{"key":"3_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":"3_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":"3_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":"3_CR5","unstructured":"Ershov, U.L.: On a conjecture of W.U. Uspenskii. Algebra i Logika (Seminar) 1, 45\u201348 (1962). (in Russian)"},{"key":"3_CR6","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. Inf. Process. Lett. 59, 75\u201377 (1996)","journal-title":"Inf. Process. Lett."},{"key":"3_CR7","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. Int. J. Found. Comput. Sci. 14, 1087\u20131102 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR8","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. Inf. Comput. 169, 284\u2013296 (2001)","journal-title":"Inf. Comput."},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-3-319-20297-6_16","volume-title":"Computer Science \u2013 Theory and Applications","author":"J\u0160 Jir\u00e1sek","year":"2015","unstructured":"Jir\u00e1sek, J.\u0160., Jir\u00e1skov\u00e1, G., Szabari, A.: Operations on self-verifying finite automata. In: Beklemishev, L.D. (ed.) CSR 2015. LNCS, vol. 9139, pp. 231\u2013261. Springer, Heidelberg (2015)"},{"key":"3_CR10","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":"3_CR11","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. Inf. Comput. 209, 528\u2013535 (2011)","journal-title":"Inf. Comput."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2012.05.008","volume":"449","author":"G Jir\u00e1skov\u00e1","year":"2012","unstructured":"Jir\u00e1skov\u00e1, G., \u0160ebej, J.: Reversal of binary regular languages. Theoret. Comput. Sci. 449, 85\u201392 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR13","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":"3_CR14","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":"3_CR15","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":"3_CR16","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)","journal-title":"Kibernetika (Kiev)"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"3_CR18","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":"3_CR19","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":"3_CR20","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of the 10th Annual ACM STOC, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"3_CR21","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":"3_CR22","first-page":"41","volume-title":"Handbook of Formal Languages","author":"Sheng Yu","year":"1997","unstructured":"Yu, S.: Chapter 2: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41\u2013110. Springer, Heidelberg (1997)"},{"key":"3_CR23","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":"3_CR24","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","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41114-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:02:55Z","timestamp":1594598575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41114-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411132","9783319411149"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41114-9_3","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"}]}}