{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:08:13Z","timestamp":1767236893359},"publisher-location":"Cham","reference-count":10,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_25","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T08:37:57Z","timestamp":1500539877000},"page":"332-344","source":"Crossref","is-referenced-by-count":3,"title":["On Computational Complexity of Set Automata"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Rubtsov","sequence":"first","affiliation":[]},{"given":"Mikhail N.","family":"Vyalyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"issue":"11","key":"25_CR1","doi-asserted-by":"crossref","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":"25_CR2","doi-asserted-by":"crossref","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, Stuttgart (1979)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-09698-8_27","volume-title":"Developments in Language Theory","author":"M Kutrib","year":"2014","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Deterministic set automata. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 303\u2013314. Springer, Cham (2014). doi: 10.1007\/978-3-319-09698-8_27"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-319-09704-6_25","volume-title":"Descriptional Complexity of Formal Systems","author":"M Kutrib","year":"2014","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Regularity and size of set automata. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 282\u2013293. Springer, Cham (2014). doi: 10.1007\/978-3-319-09704-6_25"},{"issue":"02","key":"25_CR5","doi-asserted-by":"crossref","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."},{"issue":"1","key":"25_CR6","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is log space complete for P. SIGACT News 7(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"key":"25_CR7","unstructured":"Lange, K.J., Reinhardt, K.: Set automata. In: Combinatorics, Complexity and Logic, Proceedings of the DMTCS 1996. pp. 321\u2013329. Springer (1996)"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Rubtsov, A.A., Vyalyi, M.N.: On computational complexity of Set Automata. ArXiv e-prints https:\/\/arxiv.org\/pdf\/1704.03730 , April 2017","DOI":"10.1007\/978-3-319-62809-7_25"},{"key":"25_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). doi: 10.1007\/978-3-319-19225-3_22"},{"key":"25_CR10","unstructured":"Vyalyi, M.N.: On the models of nondeterminizm for two-way automata. In: Proceedings of VIII International Conference on Discrete Models in the Theory of Control Systems, pp. 54\u201360 (2009). (in Russian)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62809-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T03:06:12Z","timestamp":1569899172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}