Geodesic
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. 
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/
@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},
     year = {2014},
     volume = {96},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a4/
%G ru
%F 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