# A characterization of poly-slender context-free languages

Lucian Ilie; Grzegorz Rozenberg; Arto Salomaa

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 1, page 77-86
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topIlie, Lucian, Rozenberg, Grzegorz, and Salomaa, Arto. "A characterization of poly-slender context-free languages." RAIRO - Theoretical Informatics and Applications 34.1 (2010): 77-86. <http://eudml.org/doc/222052>.

@article{Ilie2010,

abstract = {
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.
},

author = {Ilie, Lucian, Rozenberg, Grzegorz, Salomaa, Arto},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Context-free language; poly-slender language; Dyck loop.; context-free language; Dyck loop},

language = {eng},

month = {3},

number = {1},

pages = {77-86},

publisher = {EDP Sciences},

title = {A characterization of poly-slender context-free languages},

url = {http://eudml.org/doc/222052},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Ilie, Lucian

AU - Rozenberg, Grzegorz

AU - Salomaa, Arto

TI - A characterization of poly-slender context-free languages

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 1

SP - 77

EP - 86

AB -
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.

LA - eng

KW - Context-free language; poly-slender language; Dyck loop.; context-free language; Dyck loop

UR - http://eudml.org/doc/222052

ER -

## References

top- M. Andrasiu, J. Dassow, Gh. Paun and A. Salomaa, Language-theoretic problems arising from Richelieu cryptosystems. Theoret. Comput. Sci.116 (1993) 339-357.
- J.-M. Autebert, J. Bestel and L. Boasson, Context-free languages and push-down automata, edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin, Heidelberg (1997) 111-174.
- J. Berstel, Sur la densité asymptotique de langages formels, edited by M. Nivat, Automata, Languages, and Programming. North-Holland (1972) 345-358.
- C. Choffrut and J. Karhumäki, Combinatorics of Words, edited by G. Rozenberg and A. Salomaa, Handbook of Formal Languages. Springer-Verlag, Berlin, Heidelberg (1997) 329-438.
- J. Dassow, G. Paun and A. Salomaa, On thinness and slenderness of L languages. Bull. EATCS49 (1993) 152-158.
- S. Ginsburg and E.H. Spanier, Bounded ALGOL-like languages. Trans. Amer. Math. Soc.113 (1964) 333-368.
- J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci.52 (1996) 185-190.
- J. Honkala, Decision problems concerning thiness and slenderness of formal languages. Acta Inform.35 (1998) 625-636.
- L. Ilie, On a conjecture about slender context-free languages. Theoret. Comput. Sci.132 (1994) 427-434.
- L. Ilie, On lengths of words in context-free languages. Theoret. Comput. Sci. (to appear).
- M. Kunze, H.J. Shyr and G. Thierrin, h-bounded and semidiscrete languages. Inform. and Control51 (1981) 147-187.
- M. Latteux and G. Thierrin, Semidiscrete context-free languages. Internat. J. Comput. Math.14 (1983) 3-18.
- M. Latteux and G. Thierrin, On bounded context-free languages. Elektron. Informtionsverarb. Kybernet.20 (1984) 3-8.
- M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).
- T. Nishida and A. Salomaa, Slender 0L languages. Theoret. Comput. Sci.158 (1996) 161-176.
- Gh. Paun and A. Salomaa, Thin and slender languages. Discrete Appl. Math.61 (1995) 257-270.
- D. Raz, Length considerations in context-free languages. Theoret. Comput. Sci.183 (1997) 21-32.
- A. Salomaa, Formal Languages. Academic Press, New York (1973).
- J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. and Comput.113 (1994) 331-347.
- A. Szilard, S. Yu, K. Zhang and J. Shallit, Characterizing regular languages with polynomial densities, in Proc. of the 17th MFCS, Prague 1992. Springer, Berlin-New York, Lecture Notes in Comput. Sci.629 (1992) 494-503.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.