Grammaires algébriques et monoïdes simplifiables
Frougny, Christiane
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 18 (1984), p. 225-239 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1984-01-01
@article{ITA_1984__18_3_225_0,
     author = {Frougny, Christiane},
     title = {Grammaires alg\'ebriques et mono\"\i des simplifiables},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {18},
     year = {1984},
     pages = {225-239},
     mrnumber = {763668},
     zbl = {0545.68071},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1984__18_3_225_0}
}

Frougny, Christiane. Grammaires algébriques et monoïdes simplifiables. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 18 (1984) pp. 225-239. http://gdmltest.u-ga.fr/item/ITA_1984__18_3_225_0/

1. S. I. Adjan, Defining Relations and Algorithmic Problems for Groups and Semigroups, Proc. Steklov Inst., vol. 85, 1966, Amer. Math. Soc. Transl., vol. 152, 1967. | MR 218434 | Zbl 0204.01702

2. A. V. Anisimov et F. D. Seifert, Zur algebraischen Charakteristik der durch kontextfreie Sprachen definierten Gruppen, Elektronische Informations-verarbeitung und Kybernetik, vol. 11, 1975, p. 695-702. | MR 422436 | Zbl 0322.68047

3. J. Beauquier, Contribution à l'étude de la complexité structurelle des langages algébriques, Th. Sc. Math., Univ. Paris-VII, 1979.

4. L. Boasson, Dérivations et réductions dans les grammaires algébriques, Proc. of the 7th I.C.A.L.P., Lecture Notes in Computer Science, vol. 85, 1980, p. 109-118. | MR 588997 | Zbl 0455.68041

5. A. Clifford et G. Preston, The Algebraic Theory of Semigroups, Amer. Math. Soc., vol. 1, 1961; vol. 2, 1967. | Zbl 0111.03403

6. Ch. Frougny, Une famille de langages algébriques congruentiels : les langages à non-terminaux séparés, Thèse 3e cycle, Univ. Paris-VII, 1980.

7. Ch. Frougny, J. Sakarovitch et E. Valkema, On the Hotz Group of a Context-Free Grammar, Acta Informatica, vol.18, 1982, p. 109-115. | MR 688347 | Zbl 0495.68066

8. S. Ginsburg et M. Harrison, Bracketed Context-Free Languages, Journal of Computer and System Sciences, vol. 1, 1967, p. 1-23. | MR 235935 | Zbl 0153.00802

9. M. Harrison, Introduction to Formal Language Theory, Addison Wesley, 1978. | MR 526397 | Zbl 0411.68058

10. G. Hotz, Eine neue Invariante für kontextfreie Sprachen, Theoret. Computer Sc., vol. 11, 1980, p. 107-116. | MR 566697 | Zbl 0447.68089

11. G. Hotz, Über die Darstellbarkeit des syntaktischen Monoides Kontextfreier Sprachen, R.A.I.R.O. Informatique Théorique, vol. 13, 1979, p. 337-345. | Numdam | MR 556956 | Zbl 0428.68085

12. R. C. Lyndon et P. E. Schupp, Combinatorial Group Theory, Springer, 1977. | MR 577064 | Zbl 0368.20023

13. D. E. Muller et P. E. Schupp, Pushdown Automata, Graphs, Ends, Second-Order logic, and reachability Problems, Proc. of the 13th Symposium on Theory of Computing, 1981, p. 46-54.

14. J. F. Perrot, Monoïdes syntactiques des langages algébriques, Acta Informatica, vol. 7, 1977, p. 399-413. | MR 439971 | Zbl 0326.68050

15. D. J. Rosenkrantz, Matrix Equations and Normal Forms for Context-Free Grammars, Journal of the Association for Computing Machinery, vol. 14, 1967, p. 501-507. | MR 234784 | Zbl 0148.25102

16. J. Sakarovitch, Sur les groupes infinis, considérés comme monoïdes syntaxiques de langages formels, Séminaire Dubreil 1975-1976, Lecture Notes 586, 1977, p. 168-179. | MR 664095 | Zbl 0395.68067