{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:28:08Z","timestamp":1754195288270},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316227"},{"type":"electronic","value":"9783642316234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_2","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T05:03:34Z","timestamp":1341810214000},"page":"20-42","source":"Crossref","is-referenced-by-count":8,"title":["Minicomplexity"],"prefix":"10.1007","author":[{"given":"Christos A.","family":"Kapoutsis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1109\/T-C.1971.223273","volume":"C-20","author":"B.H. Barnes","year":"1971","unstructured":"Barnes, B.H.: A two-way automaton with fewer states than any equivalent one-way automaton. IEEE Transactions on Computers\u00a0C-20(4), 474\u2013475 (1971)","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR2","unstructured":"Berman, P., Lingas, A.: On complexity of regular languages in terms of finite automata. Report 304, Institute of Computer Science, Polish Academy of Sciences, Warsaw (1977)"},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01201276","volume":"29","author":"J.C. Birget","year":"1996","unstructured":"Birget, J.C.: Two-way automata and length-preserving homomorphisms. Mathematical Systems Theory\u00a029, 191\u2013226 (1996)","journal-title":"Mathematical Systems Theory"},{"key":"2_CR4","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. Theoretical Computer Science (to appear)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-28332-1_23","volume-title":"Language and Automata Theory and Applications","author":"V. Geffert","year":"2012","unstructured":"Geffert, V., Guillon, B., Pighizzini, G.: Two-Way Automata Making Choices Only at the Endmarkers. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 264\u2013276. Springer, Heidelberg (2012)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","volume":"295","author":"V. Geffert","year":"2003","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science\u00a0295, 189\u2013203 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.ic.2007.01.008","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation\u00a0205(8), 1173\u20131187 (2007)","journal-title":"Information and Computation"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-45061-0_36","volume-title":"Automata, Languages and Programming","author":"J. Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Nondeterminism Versus Determinism for Two-Way Finite Automata: Generalizations of Sipser\u2019s Separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 439\u2013451. Springer, Heidelberg (2003)"},{"key":"2_CR9","unstructured":"Kapoutsis, C.A.: Nondeterminism is essential in small two-way finite automata with few reversals. Information and Computation (to appear)"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/11549345_47","volume-title":"Mathematical Foundations of Computer Science 2005","author":"C.A. Kapoutsis","year":"2005","unstructured":"Kapoutsis, C.A.: Removing Bidirectionality from Nondeterministic Finite Automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 544\u2013555. Springer, Heidelberg (2005)"},{"key":"2_CR11","unstructured":"Kapoutsis, C.A.: Algorithms and lower bounds in finite automata size complexity. Phd thesis, Massachusetts Institute of Technology (June 2006)"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11786986_14","volume-title":"Automata, Languages and Programming","author":"C.A. Kapoutsis","year":"2006","unstructured":"Kapoutsis, C.A.: Small Sweeping 2NFAs Are Not Closed Under Complement. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 144\u2013156. Springer, Heidelberg (2006)"},{"issue":"1-2","key":"2_CR13","first-page":"215","volume":"12","author":"C.A. Kapoutsis","year":"2007","unstructured":"Kapoutsis, C.A.: Deterministic moles cannot solve liveness. Journal of Automata, Languages and Combinatorics\u00a012(1-2), 215\u2013235 (2007)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"C.A. Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size Complexity of Two-Way Finite Automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 47\u201366. Springer, Heidelberg (2009)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-20712-9_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"C.A. Kapoutsis","year":"2011","unstructured":"Kapoutsis, C.A.: Two-Way Automata versus Logarithmic Space. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 359\u2013372. Springer, Heidelberg (2011)"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-540-85780-8_36","volume-title":"Developments in Language Theory","author":"C.A. Kapoutsis","year":"2008","unstructured":"Kapoutsis, C.A., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the Size Complexity of Rotating and Sweeping Automata. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol.\u00a05257, pp. 455\u2013466. Springer, Heidelberg (2008)"},{"key":"2_CR17","unstructured":"Kapoutsis, C.A., Lefebvre, N.: Analogs of Fagin\u2019s Theorem for small nondeterministic finite automata. In: Proceedings of DLT (to appear, 2012)"},{"key":"2_CR18","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Reversal hierarchies for small 2DFAs (submitted)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L\/poly versus NL. In: Proceedings of CSR, pp. 222\u2013233 (2012)","DOI":"10.1007\/978-3-642-30642-6_21"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Kozen, D.C.: Automata and computability. Springer (1997)","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of FOCS, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"10","key":"2_CR22","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers\u00a020(10), 1211\u20131214 (1971)","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development\u00a03, 114\u2013125 (1959)","journal-title":"IBM Journal of Research and Development"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences\u00a04, 177\u2013192 (1970)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR26","unstructured":"Seiferas, J.I.: Untitled (October 1973), manuscript"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J.C. Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM Journal of Research and Development\u00a03, 198\u2013200 (1959)","journal-title":"IBM Journal of Research and Development"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Halting space-bounded computations. Theoretical Computer Science\u00a010, 335\u2013338 (1980)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"2_CR29","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. Journal of Computer and System Sciences\u00a021(2), 195\u2013202 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR30","unstructured":"Sipser, M.: Introduction to the theory of computation. Thomson Course Technology, 2nd edn. (2006)"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Szepietowski, A.: If deterministic and nondeterministic space complexities are equal for loglogn then they are also equal for logn. In: Proceedings of STACS, pp. 251\u2013255 (1989)","DOI":"10.1007\/BFb0028989"}],"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-642-31623-4_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:40:37Z","timestamp":1620128437000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}