A method for constructing combinatorial generation algorithms for context-free languages based on AND/OR tree structures

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

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.

About the authors

Y. V. Shablya

Tomsk State University of Control Systems and Radioelectronics

Author for correspondence.
Email: syv@fb.tusur.ru

Ph.D., Senior Researcher

Russian Federation, Tomsk

References

  1. Chavan P. V., Jadhav A. Automata Theory and Formal Languages. USA, Cambridge: Academic Press, 2023. 232 p.
  2. Kreher D. L., Stinson D. R. Combinatorial Algorithms: Generation, Enumeration, and Search. USA, Boca Raton: CRC Press, 1999. 342 p.
  3. Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. USA, Boston: AddisonWesley Professional, 2011. 912 p.
  4. Goldberg A. V., Sipser M. Compression and ranking // SIAM Journal on Computing. 1991. Vol. 20, N. 3. P. 524—536.
  5. Huynh D. T. The complexity of ranking simple languages // Mathematical Systems Theory. 1990. Vol. 23. P. 1—19.
  6. Lange K.-J., Rossmanith P., Rytter W. Parallel recognition and ranking of context-free languages // Mathematical Foundations of Computer Science. 1992. Р. 24—36.
  7. Makinen E. Ranking and unranking left Szilard languages // International Journal of Computer Mathematics. 1998. Vol. 68, N. 1—2. P. 29—38.
  8. 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.
  9. Naganuma H., Hendrian D., Yoshinaka R., Shinohara A., Kobayashi N. Grammar compression with probabilistic contextfree grammar // 2020 Data Compression Conference. 2020. P. 386—386.
  10. 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.
  11. Mairson H. G. Generating words in a context-free language uniformly at random // Information Processing Letters. 1994. Vol. 49, N. 2. P. 95—99.
  12. 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.
  13. 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.
  14. Miracle S., Yilek S. Targeted invertible pseudorandom functions and deterministic format-transforming encryption // RSA Conference. 2023. P. 622—642.
  15. Bellare M., Ristenpart T., Rogaway P., Stegers T. Format-preserving encryption // International Conference on Selected Areas in Cryptography. 2009. P. 295—312.
  16. Bacchelli S., Barcucci E., Grazzini E., Pergola E. Exhaustive generation of combinatorial objects by ECO // Acta Informatica. 2004. Vol. 40. P. 585—602.
  17. 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.
  18. Ryabko B. Y. Fast enumeration of combinatorial objects // Discrete Mathematics and Applications. 1998. Vol. 8, N. 2. P. 163—182.
  19. 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.
  20. Кручинин В. В. Методы построения алгоритмов генерации и нумерации комбинаторных объектов на основе деревьев И/ИЛИ. Томск: В-Спектр, 2007. 200 с.
  21. 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.
  22. Shablya Y., Merinov A., Kruchinin D. Combinatorial gene ration algorithms for directed lattice paths // Mathematics. 2024. Vol. 12, N. 8. Article 1207.
  23. Earley J. An efficient context-free parsing algorithm // Communications of the ACM. 1970. Vol. 13, N. 2. P. 94—102.
  24. Шабля Ю. В. Алгоритмическое обеспечение комбинаторной генерации на основе применения теории производящих функций: дис. ... канд. техн. наук. Томск, 2019. 123 с.
  25. Stanley R. P. Catalan Numbers. USA, Cambridge: Cambridge University Press, 2015. 224 p.
  26. Kruchinin D., Kruchinin V., Shablya Y. On some properties of generalized Narayana numbers // Quaestiones Mathematicae. 2022. Vol. 45, N. 12. P. 1949—1963.
  27. 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.
  28. 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.
  29. Kasa Z. Generating and ranking of Dyck words // Acta Universitatis Sapientiae, Informatica. 2009. Vol. 1, N. 1. P. 109—118.
  30. 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.
  31. Medvedeva Y. S. Fast enumeration of words generated by Dyck grammars // Mathematical Notes. 2014. Vol. 96, N. 1. P. 68—83.
  32. Kruchinin D., Kruchinin V., Shablya Y. Method for obtaining coefficients of powers of multivariate generating functions // Mathematics. 2023. Vol. 11, N. 13. Article 2859.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Informacionnye Tehnologii


СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ПИ № 77 - 15565 от 02 июня 2003 г.