{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T03:38:36Z","timestamp":1775014716021,"version":"3.50.1"},"reference-count":18,"publisher":"Pleiades Publishing Ltd","issue":"4","license":[{"start":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T00:00:00Z","timestamp":1443657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T00:00:00Z","timestamp":1443657600000},"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":["Probl Inf Transm"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1134\/s0032946015040043","type":"journal-article","created":{"date-parts":[[2016,1,3]],"date-time":"2016-01-03T21:14:43Z","timestamp":1451855683000},"page":"349-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On regular realizability problems for context-free languages"],"prefix":"10.1134","volume":"51","author":[{"given":"M. N.","family":"Vyalyi","sequence":"first","affiliation":[]},{"given":"A. A.","family":"Rubtsov","sequence":"additional","affiliation":[]}],"member":"137","published-online":{"date-parts":[[2016,1,5]]},"reference":[{"key":"4245_CR1","first-page":"61","volume-title":"On Prompting Regular Languages in the Model of Generalized Nondeterministic Automata, in Matematicheskie modeli i zadachi upravleniya (Mathematical Models and Control)","author":"A.A. Rubtsov","year":"2011","unstructured":"Rubtsov, A.A., On Prompting Regular Languages in the Model of Generalized Nondeterministic Automata, in Matematicheskie modeli i zadachi upravleniya (Mathematical Models and Control), Moscow: Moscow Inst. of Physics and Technology, 2011, pp. 61\u201367."},{"issue":"11","key":"4245_CR2","doi-asserted-by":"publisher","first-page":"096","DOI":"10.1016\/j.ic.2008.06.007","volume":"207","author":"T. Anderson","year":"2009","unstructured":"Anderson, T., Loftus, J., Rampersad, N., Santean, N., and Shallit, J., Detecting Palindromes, Patterns and Borders in Regular Languages, Inform. and Comput., 2009, vol. 207, no. 11, pp. 096\u20131118.","journal-title":"Inform. and Comput."},{"issue":"4","key":"4245_CR3","first-page":"43","volume":"47","author":"M.N. Vyalyi","year":"2011","unstructured":"Vyalyi, M.N., On Regular Realizability, Probl. Peredachi Inf., 2011, vol. 47, no. 4, pp. 43\u201354 [Probl. Inf. Trans. (Engl. Transl.), 2011, vol. 47, no. 4, pp. 342\u2013352].","journal-title":"Probl. Peredachi Inf."},{"issue":"3","key":"4245_CR4","first-page":"86","volume":"49","author":"M.N. Vyalyi","year":"2013","unstructured":"Vyalyi, M.N., On Expressive Power of Regular Realizability, Probl. Peredachi Inf., 2013, vol. 49, no. 3, pp. 86\u2013104 [Probl. Inf. Trans. (Engl. Transl.), 2013, vol. 49, no. 3, pp. 276\u2013291].","journal-title":"Probl. Peredachi Inf."},{"key":"4245_CR5","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, Stuttgart: Teubner, 1979."},{"issue":"4","key":"4245_CR6","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1051\/ita\/1979130403631","volume":"13","author":"J.-M. Autebert","year":"1979","unstructured":"Autebert, J.-M., Beauquier, J., Boasson, L., and Nivat, M., Quelques probl\u00e9mes ouverts en th\u00e9orie des langages alg\u00e9briques, RAIRO Inform. Th\u00e9or., 1979, vol. 13, no. 4, pp. 363\u2013378.","journal-title":"RAIRO Inform. Th\u00e9or."},{"issue":"3","key":"4245_CR7","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1051\/ita\/1990240302751","volume":"24","author":"L. Pierre","year":"1990","unstructured":"Pierre, L. and Farinone, J.-M., Context-Free Languages with Rational Index in \u00a6\u00a8(n\u00a6\u00cb) for Algebraic Numbers \u00a6\u00cb, RAIRO Inform. Th\u00e9or. Appl., 1990, vol. 24, no. 3, pp. 275\u2013322.","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"4245_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S. and Barak, B., Computational Complexity: A Modern Approach, Cambridge, UK: Cambridge Univ. Press, 2009."},{"key":"4245_CR9","volume-title":"Introduction to the Theory of Computation","author":"M. Sipser","year":"2012","unstructured":"Sipser, M., Introduction to the Theory of Computation, Boston, MA: Course Technology Cengage Learning, 2012, 3rd ed."},{"key":"4245_CR10","first-page":"59","volume":"B","author":"J. Berstel","year":"1990","unstructured":"Berstel, J. and Boasson, L., Context-Free Languages, Handbook of Theoretical Computer Science, van Leewen, J., Ed., Amsterdam: Elsevier, 1990, vol. B, pp. 59\u2013102.","journal-title":"Context-Free Languages, Handbook of Theoretical Computer Science"},{"key":"4245_CR11","unstructured":"Word, Language, Grammar, vol. 1 of Handbook of Formal Languages, Rozenberg, G. and Salomaa, A., Eds., Berlin: Springer, 1997."},{"issue":"1","key":"4245_CR12","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"S.A. Greibach","year":"1969","unstructured":"Greibach, S.A., An Infinite Hierarchy of Context-Free Languages, J. ACM, 1969, vol. 16, no. 1, pp. 91\u2013106.","journal-title":"J. ACM"},{"key":"4245_CR13","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., and Ruzzo, W.L., Limits to Parallel Computation: P-Completeness Theory, New York: Oxford Univ. Press, 1995."},{"issue":"2","key":"4245_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1051\/ita\/1985190201251","volume":"19","author":"L. Boasson","year":"1985","unstructured":"Boasson, L., Non-g\u00e9n\u00e9rateurs alg\u00e9briques et substitution, RAIRO Inform. Th\u00e9or., 1985, vol. 19, no. 2, pp. 25\u2013136.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"4245_CR15","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-38536-0_32","volume":"7913","author":"A. Yakary\u03b9lmaz","year":"2013","unstructured":"Yakary\u03b9lmaz, A., One-Counter Verifiers for Decidable Languages, Computer Science\u00a1\u00aaTheory and Applications (Proc. 8th Int. Computer Science Sympos. in Russia (CSR\u20192013), Ekaterinburg, Russia, June 25\u201329, 2013), Bulatov, A.A. and Shur, A.M., Eds., Lect. Notes Comput. Sci., vol. 7913, Heidelberg: Springer, 2013, pp. 366\u2013377.","journal-title":"Lect. Notes Comput. Sci."},{"issue":"2","key":"4245_CR16","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0210020","volume":"10","author":"L. Boasson","year":"1981","unstructured":"Boasson, L., Courcelle, B., and Nivat, M., The Rational Index: A Complexity Measure for Languages, SIAM J. Comput., 1981, vol. 10, no. 2, pp. 284\u2013296.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"4245_CR17","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, Theoret. Comput. Sci., 1992, vol. 95, no. 2, pp. 279\u2013305.","journal-title":"Theoret. Comput. Sci."},{"key":"4245_CR18","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1109\/FOCS.1965.14","volume-title":"Proc. 6th Annual Sympos. on Switching Circuit Theory and Logical Design (SWCT\u20191965)","author":"P.M. Lewis","year":"1965","unstructured":"Lewis, P.M., Stearns, R.E., and Hartmanis, J., Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages, in Proc. 6th Annual Sympos. on Switching Circuit Theory and Logical Design (SWCT\u20191965), Ann Arbor, MI, USA, Oct. 6\u20138, 1965, New York: IEEE, 1965, pp. 191\u2013202."}],"container-title":["Problems of Information Transmission"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946015040043.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S0032946015040043","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946015040043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946015040043.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:21:01Z","timestamp":1775010061000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S0032946015040043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["4245"],"URL":"https:\/\/doi.org\/10.1134\/s0032946015040043","relation":{},"ISSN":["0032-9460","1608-3253"],"issn-type":[{"value":"0032-9460","type":"print"},{"value":"1608-3253","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10]]},"assertion":[{"value":"9 September 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}