Fast Enumeration of Words Generated by Dyck Grammars

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.