<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE root>
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" article-type="review-article" dtd-version="1.2" xml:lang="en"><front><journal-meta><journal-id journal-id-type="publisher-id">Informacionnye Tehnologii</journal-id><journal-title-group><journal-title xml:lang="en">Informacionnye Tehnologii</journal-title><trans-title-group xml:lang="ru"><trans-title>Информационные технологии</trans-title></trans-title-group></journal-title-group><issn publication-format="print">1684-6400</issn><publisher><publisher-name xml:lang="en">New Technologies Publishing House</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="publisher-id">702167</article-id><article-id pub-id-type="doi">10.17587/it.31.465-476</article-id><article-categories><subj-group subj-group-type="toc-heading" xml:lang="en"><subject>Modeling and optimization</subject></subj-group><subj-group subj-group-type="toc-heading" xml:lang="ru"><subject>Моделирование и оптимизация</subject></subj-group><subj-group subj-group-type="article-type"><subject>Review Article</subject></subj-group></article-categories><title-group><article-title xml:lang="en">A method for constructing combinatorial generation algorithms for context-free languages based on AND/OR tree structures</article-title><trans-title-group xml:lang="ru"><trans-title>Метод построения алгоритмов комбинаторной генерации для контекстно-свободных языков на основе структур деревьев И/ИЛИ*</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author"><name-alternatives><name xml:lang="en"><surname>Shablya</surname><given-names>Y. V.</given-names></name><name xml:lang="ru"><surname>Шабля</surname><given-names>Ю. В.</given-names></name></name-alternatives><address><country country="RU">Russian Federation</country></address><bio xml:lang="en"><p>Ph.D., Senior Researcher</p></bio><bio xml:lang="ru"><p>канд. техн. наук, ст. науч. сотр.</p></bio><email>syv@fb.tusur.ru</email><xref ref-type="aff" rid="aff1"/></contrib></contrib-group><aff-alternatives id="aff1"><aff><institution xml:lang="en">Tomsk State University of Control Systems and Radioelectronics</institution></aff><aff><institution xml:lang="ru">Томский государственный университет систем управления и радиоэлектроники</institution></aff></aff-alternatives><pub-date date-type="pub" iso-8601-date="2025-09-15" publication-format="electronic"><day>15</day><month>09</month><year>2025</year></pub-date><volume>31</volume><issue>9</issue><issue-title xml:lang="en">Informacionnye Tehnologii</issue-title><issue-title xml:lang="ru">Информационные технологии</issue-title><fpage>465</fpage><lpage>475</lpage><history><date date-type="received" iso-8601-date="2026-02-04"><day>04</day><month>02</month><year>2026</year></date><date date-type="accepted" iso-8601-date="2026-02-04"><day>04</day><month>02</month><year>2026</year></date></history><permissions><copyright-statement xml:lang="en">Copyright ©; 2025, Informacionnye Tehnologii</copyright-statement><copyright-statement xml:lang="ru">Copyright ©; 2025, Информационные технологии</copyright-statement><copyright-year>2025</copyright-year><copyright-holder xml:lang="en">Informacionnye Tehnologii</copyright-holder><copyright-holder xml:lang="ru">Информационные технологии</copyright-holder></permissions><self-uri xlink:href="https://journals.eco-vector.com/1684-6400/article/view/702167">https://journals.eco-vector.com/1684-6400/article/view/702167</self-uri><abstract xml:lang="en"><p>This paper considers the problem of constructing combinatorial generation algorithms for sets of discrete structures representing words of formal languages defined by context-free grammars. Existing combinatorial generation algorithms process only words of a given length from formal languages defined by context-free grammars, which is a limitation on their application. The main result of the study is the proposed method for constructing ranking and unranking algorithms, which is based on the mapping a given set onto a set of variants of the corresponding AND/OR tree. In comparison with existing analogues, the proposed method also allows processing both unambiguous and ambiguous context-free grammars. In addition, the use of the obtained unranking algorithms ensures uniform distribution of randomly generated words, but due to duplication of branches of the AND/OR tree, it is also possible to ensure non-uniform generation. At the same time, a distinctive feature of the obtained combinatorial generation algorithms is the ability to work with additional quantitative characteristics, which is absent in existing analogues. To confirm the performance of the proposed method, examples of constructing ranking and unranking algorithms for context-free languages according to the proposed method are presented. The ranking and unranking algorithms for context-free languages obtained using the proposed method can find their application in solving data compression problems and modeling objects described by words of such formal languages.</p></abstract><trans-abstract xml:lang="ru"><p>Рассматривается задача построения алгоритмов комбинаторной генерации для множеств дискретных структур, представляющих собой слова формальных языков, задаваемых контекстно-свободными грамматиками. Предлагается метод построения алгоритмов ранжирования и генерации по рангу, в основе которого лежит отображение заданного множества на множество структур вариантов соответствующего дерева И/ИЛИ. Представлены примеры построения алгоритмов комбинаторной генерации.</p></trans-abstract><kwd-group xml:lang="en"><kwd>combinatorial generation</kwd><kwd>formal language</kwd><kwd>context-free grammar</kwd><kwd>AND/OR tree</kwd><kwd>ranking algorithm</kwd><kwd>unranking algorithm</kwd></kwd-group><kwd-group xml:lang="ru"><kwd>комбинаторная генерация</kwd><kwd>формальный язык</kwd><kwd>контекстно-свободная грамматика</kwd><kwd>дерево И/ИЛИ</kwd><kwd>алгоритм ранжирования</kwd><kwd>алгоритм генерации по рангу</kwd></kwd-group><funding-group><funding-statement xml:lang="en">The work was carried out with the financial support of the Russian Science Foundation as part of a scientific project № 22-71-10052.</funding-statement><funding-statement xml:lang="ru">Работа выполнена при финансовой поддержке Российского научного фонда в рамках научного проекта № 22-71-10052.</funding-statement></funding-group></article-meta></front><body></body><back><ref-list><ref id="B1"><label>1.</label><mixed-citation>Chavan P. V., Jadhav A. Automata Theory and Formal Languages. USA, Cambridge: Academic Press, 2023. 232 p.</mixed-citation></ref><ref id="B2"><label>2.</label><mixed-citation>Kreher D. L., Stinson D. R. Combinatorial Algorithms: Generation, Enumeration, and Search. USA, Boca Raton: CRC Press, 1999. 342 p.</mixed-citation></ref><ref id="B3"><label>3.</label><mixed-citation>Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. USA, Boston: AddisonWesley Professional, 2011. 912 p.</mixed-citation></ref><ref id="B4"><label>4.</label><mixed-citation>Goldberg A. V., Sipser M. Compression and ranking // SIAM Journal on Computing. 1991. Vol. 20, N. 3. P. 524—536.</mixed-citation></ref><ref id="B5"><label>5.</label><mixed-citation>Huynh D. T. The complexity of ranking simple languages // Mathematical Systems Theory. 1990. Vol. 23. P. 1—19.</mixed-citation></ref><ref id="B6"><label>6.</label><mixed-citation>Lange K.-J., Rossmanith P., Rytter W. Parallel recognition and ranking of context-free languages // Mathematical Foundations of Computer Science. 1992. Р. 24—36.</mixed-citation></ref><ref id="B7"><label>7.</label><mixed-citation>Makinen E. Ranking and unranking left Szilard languages // International Journal of Computer Mathematics. 1998. Vol. 68, N. 1—2. P. 29—38.</mixed-citation></ref><ref id="B8"><label>8.</label><mixed-citation>Luchaup D., Shrimpton T., Ristenpart T., Jha S. Formatted encryption beyond regular languages // Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014. Р. 1292—1303.</mixed-citation></ref><ref id="B9"><label>9.</label><mixed-citation>Naganuma H., Hendrian D., Yoshinaka R., Shinohara A., Kobayashi N. Grammar compression with probabilistic contextfree grammar // 2020 Data Compression Conference. 2020. P. 386—386.</mixed-citation></ref><ref id="B10"><label>10.</label><mixed-citation>Hickey T., Cohen J. Uniform random generation of strings in a context-free language // SIAM Journal on Computing. 1983. Vol. 12, N. 4. P. 645—655.</mixed-citation></ref><ref id="B11"><label>11.</label><mixed-citation>Mairson H. G. Generating words in a context-free language uniformly at random // Information Processing Letters. 1994. Vol. 49, N. 2. P. 95—99.</mixed-citation></ref><ref id="B12"><label>12.</label><mixed-citation>Nebel M. E., Scheid A., Weinberg F. Random generation of RNA secondary structures according to native distributions // Algorithms for Molecular Biology. 2011. Vol. 6, N. 1.</mixed-citation></ref><ref id="B13"><label>13.</label><mixed-citation>Onokpasa E., Wild S., Wong P. W. H. RNA secondary structures: from ab initio prediction to better compression, and back // 2023 Data Compression Conference. 2023. P. 278—287.</mixed-citation></ref><ref id="B14"><label>14.</label><mixed-citation>Miracle S., Yilek S. Targeted invertible pseudorandom functions and deterministic format-transforming encryption // RSA Conference. 2023. P. 622—642.</mixed-citation></ref><ref id="B15"><label>15.</label><mixed-citation>Bellare M., Ristenpart T., Rogaway P., Stegers T. Format-preserving encryption // International Conference on Selected Areas in Cryptography. 2009. P. 295—312.</mixed-citation></ref><ref id="B16"><label>16.</label><mixed-citation>Bacchelli S., Barcucci E., Grazzini E., Pergola E. Exhaustive generation of combinatorial objects by ECO // Acta Informatica. 2004. Vol. 40. P. 585—602.</mixed-citation></ref><ref id="B17"><label>17.</label><mixed-citation>Flajolet P., Zimmermann P., Cutsem B. V. A calculus for the random generation of labelled combinatorial structures // Theoretical Computer Science. 1994. Vol. 132, N. 1—2. P. 1—35.</mixed-citation></ref><ref id="B18"><label>18.</label><mixed-citation>Ryabko B. Y. Fast enumeration of combinatorial objects // Discrete Mathematics and Applications. 1998. Vol. 8, N. 2. P. 163—182.</mixed-citation></ref><ref id="B19"><label>19.</label><mixed-citation>Hartung E., Hoang H. P., Mutze T., Williams A. Combinatorial generation via permutation languages. I. Fundamentals // Transactions of the American Mathematical Society. 2022. Vol. 375, N. 4. P. 2255—2291.</mixed-citation></ref><ref id="B20"><label>20.</label><mixed-citation>Кручинин В. В. Методы построения алгоритмов генерации и нумерации комбинаторных объектов на основе деревьев И/ИЛИ. Томск: В-Спектр, 2007. 200 с.</mixed-citation></ref><ref id="B21"><label>21.</label><mixed-citation>Shablya Y., Kruchinin D., Kruchinin V. Method for developing combinatorial generation algorithms based on AND/OR trees and its application // Mathematics. 2020. Vol. 8, N. 6. Article 962.</mixed-citation></ref><ref id="B22"><label>22.</label><mixed-citation>Shablya Y., Merinov A., Kruchinin D. Combinatorial gene ration algorithms for directed lattice paths // Mathematics. 2024. Vol. 12, N. 8. Article 1207.</mixed-citation></ref><ref id="B23"><label>23.</label><mixed-citation>Earley J. An efficient context-free parsing algorithm // Communications of the ACM. 1970. Vol. 13, N. 2. P. 94—102.</mixed-citation></ref><ref id="B24"><label>24.</label><mixed-citation>Шабля Ю. В. Алгоритмическое обеспечение комбинаторной генерации на основе применения теории производящих функций: дис. ... канд. техн. наук. Томск, 2019. 123 с.</mixed-citation></ref><ref id="B25"><label>25.</label><mixed-citation>Stanley R. P. Catalan Numbers. USA, Cambridge: Cambridge University Press, 2015. 224 p.</mixed-citation></ref><ref id="B26"><label>26.</label><mixed-citation>Kruchinin D., Kruchinin V., Shablya Y. On some properties of generalized Narayana numbers // Quaestiones Mathematicae. 2022. Vol. 45, N. 12. P. 1949—1963.</mixed-citation></ref><ref id="B27"><label>27.</label><citation-alternatives><mixed-citation xml:lang="en">Liebehenschel J. Ranking and unranking of a generalized Dyck language and the application to the generation of random trees // Seminaire Lotharingien de Combinatoire. 1999. Vol. 43. Article B43d.</mixed-citation><mixed-citation xml:lang="ru">Liebehenschel J. Ranking and unranking of a generalized Dyck language and the application to the generation of randomtrees // Seminaire Lotharingien de Combinatoire. 1999. Vol. 43. Article B43d.</mixed-citation></citation-alternatives></ref><ref id="B28"><label>28.</label><mixed-citation>Durocher S., Li P. C., Mondal D., Williams A. Ranking and loopless generation of k-ary Dyck words in cool-lex order // International Workshop on Combinatorial Algorithms. 2011. P. 182—194.</mixed-citation></ref><ref id="B29"><label>29.</label><mixed-citation>Kasa Z. Generating and ranking of Dyck words // Acta Universitatis Sapientiae, Informatica. 2009. Vol. 1, N. 1. P. 109—118.</mixed-citation></ref><ref id="B30"><label>30.</label><mixed-citation>Barcucci E., Pergola E., Pinzani R., Rinaldi S. ECO method and hill-free generalized Motzkin paths // Seminaire Lotharingien de Combinatoire. 2001. Vol. 46. Article B46b.</mixed-citation></ref><ref id="B31"><label>31.</label><mixed-citation>Medvedeva Y. S. Fast enumeration of words generated by Dyck grammars // Mathematical Notes. 2014. Vol. 96, N. 1. P. 68—83.</mixed-citation></ref><ref id="B32"><label>32.</label><mixed-citation>Kruchinin D., Kruchinin V., Shablya Y. Method for obtaining coefficients of powers of multivariate generating functions // Mathematics. 2023. Vol. 11, N. 13. Article 2859.</mixed-citation></ref></ref-list></back></article>
