Задачи бесконечной регулярной реализуемости

Задачи бесконечной регулярной реализуемости

Шиманогов И. Н., Вялый М. Н.
Дискретный анализ и исследование операций, 32, 4, 213-230 (2025)
Скачать статью

УДК 519.713 
DOI: 10.33048/daio.2025.32.822

Аннотация:

Хорошо изученным классом алгоритмических задач являются задачи регулярной реализуемости — проверки непустоты пересечения регулярного языка с заданным языком. Такая задача имеет естественную алгебраическую интерпретацию — проверку принадлежности элемента булевой алгебры ядру определённого гомоморфизма. Это мотивирует рассмотрение аналогичной задачи бесконечной регулярной реализуемости — проверки бесконечности пересечения регулярного языка с заданным. В работе рассматриваются задачи регулярной реализуемости для разрешимых языков и приводится сравнительный анализ сложности задач бесконечной регулярной реализуемости и задач регулярной реализуемости. 

Библиогр. 22.

Литература:
  1. Bouajjani A., Esparza J., Maler O. Reachability analysis of pushdown automata: Application to model-checking // CONCUR’97: Concurrency theory. Proc. 8th Int. Conf. (Warsaw, Poland, July 1–4, 1997). Heidelberg: Springer, 1997. P. 135–150. (Lect. Notes Comput. Sci.; V. 1243). DOI: 10.1007/ 3-540-63141-0_10.
     
  2. Rubtsov A., Vyalyi M. Regular realizability problems and context-free languages // Descriptional complexity of formal systems. Proc. 17th Int. Workshop DCFS 2015 (Waterloo, ON, Canada, June 25–27, 2015). Cham: Springer, 2015. P. 256–267. (Lect. Notes Comput. Sci.; V. 9118). DOI: 10.1007/ 978-3-319-19225-3_22.
     
  3. Chistikov D., Majumdar R., Schepper P. Subcubic certificates for CFL reachability // Proc. ACM Program. Lang. 2022. V. 6, No. POPL. Article ID 41. 29 p. DOI: 10.1145/3498702.
     
  4. Pavlogiannis A. CFL/Dyck reachability: An algorithmic perspective // ACM SIGLOG News. 2023. V. 9, No. 4. P. 5–25. DOI: 10.1145/3583660.3583664.
     
  5. Kjelstrøm A. H., Pavlogiannis A. The decidability and complexity of interleaved bidirected Dyck reachability // Proc. ACM Program. Lang. 2022. V. 6, No. POPL. Article ID 12. 26 p. DOI: 10.1145/3498673.
     
  6. Koutris P., Deep S. The fine-grained complexity of CFL reachability // Proc. ACM Program. Lang. 2023. V. 7, No. POPL. Article ID 59. 27 p. DOI: 10.1145/ 3571252.
     
  7. Anderson T., Loftus J., Rampersad N., Santean N., Shallit J. Detecting palindromes, patterns and borders in regular languages // Inf. Comput. 2009. V. 207. P. 1096–1118. DOI: 10.1016/j.ic.2008.06.007.
     
  8. Wolf P., Fernau H. Regular intersection emptiness of graph problems: Finding a needle in a haystack of graphs with the help of automata. Ithaca, NY, 2020. 29 p. (e-Print Archive / Cornell Univ.; arXiv:2003.05826). DOI: 10.48550/arXiv.2003.05826.
     
  9. Wolf P. From decidability to undecidability by considering regular sets of instances // Theor. Comput. Sci. 2022. V. 899. P. 25–38. DOI: 10.1016/j.tcs. 2021.11.006.
     
  10. Diekert V., Fernau H., Wolf P. Properties of graphs specified by a regular language // Acta Inform. 2022. V. 59. P. 357–385. DOI: 10.1007/ s00236-022-00427-z.
     
  11. Wolf P. On the decidability of finding a positive ILP-instance in a regular set of ILP-instances // Acta Inform. 2022. V. 59. P. 505–519. DOI: 10.1007/ s00236-022-00429-x.
     
  12. Feder T., Vardi M. Y. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory // SIAM J. Comput. 1999. V. 28, No. 1. P. 57–104.
     
  13. Bulatov A. A. A dichotomy theorem for nonuniform CSPs // Proc. 58th IEEE Annu. Symp. Foundations of Computer Science (Berkeley, CA, USA, Oct. 15–17, 2017). Piscataway: IEEE, 2017. P. 319–330. DOI: 10.1109/FOCS. 2017.37
     
  14. Zhuk D. A proof of CSP dichotomy conjecture // Proc. 58th IEEE Annu. Symp. Foundations of Computer Science (Berkeley, CA, USA, Oct. 15–17, 2017). Piscataway: IEEE, 2017. P. 331–342. DOI: 10.1109/FOCS.2017.38 
     
  15. Bulatov A. A. A dichotomy theorem for nonuniform CSPs. Ithaca, NY, 2017. 101 p. (e-Print Archive / Cornell Univ.; arXiv:1703.03021). DOI: 10.48550/ arXiv.1703.03021.
     
  16. Zhuk D. A proof of the CSP dichotomy conjecture // J. ACM. 2020. V. 67, No. 5. Article ID 30. 78 p. DOI: 10.1145/3402029.
     
  17. Вялый М. Н., Рубцов А. А. Задачи регулярной реализуемости для описаний конечных отношений // Пробл. передачи информации. 2024. Т. 60, № 3. С. 46–58.
     
  18. Soare R. Turing computability: Theory and applications. Heidelberg: Springer, 2016. 264 p. DOI: 10.1007/978-3-642-3.
     
  19. Kozen D. Automata and computability. New York: Springer, 2012. 400 p. DOI: 10.1007/978-1-4612-1844-9.
     
  20. Shallit J. O. A second course in formal languages and automata theory. New York: Camb. Univ. Press, 2008. 240 p. DOI: 10.1017/CBO9780511808876.
     
  21. Шиманогов И. Н., Вялый М. Н. Классификация относительно регулярных алгебр // Тр. МФТИ. 2024. Т. 16, № 4. C. 128–134.
     
  22. Гончаров С. C. Счётные булевы алгебры и разрешимость. Новосибирск: Науч. книга, 1996. 364 c.

