ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 9. Vol. 31. 2025

DOI: 10.17587/it.31.465-476

Y. V. Shablya, Ph.D., Senior Researcher,
Tomsk State University of Control Systems and Radioelectronics, Tomsk, 634050, Russian Federation

A Method for Constructing Combinatorial Generation Algorithms for Context-Free Languages Based on AND/OR Tree Structures

Received on 28.08.2024
Accepted on 17.01.2025

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.
Keywords: combinatorial generation, formal language, context-free grammar, AND/OR tree, ranking algorithm, unranking algorithm

P. 465-476

Full text on eLIBRARY

References

1. Chavan P. V., Jadhav A. Automata theory and formal lan­guages, 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, Addison-Wesley Professional, 2011, 912 p.
4. Goldberg A. V., Sipser M. Compression and ranking, SIAM Journal on Computing, 1991, vol. 20, no. 3, pp. 524—536.
5. Huynh D. T. The complexity of ranking simple languages, Mathematical Systems Theory, 1990, vol. 23, pp. 1—19.
6. Lange K.-J., Rossmanith P., Rytter W. Parallel recognition and ranking of context-free languages, Mathematical Foundations of Computer Science, 1992, pp. 24—36.
7. Makinen E. Ranking and unranking left Szilard languages, International Journal of Computer Mathematics, 1998, vol. 68, no. 1—2, pp. 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, pp. 1292—1303.
9. Naganuma H., Hendrian D., Yoshinaka R., Shino-hara A., Kobayashi N. Grammar compression with probabilistic context-free grammar, 2020 Data Compression Conference, 2020, pp. 386—386.
10. Hickey T., Cohen J. Uniform random generation of strings in a context-free language, SIAM Journal on Computing, 1983, vol. 12, no. 4, pp. 645—655.
11. Mairson H. G. Generating words in a context-free language uniformly at random, Information Processing Letters, 1994, vol. 49, no. 2, pp. 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, no. 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, pp. 278—287.
14. Miracle S., Yilek S. Targeted invertible pseudorandom functions and deterministic format-transforming encryption, RSA Conference, 2023, pp. 622—642.
15. Bellare M., Ristenpart T., Rogaway P., Stegers T. Format-preserving encryption, International Conference on Selected Areas in Cryptography, 2009, pp. 295—312.
16. Bacchelli S., Barcucci E., Grazzini E., Pergola E. Ex­haustive generation of combinatorial objects by ECO, Acta Informatica, 2004, vol. 40, pp. 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, no. 1—2, pp. 1—35.
18. Ryabko B. Y. Fast enumeration of combinatorial objects, Discrete Mathematics and Applications, 1998, vol. 8, no. 2, pp. 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, no. 4, pp. 2255—2291.
20. Kruchinin V. V. Methods for constructing algorithms for generating and numbering combinatorial objects based on AND/OR trees, Tomsk, V-Spektr, 2007, 200 p. (in Russian).
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, no. 6, Article 962.
22. Shablya Y., Merinov A., Kruchinin D. Combinatorial generation algorithms for directed lattice paths, Mathematics, 2024, vol. 12, no. 8, Article 1207.
23. Earley J. An efficient context-free parsing algorithm, Communications of the ACM, 1970, vol. 13, no. 2, pp. 94—102.
24. Shablya Y. V. Algorithmic support for combinatorial generation based on the application of the theory of generating functions, Tomsk, 2019, 123 p. (in Russian).
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, no. 12, pp. 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. 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, pp. 182—194.
29. Kasa Z. Generating and ranking of Dyck words, Acta Universitatis Sapientiae, Informatica, 2009, vol. 1, no. 1, pp. 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, no. 1, pp. 68—83.
32. Kruchinin D., Kruchinin V., Shablya Y. Method for obtaining coefficients of powers of multivariate generating functions, Mathematics, 2023, vol. 11, no. 13, Article 2859.

To the contents