Normal forms for phrase-structure grammars
Geffert, Viliam
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 473-496 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1991-01-01
@article{ITA_1991__25_5_473_0,
     author = {Geffert, Viliam},
     title = {Normal forms for phrase-structure grammars},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {473-496},
     mrnumber = {1144010},
     zbl = {0755.68092},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1991__25_5_473_0}
}

Geffert, Viliam. Normal forms for phrase-structure grammars. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) pp. 473-496. http://gdmltest.u-ga.fr/item/ITA_1991__25_5_473_0/

1. V. Geffert, A Representation of Recursively Enumerable Languages by two Homomorphisms and a Quotient, Theoret. Comput. Sci., 1988, 62, pp. 235-249. | MR 980932 | Zbl 0664.68075

2. V. Geffert, Grammars with Context Dependency Restricted to Synchronization, Proc. of M.FC.S' 86, L.N.C.S., 1986, 233, Springer-Verlag, pp. 370-378. | MR 874614 | Zbl 0611.68050

3. V. Geffert, Context-Free-Like Forms for the Phrase-Structure Grammars, Proc. of M.F.C.S.' 88, L.N.C.S., 1988, 324, Springer-Verlag, pp. 309-317. | MR 1023435 | Zbl 0652.68095

4. S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, Amsterdam, 1975. | MR 443446 | Zbl 0325.68002

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

6. M. A. Harrison and M. Scholnick, A Grammatical Characterization of One Way Nondeterministic Stack Languages, Ibid., 1971, 18, pp. 148-172. | MR 290902 | Zbl 0274.68020

7. J. E. Hopcroft and J. D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969. | MR 237243 | Zbl 0196.01701

8. M. Jantzen, M. Kudlek, K. L. Lange and H. Petersen, Dyck1-Reductions of Context-Free Languages, Comput. Artificial Intelligence, 1990, 9, No. 1, pp. 3-18. | MR 1047742 | Zbl 0695.68054

9. E. Post, A Variant of a Recursively Unsolvable Problem, Bull. Amer. Math, Soc., 1946, 52, pp. 264-268. | MR 15343 | Zbl 0063.06329

10. B. Rovan, A Framework for Studying Gramars, Proc. of M.F.C.S' 81, L.N.C.S., 1981, 118, Springer-Verlag, pp. 473-482. | MR 652779 | Zbl 0491.68076

11. B. Rovan, Complexity Classes of g-Systems are AFL, Univ. Comeniana, Acta Math. Univ. Comenian., XLVIII-XLIX, 1986, pp. 283-297. | MR 885343 | Zbl 0639.68064

12. E. S. Santos, A Note on Bracketed Grammars, J. Assoc. Comput. Mach., 1972, 9, pp. 222-224. | MR 449050 | Zbl 0238.68025

13. W. J. Savitch, How to Make Arbitrary Grammars Look Like Context-Free Grammars, S.I.A.M. J. Comput., 2, No. 3, 1973. | MR 356596 | Zbl 0298.68057