{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:24Z","timestamp":1725728364686},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_24","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"271-282","source":"Crossref","is-referenced-by-count":1,"title":["Universality of Regular Realizability Problems"],"prefix":"10.1007","author":[{"given":"Mikhail N.","family":"Vyalyi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #L, and the determinant. Informatique Th\u00e9orique et Applications\u00a030, 1\u201321 (1996)","journal-title":"Informatique Th\u00e9orique et Applications"},{"issue":"2","key":"24_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01191473","volume":"28","author":"C. \u00c0lvarez","year":"1995","unstructured":"\u00c0lvarez, C., Balc\u00e1zar, J.L., Jenner, B.: Adaptive logspace reducibility and parallel time. Mathematical Systems Theory\u00a028(2), 117\u2013140 (1995)","journal-title":"Mathematical Systems Theory"},{"key":"24_CR3","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.: Detecting palindromes, patterns and borders in regular languages. Information and Computation\u00a0207, 1096\u20131118 (2009)","journal-title":"Information and Computation"},{"key":"24_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational complexity: a modern approach. Cambridge Univ. Press, Cambridge (2009)"},{"issue":"5","key":"24_CR5","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 complement. SIAM Journal on Computing\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9","volume-title":"Automata and Computability","author":"D. Kozen","year":"1997","unstructured":"Kozen, D.: Automata and Computability. Springer, New York (1997)"},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R.E. Ladner","year":"1976","unstructured":"Ladner, R.E., Lynch, N.A.: Relativization of questions about log space computability. Mathematical Systems Theory\u00a010(1), 19\u201332 (1976)","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"24_CR8","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. Journal of the ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"Journal of the ACM"},{"issue":"4","key":"24_CR9","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K. Reinhardt","year":"2000","unstructured":"Reinhardt, K., Allender, E.: Making nondeterminism unambiguous. SIAM Journal on Computing\u00a029(4), 1118\u20131131 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR10","volume-title":"Introduction to the theory of computation","author":"M. Sipser","year":"2012","unstructured":"Sipser, M.: Introduction to the theory of computation, 3rd edn. Cengage Learning, Boston (2012)","edition":"3"},{"key":"24_CR11","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":"M.N. 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.\u00a05675, pp. 334\u2013345. Springer, Heidelberg (2009)"},{"key":"24_CR12","unstructured":"Vyalyi, M.N.: On nondeterminism models for two-way automata. In: Proc. VIII Int. Conf. on Discrete Models in Control System Theory, pp. 54\u201360. MAKS Press, Moscow (2009) (in Russian)"},{"issue":"4","key":"24_CR13","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1134\/S003294601104003X","volume":"47","author":"M.N. Vyalyi","year":"2011","unstructured":"Vyalyi, M.N.: On regular realizability problems. Problems of Information Transmission\u00a047(4), 342\u2013352 (2011)","journal-title":"Problems of Information Transmission"},{"key":"24_CR14","unstructured":"Vyalyi, M.N.: On complexity of regular realizability problems. arXiv:1211.0606v2"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T16:27:23Z","timestamp":1557764843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}