Fast Enumeration of Words Generated by Dyck Grammars
Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 51-69.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 Schönhage–Strassen multiplication and division algorithm is used. The well-known methods applied earlier possess complexity $O(n)$ per one symbol of enumerated words. The construction of the proposed algorithm is based on the Ryabko method.
Keywords: ranking and unranking of words, fast enumeration and denumeration of words, enumerative encoding, Dyck language.
@article{MZM_2014_96_1_a4,
     author = {Yu. S. Medvedeva},
     title = {Fast {Enumeration} of {Words} {Generated} by {Dyck} {Grammars}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {51--69},
     publisher = {mathdoc},
     volume = {96},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a4/}
}
TY  - JOUR
AU  - Yu. S. Medvedeva
TI  - Fast Enumeration of Words Generated by Dyck Grammars
JO  - Matematičeskie zametki
PY  - 2014
SP  - 51
EP  - 69
VL  - 96
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a4/
LA  - ru
ID  - MZM_2014_96_1_a4
ER  - 
%0 Journal Article
%A Yu. S. Medvedeva
%T Fast Enumeration of Words Generated by Dyck Grammars
%J Matematičeskie zametki
%D 2014
%P 51-69
%V 96
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a4/
%G ru
%F MZM_2014_96_1_a4
Yu. S. Medvedeva. Fast Enumeration of Words Generated by Dyck Grammars. Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 51-69. http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a4/

[1] T. J. Lunch, “Sequence time coding for data compression”, Proc. IEEE, 54:10 (1966), 1490–1491 | DOI

[2] Yu. S. Medvedeva, B. Ya. Ryabko, “Bystryi algoritm numeratsii slov s zadannymi ogranicheniyami na dliny serii edinits”, Probl. peredachi inform., 46:4 (2010), 130–139 | MR | Zbl

[3] T. M. Cover, “Enumerative Source Encoding”, IEEE Trans. Information Theory, IT-19:1 (1973), 73–77 | MR

[4] B. Ya. Ryabko, “Bystraya numeratsiya kombinatornykh ob'ektov”, Diskret. matem., 10:2 (1998), 101–119 | DOI | MR | Zbl

[5] A. E. Pentus, M. R. Pentus, Teoriya formalnykh yazykov, Uchebnoe posobie, Izd-vo TsPI pri mekh.-mat. fak-te MGU, M., 2004

[6] E. Reingold, Yu. Nivergelt, N. Deo, Kombinatornye algoritmy. Teoriya i praktika, Mir, M., 1980 | MR

[7] A. V. Akho, M. S. Lam, R. Seti, D. D. Ulman, Kompilyatory. Printsipy, tekhnologii i instrumentarii, Vilyams, M., 2008

[8] R. E. Krichevskii, Szhatie i poisk informatsii, Radio i svyaz, M., 1989 | MR

[9] A. Schönhage, V. Strassen, “Schnelle Multiplikation grosser Zahlen”, Computing, 7:3-4 (1971), 281–292 | DOI | MR | Zbl

[10] M. Fürer, “Faster integer multiplication”, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, 57–66 | DOI | MR | Zbl

[11] A. Shen, Programmirovanie: teoremy i zadachi, MTsNMO, M., 2004