{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:05:03Z","timestamp":1767236703396,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T00:00:00Z","timestamp":1581897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003194","name":"Agent\u00fara Ministerstva \u0160kolstva, Vedy, V\u00fdskumu a \u0160portu SR","doi-asserted-by":"publisher","award":["VEGA 1\/0056\/18"],"award-info":[{"award-number":["VEGA 1\/0056\/18"]}],"id":[{"id":"10.13039\/501100003194","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005357","name":"Agent\u00fara na Podporu V\u00fdskumu a V\u00fdvoja","doi-asserted-by":"publisher","award":["APVV-15-0091"],"award-info":[{"award-number":["APVV-15-0091"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s00236-020-00373-8","type":"journal-article","created":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T15:06:56Z","timestamp":1581952016000},"page":"463-495","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complement for two-way alternating automata"],"prefix":"10.1007","volume":"58","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos A.","family":"Kapoutsis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Zakzok","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,17]]},"reference":[{"key":"373_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1976","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston, MA (1976)"},{"key":"373_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(87)90085-8","volume":"25","author":"L Berman","year":"1987","unstructured":"Berman, L., Chang, J.H., Ibarra, O.H., Ravikumar, B.: Some observations concerning alternating turing machines using small space. Inf. Process. Lett. 25, 1\u20139 (1987). (Corr. ibid., 27, p.\u00a053, 1988.)","journal-title":"Inf. Process. Lett."},{"key":"373_CR3","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"J-C Birget","year":"1993","unstructured":"Birget, J.-C.: Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci. 119, 267\u201391 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"373_CR4","volume-title":"Introduction to the Theory of Complexity","author":"DP Bovet","year":"1994","unstructured":"Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice Hall, Upper Saddle River, NJ (1994)"},{"key":"373_CR5","volume-title":"Fundamentals of Algorithmics","author":"G Brassard","year":"1996","unstructured":"Brassard, G., Bratley, P.: Fundamentals of Algorithmics. Prentice Hall, Upper Saddle River, NJ (1996)"},{"key":"373_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. Assoc. Comput. Mach. 28, 114\u201333 (1981)","journal-title":"J. Assoc. Comput. Mach."},{"key":"373_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90362-W","volume":"118","author":"V Geffert","year":"1993","unstructured":"Geffert, V.: A speed-up theorem without tape compression. Theor. Comput. Sci. 118, 49\u201365 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"373_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.044","volume":"445","author":"V Geffert","year":"2012","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. Theor. Comput. Sci. 445, 1\u201324 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"373_CR9","doi-asserted-by":"crossref","unstructured":"Geffert, V.: Complement for two-way alternating automata. In: Proceedings on Computer Science Theory and Applications in Russia, Lecture Notes in Computer Science, vol. 10846, pp.\u00a0132\u201344. Springer (2018)","DOI":"10.1007\/978-3-319-90530-3_12"},{"key":"373_CR10","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. Inf. Comput. 205, 1173\u201387 (2007)","journal-title":"Inf. Comput."},{"key":"373_CR11","doi-asserted-by":"crossref","unstructured":"Geffert, V., Okhotin, A.: Transforming two-way alternating finite automata to one-way nondeterministic automata. In: Proceedings on Mathematical Foundations of Computer Science Part\u00a0I, Lecture Notes in Computer Science, vol.\u00a08634, pp.\u00a0291\u2013302. Springer (2014)","DOI":"10.1007\/978-3-662-44522-8_25"},{"key":"373_CR12","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J Hopcroft","year":"2001","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston, MA (2001)"},{"key":"373_CR13","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. 17, 935\u201338 (1988)","journal-title":"SIAM J. Comput."},{"key":"373_CR14","doi-asserted-by":"crossref","unstructured":"Kapoutsis, Ch.A.: Size complexity of two-way finite automata. In: Proceedings on Developments in Language Theory, Lecture Notes in Computer Science, vol.\u00a05583, pp.\u00a047\u201366. Springer (2009)","DOI":"10.1007\/978-3-642-02737-6_4"},{"key":"373_CR15","unstructured":"Kapoutsis, Ch.A.: Minicomplexity. J. Autom. Lang. Combin. 17, 205\u201324 (2012)"},{"key":"373_CR16","doi-asserted-by":"crossref","unstructured":"Kunc, M., Okhotin, A.: Reversibility of computations in graph-walking automata. In: Proceedings on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol.\u00a08087, pp.\u00a0595\u2013606. Springer (2013)","DOI":"10.1007\/978-3-642-40313-2_53"},{"key":"373_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"RE Ladner","year":"1984","unstructured":"Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput. 13, 135\u201355 (1984)","journal-title":"SIAM J. Comput."},{"key":"373_CR18","volume-title":"Complexity Theory Retrospective II","author":"M Li\u015bkiewicz","year":"1997","unstructured":"Li\u015bkiewicz, M., Reischuk, R.: Computing with sublogarithmic space. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II. Springer, Berlin (1997)"},{"key":"373_CR19","unstructured":"Papadimitriou, Ch.H.: Computational Complexity. Addison-Wesley, Boston, MA (1994)"},{"key":"373_CR20","doi-asserted-by":"crossref","unstructured":"Sakoda, W., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings on ACM Symposium Theory of Computing, pp.\u00a0275\u201386 (1978)","DOI":"10.1145\/800133.804357"},{"key":"373_CR21","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. Theor. Comput. Sci. 10, 335\u201338 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"373_CR22","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2006","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Thomson Course Technology, Boston, MA (2006)","edition":"2"},{"key":"373_CR23","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. 26, 279\u201384 (1988)","journal-title":"Acta Inform."},{"key":"373_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58355-6","volume-title":"Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science","author":"A Szepietowski","year":"1994","unstructured":"Szepietowski, A.: Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science, vol. 843. Springer, Berlin (1994)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00373-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-020-00373-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00373-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T10:11:00Z","timestamp":1630059060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-020-00373-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,17]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["373"],"URL":"https:\/\/doi.org\/10.1007\/s00236-020-00373-8","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2020,2,17]]},"assertion":[{"value":"19 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}