Инд. авторы:	Medvedeva Yu. S.
Заглавие:	Fast enumeration of words generated by Dyck grammars
Библ. ссылка:	Medvedeva Yu. S. Fast enumeration of words generated by Dyck grammars // Mathematical Notes. - 2014. - Vol.96. - Iss. 1-2. - P.68-83. - ISSN 0001-4346. - EISSN 1573-8876.
Внешние системы:	DOI: 10.1134/S0001434614070062; РИНЦ: 23984335; SCOPUS: 2-s2.0-84906508933; WoS: 000340938800006;
Реферат:	eng: The problem of enumerating and denumerating words generated by Dyck grammars arises in the work of compilers for high-level programming languages and a number of other applications. The present paper proposes an algorithm for the fast enumeration and denumeration of words of Dyck languages; the complexity of this algorithm per one symbol of enumerated words is O(log(3) n log log n) bit operations, provided that the Schonhage-Strassen multiplication and division algorithmis used. The well-knownmethods applied earlier possess complexityO(n) per one symbol of enumerated words. The construction of the proposed algorithm is based on the Ryabko method.
Ключевые слова:	Dyck language; enumerative encoding; fast enumeration and denumeration of words; ranking and unranking of words;
Издано:	2014
Физ. характеристика:	с.68-83
Цитирование:	1. T. J. Lunch, "Sequence time coding for data compression," Proc. IEEE 54(10), 1490-1491 (1966). 2. Yu. S. Medvedeva and B. Ya. Ryabko, "A fast algorithm for the enumeration of words with given constraints on the run lengths of ones," Problemy Peredachi Informatsii 46(4), 130-139 (2010) [Probl. Inform. Transm. 46 (4), 390-399 (2010)]. 3. T. M. Cover, "Enumerative Source Encoding," IEEE Trans. Information Theory IT-19(1), 73-77 (1973). 4. B. Ya. Ryabko, "Fast enumeration of combinatorial objects," Diskret. Mat. 10(2), 101-119 (1998) [Discrete Math. Appl. 8 (2), 163-182 (1998)]. 5. A. E. Pentus and M. R. Pentus, Theory of Formal Languages, A manual (Izd. TsPI, Mekh.-Mat. Moskov. Univ., Moscow, 2004) [in Russian]. 6. E. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice (Prentice-Hall, Englewood Cliffs, NJ, 1977; Mir, Moscow, 1980). Compilers: Principles, Techniques, and Tools[1] is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction. 7. A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools (Pearson Education, Inc., 2006; Williams, Moscow, 2008). 8. R. E. Krichevskii, Information Compression and Search (Radio i Svyaz, Moscow, 1989) [in Russian]. 9. A. Schönhage and V. Strassen, "Schnelle Multiplikation grosser Zahlen," Computing 7(3-4), 281-292 (1971). 10. M. Fürer, "Faster integer multiplication," in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (ACM, New York, 2007), pp. 57-66. 11. A. Shen', Programming: Theorems and Problems (MTsNMO, Moscow, 2004) [in Russian].