{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:44:08Z","timestamp":1775018648896,"version":"3.50.1"},"reference-count":24,"publisher":"Pleiades Publishing Ltd","issue":"3","license":[{"start":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T00:00:00Z","timestamp":1725148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T00:00:00Z","timestamp":1725148800000},"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":[[2024,9]]},"DOI":"10.1134\/s0032946024030050","type":"journal-article","created":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T09:02:58Z","timestamp":1736067778000},"page":"209-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Universality of Regular Realizability Problems"],"prefix":"10.1134","volume":"60","author":[{"given":"A. A.","family":"Rubtsov","sequence":"first","affiliation":[]},{"given":"M. N.","family":"Vyalyi","sequence":"additional","affiliation":[]}],"member":"137","published-online":{"date-parts":[[2025,1,5]]},"reference":[{"key":"5102_CR1","doi-asserted-by":"crossref","unstructured":"Yannakakis, M., Graph-Theoretic Methods in Database Theory, in Proc. 9th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS\u201990), Nashville, TN, USA, Apr. 2\u20134, 1990, New York: ACM, 1990, pp.\u00a0230\u2013242. https:\/\/doi.org\/10.1145\/298514.298576","DOI":"10.1145\/298514.298576"},{"key":"5102_CR2","doi-asserted-by":"crossref","unstructured":"Bouajjani, A., Esparza, J., and Maler, O., Reachability Analysis of Pushdown Automata: Application to Model-Checking, Proc. Int. Conf. on Concurrency Theory (CONCUR\u201997), Warsaw, Poland, July 1\u20134, 1997, Mazurkiewicz, A. and Winkowski, J., Eds., Lect. Notes Comput. Sci., vol.\u00a01243, Berlin, Heidelberg: Springer, 1997, pp.\u00a0135\u2013150. https:\/\/doi.org\/10.1007\/3-540-63141-0_10","DOI":"10.1007\/3-540-63141-0_10"},{"key":"5102_CR3","doi-asserted-by":"crossref","unstructured":"Rubtsov, A.A. and Vyalyi, M.N., Regular Realizability Problems and Context-Free Languages, Proc. 17th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS\u20192015), Waterloo, ON, Canada, June 25\u201327, 2015, Shallit, J.O. and Okhotin, A., Lect. Notes Comput. Sci., vol.\u00a09118, Berlin, Heidelberg: Springer, 2015, pp.\u00a0256\u2013267. https:\/\/doi.org\/10.1007\/978-3-319-19225-3_22","DOI":"10.1007\/978-3-319-19225-3_22"},{"key":"5102_CR4","doi-asserted-by":"publisher","DOI":"10.1145\/3498702","volume":"6","author":"D. Chistikov","year":"2022","unstructured":"Chistikov, D., Majumdar, R., and Schepper, P., Subcubic Certificates for CFL Reachability, Proc. ACM Program. Lang., 2022, vol.\u00a06, Article 41 (29\u00a0pp.). https:\/\/doi.org\/10.1145\/3498702","journal-title":"Proc. ACM Program. Lang."},{"issue":"4","key":"5102_CR5","first-page":"43","volume":"47","author":"M.N. Vyalyi","year":"2011","unstructured":"Vyalyi, M.N., On Regular Realizability Problems, Probl. Peredachi Inf., 2011, vol.\u00a047, no.\u00a04, pp.\u00a043\u201354 [Probl. Inf. Transm. (Engl. Transl.), 2011, vol.\u00a047, no.\u00a04, pp.\u00a0342\u2013352]. https:\/\/doi.org\/10.1134\/S003294601104003X","journal-title":"Probl. Peredachi Inf."},{"issue":"3","key":"5102_CR6","first-page":"86","volume":"49","author":"M.N. Vyalyi","year":"2013","unstructured":"Vyalyi, M.N., On Expressive Power of Regular Realizability Problems, Probl. Peredachi Inf., 2013, vol.\u00a049, no.\u00a03, pp.\u00a086\u2013104 [Probl. Inf. Transm. (Engl. Transl.), 2013, vol.\u00a049, no.\u00a03, pp.\u00a0276\u2013291]. https:\/\/doi.org\/10.1134\/S0032946013030058","journal-title":"Probl. Peredachi Inf."},{"key":"5102_CR7","doi-asserted-by":"crossref","unstructured":"Vyalyi, M.N., On Models of a Nondeterministic Computation, Computer Science \u2013 Theory and Applications: Proc. 4th Int. Computer Science Symp. in Russia (CSR\u201909), Novosibirsk, Russia, Aug. 18\u201323, 2009, Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W., Eds., Lect. Notes Comput. Sci., vol.\u00a05675, Berlin, Heidelberg: Springer, 2009, pp.\u00a0334\u2013345. https:\/\/doi.org\/10.1007\/978-3-642-03351-3_31","DOI":"10.1007\/978-3-642-03351-3_31"},{"key":"5102_CR8","unstructured":"Rubtsov, A. and Vyalyi, M., Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems, https:\/\/arxiv.org\/abs\/2210.03934\n [cs.FL], 2022."},{"key":"5102_CR9","unstructured":"Wolf, P. and Fernau, H., Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata, https:\/\/arxiv.org\/abs\/2003.05826\n [cs.FL], 2020."},{"key":"5102_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2021.11.006","volume":"899","author":"P. Wolf","year":"2022","unstructured":"Wolf, P., From Decidability to Undecidability by Considering Regular Sets of Instances, Theor. Comput. Sci., 2022, vol.\u00a0899, pp.\u00a025\u201338. https:\/\/doi.org\/10.1016\/j.tcs.2021.11.006","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"5102_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00236-022-00427-z","volume":"59","author":"V. Diekert","year":"2022","unstructured":"Diekert, V., Fernau, H., and Wolf, P., Properties of Graphs Specified by a Regular Language, Acta Inform., 2022, vol.\u00a059, no.\u00a04, pp.\u00a0357\u2013385. https:\/\/doi.org\/10.1007\/s00236-022-00427-z","journal-title":"Acta Inform."},{"issue":"3","key":"5102_CR12","first-page":"46","volume":"60","author":"M.N. Vyalyi","year":"2024","unstructured":"Vyalyi, M.N. and Rubtsov A.A. Regular Realizability Problems for Descriptions of Finite Relations, Probl. Peredachi Inf., 2024, vol.\u00a060, no.\u00a03, pp.\u00a046\u201358. https:\/\/doi.org\/10.31857\/S0555292324030069","journal-title":"Probl. Peredachi Inf."},{"key":"5102_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M., Finite Automata and Unary Languages, Theor. Comput. Sci., 1986, vol.\u00a047, pp.\u00a0149\u2013158. https:\/\/doi.org\/10.1016\/0304-3975(86)90142-8","journal-title":"Theor. Comput. Sci."},{"key":"5102_CR14","unstructured":"Martinez, A., Efficient Computation of Regular Expressions from Unary NFAs, Pre-proc. 4th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS 2002), London, Canada, Aug. 21\u201324, 2002, Dassow, J., Hoeberechts, M., Jurgensen, H., and Wotschke, D., Eds., Dept. Comput. Sci., Univ. of Western Ontario, Canada, 2002, pp.\u00a0174\u2013187."},{"issue":"1\u20133","key":"5102_CR15","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0304-3975(03)00136-1","volume":"302","author":"M. Chrobak","year":"2003","unstructured":"Chrobak, M., Errata to: \u201cFinite Automata and Unary Languages\u201d: [Theoret. Comput. Sci. 47 (1986) 149\u2013158], Theor. Comput. Sci., 2003, vol.\u00a0302, no.\u00a01\u20133, pp.\u00a0497\u2013498. https:\/\/doi.org\/10.1016\/S0304-3975(03)00136-1","journal-title":"Theor. Comput. Sci."},{"issue":"17","key":"5102_CR16","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1016\/j.ipl.2009.06.005","volume":"109","author":"A.W. To","year":"2009","unstructured":"To, A.W., Unary Finite Automata vs. Arithmetic Progressions, Inform. Process. Lett., 2009, vol.\u00a0109, no.\u00a017, pp.\u00a01010\u20131014. https:\/\/doi.org\/10.1016\/j.ipl.2009.06.005","journal-title":"Inform. Process. Lett."},{"key":"5102_CR17","doi-asserted-by":"crossref","unstructured":"Gurvich, V., Complexity of Generation, Computer Science \u2013 Theory and Applications: Proc. 13th Int. Computer Science Symp. in Russia (CSR 2018), Moscow, Russia, June 6\u201310, 2018, Fomin, F.V. and Podolskii, V.V., Eds., Lect. Notes Comput. Sci., vol.\u00a010846, Berlin, Heidelberg: Springer, 2018, pp.\u00a01\u201314. https:\/\/doi.org\/10.1007\/978-3-319-90530-3_1","DOI":"10.1007\/978-3-319-90530-3_1"},{"key":"5102_CR18","unstructured":"MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977."},{"key":"5102_CR19","unstructured":"Romashchenko, A.E., Rumyantsev, A.Yu., and Shen, A., Zametki po teorii kodirovaniya (Notes on Coding Theory), Moscow: MCCME, 2017, 2nd ed."},{"key":"5102_CR20","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Constructing Error-Correcting Codes from Expander Graphs, Emerging Applications of Number Theory, Hejhal, D.A., Friedman, J., Gutzwiller, M.C., and Odlyzko, A.M., Eds., IMA Volumes in Mathematics and Its Applications, vol.\u00a0109, New York: Springer, 1999, pp.\u00a0591\u2013600. https:\/\/doi.org\/10.1007\/978-1-4612-1544-8_25","DOI":"10.1007\/978-1-4612-1544-8_25"},{"key":"5102_CR21","doi-asserted-by":"crossref","unstructured":"Capalbo, M., Reingold, O., Vadhan, S., and Wigderson, A., Randomness Conductors and Constant-Degree Lossless Expanders, in Proc. 34th Annu. ACM Symp. on Theory of Computing (STOC\u201902), Montreal, Quebec, Canada, May 19\u201321, 2002, New York: ACM, 2002, pp.\u00a0659\u2013668. https:\/\/doi.org\/10.1145\/509907.510003","DOI":"10.1145\/509907.510003"},{"issue":"3","key":"5102_CR22","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1027914.1027924","volume":"35","author":"V. Guruswami","year":"2004","unstructured":"Guruswami, V., Guest Column: Error-Correcting Codes and Expander Graphs, SIGACT News, 2004, vol.\u00a035, no.\u00a03, pp.\u00a025\u201341. https:\/\/doi.org\/10.1145\/1027914.1027924","journal-title":"SIGACT News"},{"key":"5102_CR23","unstructured":"Schrijver, A., Theory of Linear and Integer Programming, Chichester: Wiley, 1986, vol.\u00a02."},{"key":"5102_CR24","doi-asserted-by":"crossref","unstructured":"Chistikov, D. and Vyalyi, M., Re-pairing Brackets, in Proc. 35th Annu. ACM\/IEEE Symp. on Logic in Computer Science (LICS\u201920), Saarbr\u00fccken, Germany, July 8\u201311, 2020, New York: ACM, 2020, pp.\u00a0312\u2013326. https:\/\/doi.org\/10.1145\/3373718.3394752","DOI":"10.1145\/3373718.3394752"}],"container-title":["Problems of Information Transmission"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946024030050.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S0032946024030050","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946024030050.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:54:40Z","timestamp":1775012080000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S0032946024030050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["5102"],"URL":"https:\/\/doi.org\/10.1134\/s0032946024030050","relation":{},"ISSN":["0032-9460","1608-3253"],"issn-type":[{"value":"0032-9460","type":"print"},{"value":"1608-3253","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"5 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors of this work declare that they have no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}