Context-free languages with rational index in for algebraic numbers
Laurent Pierre; Jean-Marc Farinone
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1990)
- Volume: 24, Issue: 3, page 275-322
- ISSN: 0988-3754
Access Full Article
top
How to cite
topPierre, Laurent, and 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 24.3 (1990): 275-322. <http://eudml.org/doc/92360>.
@article{Pierre1990,
author = {Pierre, Laurent, Farinone, Jean-Marc},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {complexity of languages},
language = {eng},
number = {3},
pages = {275-322},
publisher = {EDP-Sciences},
title = {Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $},
url = {http://eudml.org/doc/92360},
volume = {24},
year = {1990},
}
TY - JOUR
AU - Pierre, Laurent
AU - Farinone, Jean-Marc
TI - Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1990
PB - EDP-Sciences
VL - 24
IS - 3
SP - 275
EP - 322
LA - eng
KW - complexity of languages
UR - http://eudml.org/doc/92360
ER -
References
top- 1. J. BERSTEL, Transductions and Context-free languages, Teubner Verlag, 1979. Zbl0424.68040MR549481
- 2. L. BOASSON, Non-générateurs algébriques et substitution, RAIRO Informatique Théorique, Vol. 19, No. 2, 1985, pp. 125-136. Zbl0569.68060MR803994
- 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. Zbl0359.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. Zbl0469.68083MR615219
- 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. Zbl0505.68033
- 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. Zbl0259.26001MR476226
- 9. M. NIVAT, Transductions des langages de Chomsky, Ann. de l'Inst. Fourier, Vol. 18, 1968, pp. 339-456. Zbl0313.68065MR238633
- 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. Zbl0646.68091MR960103
NotesEmbed ?
topYou 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.