Вычислимые изоморфизмы относительно регулярных булевых алгебр

Вычислимые изоморфизмы относительно регулярных булевых алгебр

Шиманогов И. Н., Вялый М. Н.
Сибирский математический журнал, 67, 5, 1007-1019 (2026)
Скачать статью

УДК 519.713.2+512.563 
DOI: 10.33048/smzh.2026.67.519

Аннотация:

Рассматривается класс булевых алгебр, образуемых пересечениями регулярных языков с заданным языком. В случае, когда такая алгебра изоморфна алгебре регулярных языков, доказывается существование изоморфизма, вычислимого с использованием оракулов для задачи регулярной реализуемости и бесконечной регулярной реализуемости. Данный результат дает существование вычислимого изоморфизма булевых алгебр регулярных языков над алфавитом из одной буквы и из двух букв. Также строится нижняя оценка сложности этой задачи.

Литература:
  1. Vyalyi M. On models of a nondeterministic computation // Lecture Notes in Computer Science. 2009. V. 5675. P. 334–345.
     
  2. Bouajjani A., Esparza J., Maler O. Reachability analysis of pushdown automata: Application to model-checking // Lecture Notes in Computer Science. 1997. V. 1243. P. 135–150.
     
  3. Chistikov D., Majumdar R., Schepper P. Subcubic certificates for CFL reachability // Proc. ACM Program. Lang. 2022. V. 6. Article 41. 29 pp.
     
  4. Koutris P., Deep S. The fine-grained complexity of CFL reachability // Proc. ACM Program. Lang. 2023. V. 7. Article 59. 27 pp.
     
  5. Wolf P. From decidability to undecidability by considering regular sets of instances // Theoretical Computer Sci. 2022. V. 899. P. 25–38.
     
  6. Wolf P., Fernau H. Regular Intersection emptiness of graph problems: Finding a needle in a haystack of graphs with the help of automata // 2020. V. 29. https://arxiv.org/abs/2003.05826
     
  7. Diekert V., Fernau H., Wolf P. Properties of graphs specified by a regular language // Acta Informatica. 2022. V. 59. P. 357–385.
     
  8. Wolf P. On the decidability of finding a positive ILP-instance in a regular set of ILP-instances // Acta Informatica. 2022. V. 59. P. 505–519.
     
  9. Шиманогов И. Н., Вялый М. Н. Классификация относительно регулярных алгебр // Тр. МФТИ. 2024. Т. 16, № 4. С. 128–134.
     
  10. Голубенко Д. A., Саватеев Ю. В. Языки, автоматы и грамматики. М.: МЦНМО, 2023.
     
  11. Bridson M. R., Gilman R. H. Context-free languages of sub-exponential growth // J. Computer System Sci. 2002. V. 64, N 2. P. 308–310.
     
  12. Anderson T., Loftus J., Rampersad N., Santean N., Shallit J. Detecting palindromes, patterns and borders in regular languages // Information and Computation. 2009. V. 207. P. 1096–1118.
     
  13. Shallit J. A second course in formal languages and automata theory. Cambridge: Camb. Univ. Press, 2008.
     
  14. Arora S., Barak B. Computational complexity: A modern approach. Cambridge: Camb. Univ. Press, 2009.
     
  15. Гончаров C. C. Счетные булевы алгебры и разрешимость. Новосибирск: Науч. книга, 1996.
     
  16. Selivanov V., Konovalov A. Boolean algebras of regular languages // Developments in language theory. Berlin; Heidelberg: Springer, 2011. P. 386–396. (Lecture Notes in Computer Sci.; V. 6795)

Исследование второго автора финансировалось в рамках госзадания FFNG-2024-0003.

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

E-mail: shimanogov.in@phystech.edu 

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

E-mail: vyalyi@gmail.com 

Статья поступила 10 декабря 2025 г.
После доработки — 18 июня 2026 г.
Принята к публикации 24 июня 2026 г.