Работа второго автора выполнена в рамках Программы фундаментальных исследований НИУ ВШЭ, а также имеет частичную финансовую поддержку в рамках гос. задания (проект № FFNG–2024–0003). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Шиманогов Игорь Николаевич
  1. Московский физико-технический институт (национальный исследовательский университет) 
    ул. Керченская, 1А, корп. 1, 117303 Москва, Россия

E-mail: shimanogov.in@phystech.edu 

Вялый Михаил Николаевич
  1. Московский физико-технический институт (национальный исследовательский университет) 
    ул. Керченская, 1А, корп. 1, 117303 Москва, Россия
  2. Федеральный исследовательский центр «Информатика и управление» РАН 
    ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
  3. Национальный исследовательский университет «Высшая школа экономики», 
    Покровский б-р, 11, 109028 Москва, Россия

E-mail: vyalyi@gmail.com 

Статья поступила 9 декабря 2024 г.
После доработки — 20 августа 2025 г.
Принята к публикации 22 сентября 2025 г.

Abstract:

A well-studied class of algorithmic problems is that of regular realizability, i.e. checking the non-emptiness of the intersection of a regular language with a given language. This problem has a natural algebraic interpretation which is verifying whether an element of a Boolean algebra belongs to the kernel of a certain homomorphism. This motivates the consideration of a similar problem of infinite regular realizability that is checking whether the intersection of a regular language with a given language is infinite. The paper examines the case of decidable languages and provides a comparative analysis of the complexity of infinite regular realizability problems versus regular realizability problems. 

Bibliogr. 22.

