A characterization of poly-slender context-free languages
Ilie, Lucian; Rozenberg, Grzegorz; Salomaa, Arto; Ilie Lucian; Turku Centre for Computer Science TUCS, 20520 Turku, Finland.; Research supported by the Academy of Finland, Project 137358. On leave of absence from Faculty of Mathematics, University of Bucharest, Str. Academiei 14, 70109 Bucharest, Romania.; Rozenberg Grzegorz; Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands and Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309, U.S.A.; Salomaa Arto; Turku Centre for Computer Science TUCS, 20520 Turku, Finland.Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands and Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309, U.S.A.
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
2000
Аннотация:
For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order ${\cal O}(n^k)$. We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.
158.2Кб