A characterization of poly-slender context-free languages
Ilie, Lucian ; Rozenberg, Grzegorz ; Salomaa, Arto
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 77-86 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_2000__34_1_77_0,
     author = {Ilie, Lucian and Rozenberg, Grzegorz and Salomaa, Arto},
     title = {A characterization of poly-slender context-free languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {77-86},
     mrnumber = {1771131},
     zbl = {0966.68097},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_1_77_0}
}

Ilie, Lucian; Rozenberg, Grzegorz; Salomaa, Arto. A characterization of poly-slender context-free languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 77-86. http://gdmltest.u-ga.fr/item/ITA_2000__34_1_77_0/

[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. | MR 1231949 | Zbl 0797.68094

[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] J. Berstel, Sur la densité asymptotique de langages formels, edited by M. Nivat, Automata, Languages, and Programming. North-Holland (1972) 345-358. | MR 386351 | Zbl 0263.68043

[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. | MR 1469998

[5] J. Dassow, G. Păun and A. Salomaa, On thinness and slenderness of L languages. Bull. EATCS 49 (1993) 152-158. | Zbl 1023.68607

[6] S. Ginsburg and E. H. Spanier, Bounded ALGOL-like languages. Trans. Amer. Math. Soc. 113 (1964) 333-368. | MR 181500 | Zbl 0142.24803

[7] J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci. 52 (1996) 185-190. | MR 1375813 | Zbl 0846.68056

[8] J. Honkala, Decision problems concerning thiness and slenderness of formal languages. Acta Inform. 35 (1998) 625-636. | MR 1635803 | Zbl 0909.68112

[9] L. Ilie, On a conjecture about slender context-free languages. Theoret. Comput. Sci. 132 (1994) 427-434. | MR 1290555 | Zbl 0938.68707

[10] L. Ilie, On lengths of words in context-free languages. Theoret. Comput. Sci. (to appear). | MR 1769785 | Zbl 0944.68099

[11] M. Kunze, H. J. Shyr and G. Thierrin, h-bounded and semidiscrete languages. Inform. and Control 51 (1981) 147-187. | MR 686837 | Zbl 0507.68053

[12] M. Latteux and G. Thierrin, Semidiscrete context-free languages. Internat. J. Comput. Math. 14 (1983) 3-18. | MR 717638 | Zbl 0514.68072

[13] M. Latteux and G. Thierrin, On bounded context-free languages. Elektron. Informtionsverarb. Kybemet. 20 (1984) 3-8. | MR 765001 | Zbl 0552.68062

[14] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). | MR 675953 | Zbl 0514.20045

[15] T. Nishida and A. Salomaa, Slender 0L languages. Theoret. Comput. Sci. 158 (1996) 161-176. | MR 1388968 | Zbl 0871.68115

[16] Gh. Păun and A. Salomaa, Thin and slender languages. Discrete Appl. Math. 61 (1995) 257-270. | MR 1345007 | Zbl 0831.68057

[17] D. Raz, Length considerations in context-free languages. Theoret. Comput. Sci. 183 (1997) 21-32. | MR 1468448 | Zbl 0911.68097

[18] A. Salomaa, Formal Languages. Academic Press, New York (1973). | MR 438755 | Zbl 0262.68025

[19] J. Shallit, Numeration Systems, linear recurrences, and regular sets. Inform. and Comput. 113 (1994) 331-347. | MR 1285236 | Zbl 0810.11006

[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. | MR 1255157