Back to Search
Start Over
Fast enumeration of words generated by Dyck grammars.
- Source :
-
Mathematical Notes . Jul2014, Vol. 96 Issue 1/2, p68-83. 16p. - Publication Year :
- 2014
-
Abstract
- 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 n log log n) bit operations, provided that the Schönhage-Strassen multiplication and division algorithmis used. The well-knownmethods applied earlier possess complexity O( n) per one symbol of enumerated words. The construction of the proposed algorithm is based on the Ryabko method. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LISTS
*ALGORITHMS
*MATHEMATICS
*COMPILERS (Computer programs)
*PROGRAMMING software
Subjects
Details
- Language :
- English
- ISSN :
- 00014346
- Volume :
- 96
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Mathematical Notes
- Publication Type :
- Academic Journal
- Accession number :
- 97565336
- Full Text :
- https://doi.org/10.1134/S0001434614070062