{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:45:05Z","timestamp":1775054705760,"version":"3.50.1"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319192246","type":"print"},{"value":"9783319192253","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_22","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"256-267","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Regular Realizability Problems and Context-Free Languages"],"prefix":"10.1007","author":[{"given":"A.","family":"Rubtsov","sequence":"first","affiliation":[]},{"given":"M.","family":"Vyalyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"22_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.: Detecting palindromes, patterns and borders in regular languages. Inf. Comput. 207, 1096\u20131118 (2009)","journal-title":"Inf. Comput."},{"key":"22_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 Verlag, Stuttgart\/Leipzig\/Wiesbaden (1979)"},{"key":"22_CR3","first-page":"59","volume-title":"Handbook of Theoretical Computer Science","author":"J Berstel","year":"1990","unstructured":"Berstel, J., Boasson, L.: Context-free languages. In: Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 59\u2013102. Elsevier, Amsterdam (1990)"},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita\/1985190201251","volume":"19","author":"L Boasson","year":"1985","unstructured":"Boasson, L.: Non-g\u00e9n\u00e9rateurs alg\u00e9briques et substitution. RAIRO Informatique th\u00e9orique 19, 125\u2013136 (1985)","journal-title":"RAIRO Informatique th\u00e9orique"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0210020","volume":"10","author":"L Boasson","year":"1981","unstructured":"Boasson, L., Courcelle, B., Nivat, M.: The rational index, a complexity measure for languages. SIAM J. Comput. 10(2), 284\u2013296 (1981)","journal-title":"SIAM J. Comput."},{"key":"22_CR6","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"SA Greibach","year":"1969","unstructured":"Greibach, S.A.: An infinite hierarchy of context-free languages. J. ACM 16, 91\u2013106 (1969)","journal-title":"J. ACM"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Lewis, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Switching Circuit Theory and Logical Design, pp. 191\u2013202. IEEE, New York (1965)","DOI":"10.1109\/FOCS.1965.14"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(92)90269-L","volume":"95","author":"L Pierre","year":"1992","unstructured":"Pierre, L.: Rational indexes of generators of the cone of context-free languages. Theor. Comput. Sci. 95, 279\u2013305 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"22_CR10","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1051\/ita\/1990240302751","volume":"24","author":"L Pierre","year":"1990","unstructured":"Pierre, L., Farinone, J.M.: Rational index of context-free languages with rational index in $$\\Theta (n^\\gamma )$$ for algebraic numbers $$\\gamma $$. Informatique th\u00e9orique et applications 24(3), 275\u2013322 (1990)","journal-title":"Informatique th\u00e9orique et applications"},{"issue":"4","key":"22_CR11","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":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-38536-0_24","volume-title":"Computer Science \u2013 Theory and Applications","author":"MN Vyalyi","year":"2013","unstructured":"Vyalyi, M.N.: Universality of regular realizability problems. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 271\u2013282. Springer, Heidelberg (2013)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-38536-0_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Yakary\u0131lmaz","year":"2013","unstructured":"Yakary\u0131lmaz, A.: One-counter verifiers for decidable languages. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 366\u2013377. Springer, Heidelberg (2013)"}],"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-319-19225-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:24:04Z","timestamp":1676942644000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}