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

Abstract

top
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 𝒪 ( 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.

How to cite

top

Ilie, 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
  1. M. Andrasiu, J. Dassow, Gh. Paun and A. Salomaa, Language-theoretic problems arising from Richelieu cryptosystems. Theoret. Comput. Sci.116 (1993) 339-357.  
  2. 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.  
  3. J. Berstel, Sur la densité asymptotique de langages formels, edited by M. Nivat, Automata, Languages, and Programming. North-Holland (1972) 345-358.  
  4. 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.  
  5. J. Dassow, G. Paun and A. Salomaa, On thinness and slenderness of L languages. Bull. EATCS49 (1993) 152-158.  
  6. S. Ginsburg and E.H. Spanier, Bounded ALGOL-like languages. Trans. Amer. Math. Soc.113 (1964) 333-368.  
  7. J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci.52 (1996) 185-190.  
  8. J. Honkala, Decision problems concerning thiness and slenderness of formal languages. Acta Inform.35 (1998) 625-636.  
  9. L. Ilie, On a conjecture about slender context-free languages. Theoret. Comput. Sci.132 (1994) 427-434.  
  10. L. Ilie, On lengths of words in context-free languages. Theoret. Comput. Sci. (to appear).  
  11. M. Kunze, H.J. Shyr and G. Thierrin, h-bounded and semidiscrete languages. Inform. and Control51 (1981) 147-187.  
  12. M. Latteux and G. Thierrin, Semidiscrete context-free languages. Internat. J. Comput. Math.14 (1983) 3-18.  
  13. M. Latteux and G. Thierrin, On bounded context-free languages. Elektron. Informtionsverarb. Kybernet.20 (1984) 3-8.  
  14. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).  
  15. T. Nishida and A. Salomaa, Slender 0L languages. Theoret. Comput. Sci.158 (1996) 161-176.  
  16. Gh. Paun and A. Salomaa, Thin and slender languages. Discrete Appl. Math.61 (1995) 257-270.  
  17. D. Raz, Length considerations in context-free languages. Theoret. Comput. Sci.183 (1997) 21-32.  
  18. A. Salomaa, Formal Languages. Academic Press, New York (1973).  
  19. J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. and Comput.113 (1994) 331-347.  
  20. 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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.