| Issue |
RAIRO-Theor. Inf. Appl.
Volume 34, Number 1, January/February 2000
|
|
|---|---|---|
| Page(s) | 77 - 86 | |
| DOI | https://doi.org/10.1051/ita:2000100 | |
| Published online | 15 April 2002 | |
A characterization of poly-slender context-free languages
1
Turku Centre for Computer Science TUCS,
20520 Turku, Finland.
2
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.
3
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.
4
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.
Received:
8
October
1999
Accepted:
8
February
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 
. 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.
Mathematics Subject Classification: 68Q45 / 68Q70
Key words: Context-free language / poly-slender language / Dyck loop.
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.