- PII
- 10.31857/S0555292324030069-1
- DOI
- 10.31857/S0555292324030069
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 60 / Issue number 3
- Pages
- 46-58
- Abstract
- Рассмотрены описания конечных отношений на множестве неотрицательных целых чисел в формате, предложенном П. Вольф и Х. Фернау, и связанные с ними задачи регулярной реализуемости. Доказана универсальность этих задач относительно дизъюнктных сводимостей за полиномиальное время для унарных отношений; относительно дизъюнктных сводимостей на полиномиальной памяти для инвариантных бинарных отношений; а также относительно сводимостей по Тьюрингу с NP-оракулом для инвариантных унарных отношений, заданных в унарном алфавите.
- Keywords
- Date of publication
- 18.09.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 14
References
- 1. Yannakakis M. Graph-Theoretic Methods in Database Theory // Proc. 9th ACM SIGACTSIGMOD-SIGART Symp. on Principles of Database Systems (PODS’90). Nashville, TN, USA. Apr. 2–4, 1990. New York: ACM, 1990. P. 230–242. https://doi.org/10.1145/298514.298576
- 2. Bouajjani A., Esparza J., Maler O. Reachability Analysis of Pushdown Automata: Application to Model-Checking // Proc. Int. Conf. on Concurrency Theory (CONCUR’97). Warsaw, Poland. July 1–4, 1997. Lect. Notes Comput. Sci. V. 1243. Berlin, Heidelberg: Springer, 1997. P. 135–150. https://doi.org/10.1007/3-540-63141-0_10
- 3. Rubtsov A.A., Vyalyi M.N. Regular Realizability Problems and Context-Free Languages // Proc. 17th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS’2015). Waterloo, ON, Canada. June 25–27, 2015. Lect. Notes Comput. Sci. V. 9118. Berlin, Heidelberg: Springer, 2015. P. 256–267. https://doi.org/10.1007/978-3-319-19225-3_22
- 4. Chistikov D., Majumdar R., Schepper P. Subcubic Certificates for CFL Reachability // Proc. ACM Program. Lang. 2022. V. 6. Article 41 (29 pp.). https://doi.org/10.1145/3498702
- 5. Вялый М.Н. О задачах регулярной реализуемости // Пробл. передачи информ. 2011.
- 6. Т. 47. № 4. С. 43–54. https://www.mathnet.ru/rus/ppi2059
- 7. Вялый М.Н. О выразительной силе задач регулярной реализуемости // Пробл. передачи информ. 2013. Т. 49. № 3. С. 86–104. https://www.mathnet.ru/rus/ppi2117
- 8. Vyalyi M.N. On Models of a Nondeterministic Computation // Computer Science – Theory and Applications: Proc. 4th Int. Computer Science Symp. in Russia (CSR’09). Novosibirsk, Russia. Aug. 18–23, 2009. Lect. Notes Comput. Sci. V. 5675. Berlin, Heidelberg: Springer, 2009. P. 334–345. https://doi.org/10.1007/978-3-642-03351-3_31
- 9. Rubtsov A., Vyalyi M. Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems, https://arxiv.org/abs/2210.03934 [cs.FL], 2022.
- 10. Wolf P., 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 [cs.FL], 2020.
- 11. Wolf P. From Decidability to Undecidability by Considering Regular Sets of Instances // Theor. Comput. Sci. 2022. V. 899. P. 25–38. https://doi.org/10.1016/j.tcs.2021.11.006
- 12. Diekert V., Fernau H., Wolf P. Properties of Graphs Specified by a Regular Language // Acta Inform. 2022. V. 59. № 4. P. 357–385. https://doi.org/10.1007/s00236-022-00427-z
- 13. Rubtsov A., Vyalyi M. On Universality of Regular Realizability Problems // Probl. Inf. Transm. 2024. V. 60. № 3. P. 209–232. https://doi.org/10.1134/S0032946024030050
- 14. Chrobak M. Finite Automata and Unary Languages // Theor. Comput. Sci. 1986. V. 47. P. 149–158. https://doi.org/10.1016/0304-3975 (86)90142-8
- 15. 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–24, 2002. Dept. Comput. Sci., Univ. of Western Ontario, Canada, 2002. P. 174–187.
- 16. Chrobak M. Errata to: “Finite Automata and Unary Languages”: [Theoret. Comput. Sci. 47 (1986) 149–158] // Theor. Comput. Sci. 2003. V. 302. № 1–3. P. 497–498. https://doi.org/10.1016/S0304-3975 (03)00136-1
- 17. To A.W. Unary Finite Automata vs. Arithmetic Progressions // Inform. Process. Lett. 2009. V. 109. № 17. P. 1010–1014. https://doi.org/10.1016/j.ipl.2009.06.005
- 18. Gurvich V. Complexity of Generation // Computer Science – Theory and Applications: Proc. 13th Int. Computer Science Symp. in Russia (CSR 2018). Moscow, Russia. June 6–10, 2018. Lect. Notes Comput. Sci. V. 10846. Berlin, Heidelberg: Springer, 2018. P. 1–14. https: //doi.org/10.1007/978-3-319-90530-3_1
- 19. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
- 20. Ромащенко А.Е., Румянцев А.Ю., Шень А. Заметки по теории кодирования. М.: МЦНМО, 2017.
