A characterization of poly-slender context-free languages

Lucian Ilie; Grzegorz Rozenberg; Arto Salomaa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

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

How to cite

top

Ilie, Lucian, Rozenberg, Grzegorz, and Salomaa, Arto. "A characterization of poly-slender context-free languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 34.1 (2000): 77-86. <http://eudml.org/doc/92625>.

@article{Ilie2000,
author = {Ilie, Lucian, Rozenberg, Grzegorz, Salomaa, Arto},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {context-free language; poly-slender language; Dyck loop},
language = {eng},
number = {1},
pages = {77-86},
publisher = {EDP-Sciences},
title = {A characterization of poly-slender context-free languages},
url = {http://eudml.org/doc/92625},
volume = {34},
year = {2000},
}

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 - Informatique Théorique et Applications
PY - 2000
PB - EDP-Sciences
VL - 34
IS - 1
SP - 77
EP - 86
LA - eng
KW - context-free language; poly-slender language; Dyck loop
UR - http://eudml.org/doc/92625
ER -

References

top
  1. [1] M. Andraşiu, J. Dassow, Gh. Păun and A. Salomaa, Language-theoretic problems arising from Richelieu cryptosystems. Theoret. Comput. Sci. 116 (1993) 339-357. Zbl0797.68094MR1231949
  2. [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 Formail Languages. Springer-Verlag, Berlin, Heidelberg (1997) 111-174. 
  3. [3] J. Berstel, Sur la densité asymptotique de langages formels, edited by M. Nivat, Automata, Languages, and Programming. North-Holland (1972) 345-358. Zbl0263.68043MR386351
  4. [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. MR1469998
  5. [5] J. Dassow, G. Păun and A. Salomaa, On thinness and slenderness of L languages. Bull. EATCS 49 (1993) 152-158. Zbl1023.68607
  6. [6] S. Ginsburg and E. H. Spanier, Bounded ALGOL-like languages. Trans. Amer. Math. Soc. 113 (1964) 333-368. Zbl0142.24803MR181500
  7. [7] J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci. 52 (1996) 185-190. Zbl0846.68056MR1375813
  8. [8] J. Honkala, Decision problems concerning thiness and slenderness of formal languages. Acta Inform. 35 (1998) 625-636. Zbl0909.68112MR1635803
  9. [9] L. Ilie, On a conjecture about slender context-free languages. Theoret. Comput. Sci. 132 (1994) 427-434. Zbl0938.68707MR1290555
  10. [10] L. Ilie, On lengths of words in context-free languages. Theoret. Comput. Sci. (to appear). Zbl0944.68099MR1769785
  11. [11] M. Kunze, H. J. Shyr and G. Thierrin, h-bounded and semidiscrete languages. Inform. and Control 51 (1981) 147-187. Zbl0507.68053MR686837
  12. [12] M. Latteux and G. Thierrin, Semidiscrete context-free languages. Internat. J. Comput. Math. 14 (1983) 3-18. Zbl0514.68072MR717638
  13. [13] M. Latteux and G. Thierrin, On bounded context-free languages. Elektron. Informtionsverarb. Kybemet. 20 (1984) 3-8. Zbl0552.68062MR765001
  14. [14] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). Zbl0514.20045MR675953
  15. [15] T. Nishida and A. Salomaa, Slender 0L languages. Theoret. Comput. Sci. 158 (1996) 161-176. Zbl0871.68115MR1388968
  16. [16] Gh. Păun and A. Salomaa, Thin and slender languages. Discrete Appl. Math. 61 (1995) 257-270. Zbl0831.68057MR1345007
  17. [17] D. Raz, Length considerations in context-free languages. Theoret. Comput. Sci. 183 (1997) 21-32. Zbl0911.68097MR1468448
  18. [18] A. Salomaa, Formal Languages. Academic Press, New York (1973). Zbl0262.68025MR438755
  19. [19] J. Shallit, Numeration Systems, linear recurrences, and regular sets. Inform. and Comput. 113 (1994) 331-347. Zbl0810.11006MR1285236
  20. [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. MR1255157

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.