{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:15:44Z","timestamp":1794381344844,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540265467","type":"print"},{"value":"9783540316824","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11505877_23","type":"book-chapter","created":{"date-parts":[[2010,9,26]],"date-time":"2010-09-26T13:40:25Z","timestamp":1285508425000},"page":"260-271","source":"Crossref","is-referenced-by-count":1,"title":["Complementing Two-Way Finite Automata"],"prefix":"10.1007","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlo","family":"Mereghetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M. Dietzelfelbinger","year":"1994","unstructured":"Dietzelfelbinger, M., Kutylowski, M., Reischuk, R.: Exact lower bounds for computing Boolean functions on CREW PRAMs. J. Comput. System Sci.\u00a048, 231\u2013254 (1994)","journal-title":"J. Comput. System Sci."},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/0222009","volume":"22","author":"V. Geffert","year":"1993","unstructured":"Geffert, V.: Tally versions of the Savitch and Immerman-Szelepcs\u00e9nyi theorems for sublogarithmic space. SIAM J. Comput.\u00a022, 102\u2013113 (1993)","journal-title":"SIAM J. Comput."},{"key":"23_CR3","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 automata into simpler automata. Theoret. Comput. Sci.\u00a0295, 189\u2013203 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR4","first-page":"193","volume":"8","author":"J. Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Universal Comput. Sci.\u00a08, 193\u2013234 (2002)","journal-title":"J. Universal Comput. Sci."},{"key":"23_CR5","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00155-9","volume":"262","author":"J. Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On the power of Las Vegas II: Two-way finite automata. Theoret. Comput. Sci.\u00a0262, 1\u201324 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput.\u00a017, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-30500-2_17","volume-title":"Implementation and Application of Automata","author":"J. Jir\u00e1sek","year":"2005","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., Szabari, A.: State complexity of concatenation and complementation of regular languages. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 132\u2013142. Springer, Heidelberg (2005)"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/SFCS.1997.646094","volume-title":"Proc. 38th Symp. Found. Comp. Sci. (FOCS 1997)","author":"A. Kondacs","year":"1997","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. 38th Symp. Found. Comp. Sci. (FOCS 1997), pp. 66\u201375. IEEE Computer Society Press, Los Alamitos (1997)"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2004.04.015","volume":"330","author":"F. Mera","year":"2005","unstructured":"Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata. Theoret. Comput. Sci.\u00a0330, 349\u2013360 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR11","first-page":"287","volume":"5","author":"C. Mereghetti","year":"2000","unstructured":"Mereghetti, C., Pighizzini, G.: Two-way automata simulations and unary languages. J. Aut. Lang. Combin.\u00a05, 287\u2013300 (2000)","journal-title":"J. Aut. Lang. Combin."},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Meyer, A., Fischer, M.: Economy of description by automata, grammars, and formal systems. In: Proc. 12th Ann. IEEE Symp. on Switching and Automata Theory, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C. Moore","year":"2000","unstructured":"Moore, C., Crutchfield, J.: Quantum automata and quantum grammars. Theoret. Comput. Sci.\u00a0237, 275\u2013306 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-20","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 by deterministic automata. IEEE Trans. Comput.\u00a0C-20, 1211\u20131219 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Inform. & Control\u00a06, 230\u2013245 (1963)","journal-title":"Inform. & Control"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Sakoda, W., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proc. 10th ACM Symp. Theory of Computing, pp. 275\u201386 (1978)","DOI":"10.1145\/800133.804357"},{"key":"23_CR17","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. J. Comput. System Sci.\u00a021, 195\u2013202 (1980)","journal-title":"J. Comput. System Sci."},{"key":"23_CR18","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. Theoret. Comput. Sci.\u00a010, 335\u2013338 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform.\u00a026, 279\u2013284 (1988)","journal-title":"Acta Inform."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11505877_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T01:38:04Z","timestamp":1553132284000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11505877_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540265467","9783540316824"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11505877_23","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b137735","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}