Context-free languages with rational index in Θ(n γ ) for algebraic numbers γ
Pierre, Laurent ; Farinone, Jean-Marc
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 275-322 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1990-01-01
@article{ITA_1990__24_3_275_0,
     author = {Pierre, Laurent and Farinone, Jean-Marc},
     title = {Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {24},
     year = {1990},
     pages = {275-322},
     mrnumber = {1072995},
     zbl = {0701.68068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1990__24_3_275_0}
}

Pierre, Laurent; Farinone, Jean-Marc. Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) pp. 275-322. http://gdmltest.u-ga.fr/item/ITA_1990__24_3_275_0/

1. J. Berstel, Transductions and Context-free languages, Teubner Verlag, 1979. | MR 549481 | Zbl 0424.68040

2. L. Boasson, Non-générateurs algébriques et substitution, RAIRO Informatique Théorique, Vol. 19, No. 2, 1985, pp. 125-136. | Numdam | MR 803994 | Zbl 0569.68060

3. L. Boasson and M. Nivat, Ordres et types de language, I, II, III, C. R. Acad. Sci. Paris, série A, Tome 284, 1977, pp. 559-562, 625-628, 703-705. | Zbl 0359.68096

4. L. Boasson, B. Courcelle and M. Nivat, The Rational Index, Complexity measure for Languages, S.I.A.M. J. Comput, Vol. 10, (2), 1981, pp. 284-296. | MR 615219 | Zbl 0469.68083

5. J. M. Farinone, Langages algébriques d'index rationnel singulier, Thèse de 3e cycle, Rapport L.I.T.P, No. 86-64, Univ. de Paris-VII, 1986.

6. J. Gabarro, Index rationnel, centre et langages algébriques, Thèse de 3e cycle, Rapport L.I.T.P., No. 81-54, Univ. de Paris-VI, 1981.

7. D. E. Knuth, Big Omicron and Big Omega and Big Theta, Sigact News, April-June 1976, pp. 18-24.

8. J. Lelong-Ferrand and J. M. Arnaudiès, Cours de mathématiques, Tome 2, Analyse, Dunod, Paris. | MR 476226 | Zbl 0259.26001

9. M. Nivat, Transductions des langages de Chomsky, Ann. de l'Inst. Fourier, Vol. 18, 1968, pp. 339-456. | Numdam | MR 238633 | Zbl 0313.68065

10. L. Pierre and J. M. Farinone, Rational Index of Context-free Languages in exp Θ (p√n) and nΘ (p√ln n), TCS, Vol. 57, 1988, pp. 185-204. | MR 960103 | Zbl 0646.68091