{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:30:13Z","timestamp":1757453413038,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006109","name":"Vedeck\u00e1 Grantov\u00e1 Agent\u00fara M\u0160VVa\u0160 SR a SAV","doi-asserted-by":"publisher","award":["1\/0177\/21"],"award-info":[{"award-number":["1\/0177\/21"]}],"id":[{"id":"10.13039\/501100006109","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005357","name":"Agent\u00fara na Podporu V\u00fdskumu a V\u00fdvoja","doi-asserted-by":"crossref","award":["APVV-15-0091"],"award-info":[{"award-number":["APVV-15-0091"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007458","name":"Qatar Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007458","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00236-021-00414-w","type":"journal-article","created":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T16:04:23Z","timestamp":1642781063000},"page":"619-669","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved complement for two-way alternating automata"],"prefix":"10.1007","volume":"59","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8963-9326","authenticated-orcid":false,"given":"Christos A.","family":"Kapoutsis","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Zakzok","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,21]]},"reference":[{"key":"414_CR1","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. Theoret. Comput. Sci. 119, 267\u2013291 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"414_CR2","doi-asserted-by":"crossref","unstructured":"Geffert, V.: Complement for two-way alternating automata. In: Proceedings of the International Computer Science Symposium in Russia, pp. 132\u2013144 (2018)","DOI":"10.1007\/978-3-319-90530-3_12"},{"key":"414_CR3","doi-asserted-by":"publisher","unstructured":"Geffert, V., Kapoutsis, C., Zakzok, M.: Complement for two-way alternating automata. Acta Informatica (2020). https:\/\/doi.org\/10.1007\/s00236-020-00373-8","DOI":"10.1007\/s00236-020-00373-8"},{"issue":"8","key":"414_CR4","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(8), 1173\u20131187 (2007)","journal-title":"Inf. Comput."},{"key":"414_CR5","doi-asserted-by":"crossref","unstructured":"Geffert, V., Okhotin, A.: Transforming two-way alternating finite automata to one-way nondeterministic automata. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 291\u2013302 (2014)","DOI":"10.1007\/978-3-662-44522-8_25"},{"issue":"2","key":"414_CR6","first-page":"193","volume":"8","author":"J Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Univ. Comput. Sci. 8(2), 193\u2013234 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"414_CR7","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.: Removing bidirectionality from nondeterministic finite automata. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 544\u2013555 (2005)","DOI":"10.1007\/11549345_47"},{"key":"414_CR8","unstructured":"Kapoutsis, C.: Algorithms and lower bounds in finite automata size complexity. Ph.D. Thesis, Massachusetts Institute of Technology (2006)"},{"issue":"2\u20134","key":"414_CR9","first-page":"205","volume":"17","author":"C Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.: Minicomplexity. J. Autom. Lang. Comb. 17(2\u20134), 205\u2013224 (2012)","journal-title":"J. Autom. Lang. Comb."},{"key":"414_CR10","doi-asserted-by":"publisher","unstructured":"Kapoutsis, C., Zakzok, M.: Alternation in two-way finite automata. Theor. Comput. Sci. (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.12.011","DOI":"10.1016\/j.tcs.2020.12.011"},{"key":"414_CR11","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of the Symposium on the Foundations of Computer Science, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"414_CR12","unstructured":"Rabin, M.O., Scott, D.: Remarks on finite automata. In: Proceedings of the Summer Institute of Symbolic Logic, pp. 106\u2013112. Cornell (1957)"},{"key":"414_CR13","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"414_CR14","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"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00414-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00414-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00414-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T09:03:01Z","timestamp":1664010181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00414-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,21]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["414"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00414-w","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,1,21]]},"assertion":[{"value":"14 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}