{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:42Z","timestamp":1770994062923,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_14","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"144-156","source":"Crossref","is-referenced-by-count":10,"title":["Small Sweeping 2NFAs Are Not Closed Under Complement"],"prefix":"10.1007","author":[{"given":"Christos A.","family":"Kapoutsis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","unstructured":"Seiferas, J.I.: Manuscript communicated to Michael\u00a0Sipser (1973)"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of the Symposium on the Theory of Computing, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"14_CR3","unstructured":"Kapoutsis, C.: Deterministic moles cannot solve liveness. In: Proceedings of the Workshop on Descriptional Complexity of Formal Systems, pp. 194\u2013205 (2005)"},{"key":"14_CR4","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"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. In: Proceedings of the International Conference on Developments in Language Theory, pp. 260\u2013271 (2005)","DOI":"10.1007\/11505877_23"},{"issue":"2","key":"14_CR6","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":"14_CR7","doi-asserted-by":"crossref","unstructured":"Berman, P.: A note on sweeping automata. In: Proceedings of the International Colloquium on Automata, Languages, and Programming, pp. 91\u201397 (1980)","DOI":"10.1007\/3-540-10003-2_62"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"Micali, S.: Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Information Processing Letters\u00a012(2), 103\u2013105 (1981)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:42Z","timestamp":1619493582000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/11786986_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}