References:
  1. A. Bouajjani, J. Esparza, and O. Maler, Reachability analysis of pushdown automata: Application to model-checking, in CONCUR’97: Concurrency Theory, Proc. 8th Int. Conf. (Warsaw, Poland, July 1–4, 1997) (Springer, Heidelberg, 1997), pp. 135–150 (Lect. Notes Comput. Sci., V. 1243), DOI: 10.1007/3-540-63141-0_10.
     
  2. A. Rubtsov and M. Vyalyi, Regular realizability problems and context-free languages, in Descriptional Complexity of Formal Systems, Proc. 17th Int. Workshop DCFS 2015 (Waterloo, ON, Canada, June 25–27, 2015) (Springer, Cham, 2015), pp. 256–267 (Lect. Notes Comput. Sci., V. 9118), DOI: 10.1007/ 978-3-319-19225-3_22. 
     
  3. D. Chistikov, R. Majumdar, and P. Schepper, Subcubic certificates for CFL reachability, Proc. ACM Program. Lang. 6 (POPL), ID 41 (2022), DOI: 10.1145/3498702.
     
  4. A. Pavlogiannis, CFL/Dyck reachability: An algorithmic perspective, ACM SIGLOG News 9 (4), 5–25 (2023), DOI: 10.1145/3583660.3583664.
     
  5. A. H. Kjelstrøm and A. Pavlogiannis, The decidability and complexity of interleaved bidirected Dyck reachability, Proc. ACM Program. Lang. 6 (POPL), ID 12 (2022), DOI: 10.1145/3498673.
     
  6. P. Koutris and S. Deep, The fine-grained complexity of CFL reachability, Proc. ACM Program. Lang. 7 (POPL), ID 59 (2023), DOI: 10.1145/3571252.
     
  7. T. Anderson, J. Loftus, N. Rampersad, N. Santean, and J. Shallit, Detecting palindromes, patterns and borders in regular languages, Inf. Comput. 207, 1096–1118 (2009), DOI: 10.1016/j.ic.2008.06.007.
     
  8. P. Wolf and H. Fernau, Regular intersection emptiness of graph problems: Finding a needle in a haystack of graphs with the help of automata (Ithaca, NY, 2020) (e-Print Archive / Cornell Univ., arXiv:2003.05826), DOI: 10.48550/ arXiv.2003.05826.
     
  9. P. Wolf, From decidability to undecidability by considering regular sets of instances, Theor. Comput. Sci. 899, 25–38 (2022), DOI: 10.1016/j.tcs.2021. 11.006.
     
  10. V. Diekert, H. Fernau, and P. Wolf, Properties of graphs specified by a regular language, Acta Inform. 59, 357–385 (2022), DOI: 10.1007/ s00236-022-00427-z.
     
  11. P. Wolf, On the decidability of finding a positive ILP-instance in a regular set of ILP-instances, Acta Inform. 59, 505–519 (2022), DOI: 10.1007/ s00236-022-00429-x.
     
  12. T. Feder and M. Y. Vardi, The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput. 28 (1), 57–104 (1999).
     
  13. A. A. Bulatov, A dichotomy theorem for nonuniform CSPs, in Proc. 58th IEEE Annu. Symp. Foundations of Computer Science (Berkeley, CA, USA, Oct. 15–17, 2017) (IEEE, Piscataway, 2017), pp. 319–330, DOI: 10.1109/FOCS. 2017.37
     
  14. D. Zhuk, A proof of CSP dichotomy conjecture, in Proc. 58th IEEE Annu. Symp. Foundations of Computer Science (Berkeley, CA, USA, Oct. 15–17, 2017) (IEEE, Piscataway, 2017), pp. 331–342, DOI: 10.1109/FOCS.2017.38
     
  15. A. A. Bulatov, A dichotomy theorem for nonuniform CSPs (Ithaca, NY, 2017) (e-Print Archive / Cornell Univ., arXiv:1703.03021), DOI: 10.48550/arXiv. 1703.03021.
     
  16. D. Zhuk, A proof of the CSP dichotomy conjecture, J. ACM 67 (5), ID 30 (2020), DOI: 10.1145/3402029.
     
  17. M. N. Vyalyi and A. A. Rubtsov, Regular realizability problems for descriptions of finite relations, Probl. Peredachi Inf. 60 (3), 46–58 (2024) [Russian] [On universality of regular realizability problems, Probl. Inf. Transm. 60 (3), 209–232 (2024), DOI: 10.1134/S0032946024030050].
     
  18. R. Soare, Turing Computability: Theory and Applications (Springer, Heidelberg, 2016), DOI: 10.1007/978-3-642-3.
     
  19. D. Kozen, Automata and Computability (Springer, New York, 2012), DOI: 10.1007/978-1-4612-1844-9.
     
  20. J. O. Shallit, A Second Course in Formal Languages and Automata Theory (Camb. Univ. Press, New York, 2008), DOI: 10.1017/CBO9780511808876.
     
  21. I. N. Shimanogov and M. N. Vyalyi, Classification of relative regular algebras, Tr. MFTI 16 (4), 128–134 (2024) [Russian].
     
  22. S. C. Goncharov, Countable Boolean Algebras and Decidability (Nauchn. Kniga, Novosibirsk, 1996) [Russian].