{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T01:07:57Z","timestamp":1767229677310,"version":"3.48.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030934880"},{"type":"electronic","value":"9783030934897"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-93489-7_13","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:30:01Z","timestamp":1640997001000},"page":"150-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8850-9749","authenticated-orcid":false,"given":"Alexander","family":"Rubtsov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9822-1060","authenticated-orcid":false,"given":"Mikhail","family":"Vyalyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,1]]},"reference":[{"issue":"11","key":"13_CR1","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.ic.2008.06.007","volume":"207","author":"T Anderson","year":"2009","unstructured":"Anderson, T., Loftus, J., Rampersad, N., Santean, N., Shallit, J.: Special issue: LATA 2008 detecting palindromes, patterns and borders in regular languages. Inf. Comput. 207(11), 1096\u20131118 (2009)","journal-title":"Inf. Comput."},{"key":"13_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","author":"J Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner, Wiesbaden (1979). https:\/\/doi.org\/10.1007\/978-3-663-09367-1"},{"issue":"3","key":"13_CR3","first-page":"185","volume":"13","author":"M Daley","year":"2008","unstructured":"Daley, M., Eramian, M., Mcquillan, I.: The bag automaton: a model of nondeterministic storage. J. Autom. Lang. Comb. 13(3), 185\u2013206 (2008)","journal-title":"J. Autom. Lang. Comb."},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Ullman, J.D.: An approach to a unified theory of automata. In: SWAT 1967, pp. 140\u2013147 (1967)","DOI":"10.1109\/FOCS.1967.4"},{"issue":"02","key":"13_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0129054116400062","volume":"27","author":"M Kutrib","year":"2016","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Set automata. Int. J. Found. Comput. Sci. 27(02), 187\u2013214 (2016)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"13_CR6","unstructured":"Lange, K.J., Reinhardt, K.: Set automata. In: Combinatorics, Complexity and Logic; Proceedings of the DMTCS 1996, pp. 321\u2013329. Springer, Berlin (1996)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-319-62809-7_25","volume-title":"Developments in Language Theory","author":"AA Rubtsov","year":"2017","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: On computational complexity of set automata. In: Charlier, \u00c9., Leroy, J., Rigo, M. (eds.) DLT 2017. LNCS, vol. 10396, pp. 332\u2013344. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-62809-7_25"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-319-90530-3_25","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Rubtsov","year":"2018","unstructured":"Rubtsov, A., Vyalyi, M.: On emptiness and membership problems for set automata. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 295\u2013307. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90530-3_25"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-319-19225-3_22","volume-title":"Descriptional Complexity of Formal Systems","author":"A Rubtsov","year":"2015","unstructured":"Rubtsov, A., Vyalyi, M.: Regular realizability problems and context-free languages. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 256\u2013267. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19225-3_22"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Rubtsov, A., Vyalyi, M.: On computational complexity of set automata. CoRR abs\/1704.03730 (2017)","DOI":"10.1007\/978-3-319-62809-7_25"},{"key":"13_CR11","unstructured":"Rubtsov, A., Vyalyi, M.: On computational complexity of set automata. Inf. Comput. (to appear)"},{"key":"13_CR12","unstructured":"Sipser, M.: Introduction to the theory of computation. Cengage Learning (2013)"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-03351-3_31","volume-title":"Computer Science - Theory and Applications","author":"MN Vyalyi","year":"2009","unstructured":"Vyalyi, M.N.: On models of a nondeterministic computation. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp. 334\u2013345. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03351-3_31"},{"key":"13_CR14","unstructured":"Vyalyi, M.: On the models of nondeterminism for two-way automata. In: Proceedings of VIII International Conference \u00abDiscrete Models in the Theory of Control Systems\u00bb, pp. 54\u201360 (2009). (in Russian)"},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1134\/S003294601104003X","volume":"47","author":"MN Vyalyi","year":"2011","unstructured":"Vyalyi, M.N.: On regular realizability problems. Probl. Inf. Transm. 47(4), 342\u2013352 (2011)","journal-title":"Probl. Inf. Transm."},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-030-23247-4_21","volume-title":"Descriptional Complexity of Formal Systems","author":"P Wolf","year":"2019","unstructured":"Wolf, P.: On the decidability of finding a positive ILP-instance in a regular set of ILP-instances. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) DCFS 2019. LNCS, vol. 11612, pp. 272\u2013284. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-23247-4_21"},{"key":"13_CR17","unstructured":"Wolf, P., Fernau, H.: Regular intersection emptiness of graph problems: finding a needle in a haystack of graphs with the help of automata. CoRR abs\/2003.05826 (2020)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-93489-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T01:02:58Z","timestamp":1767229378000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-93489-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030934880","9783030934897"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-93489-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/toc.yonsei.ac.kr\/dcfs2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}