Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T17:23:27.468Z Has data issue: false hasContentIssue false
  • English
  • Français

A characterization of poly-slender context-free languages

Published online by Cambridge University Press:  15 April 2002

Lucian Ilie ,
Grzegorz Rozenberg  and
Arto Salomaa
Lucian Ilie
Affiliation:
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.
Grzegorz Rozenberg
Affiliation:
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.
Arto Salomaa
Affiliation:
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.
Get access

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.

Keywords

Context-free languagepoly-slender languageDyck loop.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 1 , January 2000 , pp. 77 - 86
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andrasiu, M., Dassow, J., Paun, Gh. and Salomaa, A., Language-theoretic problems arising from Richelieu cryptosystems. Theoret. Comput. Sci. 116 (1993) 339-357. CrossRef
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.
Dassow, J., Paun, G. and Salomaa, A., On thinness and slenderness of L languages. Bull. EATCS 49 (1993) 152-158.
Ginsburg, S. and Spanier, E.H., Bounded ALGOL-like languages. Trans. Amer. Math. Soc. 113 (1964) 333-368.
Honkala, J., Parikh, On slender languages and power series. J. Comput. System Sci. 52 (1996) 185-190. CrossRef
Honkala, J., Decision problems concerning thiness and slenderness of formal languages. Acta Inform. 35 (1998) 625-636. CrossRef
Ilie, L., On a conjecture about slender context-free languages. Theoret. Comput. Sci. 132 (1994) 427-434. CrossRef
L. Ilie, On lengths of words in context-free languages. Theoret. Comput. Sci. (to appear).
Kunze, M., Shyr, H.J. and Thierrin, G., h-bounded and semidiscrete languages. Inform. and Control 51 (1981) 147-187. CrossRef
Latteux, M. and Thierrin, G., Semidiscrete context-free languages. Internat. J. Comput. Math. 14 (1983) 3-18. CrossRef
Latteux, M. and Thierrin, G., On bounded context-free languages. Elektron. Informtionsverarb. Kybernet. 20 (1984) 3-8.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).
Nishida, T. and Salomaa, A., Slender 0L languages. Theoret. Comput. Sci. 158 (1996) 161-176. CrossRef
Gh. Paun, A. Salomaa, Thin and slender languages. Discrete Appl. Math. 61 (1995) 257-270. CrossRef
Raz, D., Length considerations in context-free languages. Theoret. Comput. Sci. 183 (1997) 21-32. CrossRef
A. Salomaa, Formal Languages. Academic Press, New York (1973).
Shallit, J., Numeration systems, linear recurrences, and regular sets. Inform. and Comput. 113 (1994) 331-347. CrossRef
Szilard, A., Yu, S., Zhang, K. and Shallit, J., 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. CrossRef