Grammaires algébriques et monoïdes simplifiables

Christiane Frougny

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

  • Volume: 18, Issue: 3, page 225-239
  • ISSN: 0988-3754

How to cite

top

Frougny, Christiane. "Grammaires algébriques et monoïdes simplifiables." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 18.3 (1984): 225-239. <http://eudml.org/doc/92209>.

@article{Frougny1984,
author = {Frougny, Christiane},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {generators; relations; very-simple grammar; context-free grammar; free monoid; free group; Hotz monoid; syntactical monoid; Hotz group; Rees quotient},
language = {fre},
number = {3},
pages = {225-239},
publisher = {EDP-Sciences},
title = {Grammaires algébriques et monoïdes simplifiables},
url = {http://eudml.org/doc/92209},
volume = {18},
year = {1984},
}

TY - JOUR
AU - Frougny, Christiane
TI - Grammaires algébriques et monoïdes simplifiables
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1984
PB - EDP-Sciences
VL - 18
IS - 3
SP - 225
EP - 239
LA - fre
KW - generators; relations; very-simple grammar; context-free grammar; free monoid; free group; Hotz monoid; syntactical monoid; Hotz group; Rees quotient
UR - http://eudml.org/doc/92209
ER -

References

top
  1. 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. Zbl0204.01702MR218434
  2. 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. Zbl0322.68047MR422436
  3. 3. J. BEAUQUIER, Contribution à l'étude de la complexité structurelle des langages algébriques, Th. Sc. Math., Univ. Paris-VII, 1979. 
  4. 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. Zbl0455.68041MR588997
  5. 5. A. CLIFFORD et G. PRESTON, The Algebraic Theory of Semigroups, Amer. Math. Soc., vol. 1, 1961; vol. 2, 1967. Zbl0111.03403
  6. 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. 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. Zbl0495.68066MR688347
  8. 8. S. GINSBURG et M. HARRISON, Bracketed Context-Free Languages, Journal of Computer and System Sciences, vol. 1, 1967, p. 1-23. Zbl0153.00802MR235935
  9. 9. M. HARRISON, Introduction to Formal Language Theory, Addison Wesley, 1978. Zbl0411.68058MR526397
  10. 10. G. HOTZ, Eine neue Invariante für kontextfreie Sprachen, Theoret. Computer Sc., vol. 11, 1980, p. 107-116. Zbl0447.68089MR566697
  11. 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. Zbl0428.68085MR556956
  12. 12. R. C. LYNDON et P. E. SCHUPP, Combinatorial Group Theory, Springer, 1977. Zbl0368.20023MR577064
  13. 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. 14. J. F. PERROT, Monoïdes syntactiques des langages algébriques, Acta Informatica, vol. 7, 1977, p. 399-413. Zbl0326.68050MR439971
  15. 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. Zbl0148.25102MR234784
  16. 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. Zbl0395.68067MR664095

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.