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. 
@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/