Ogden's lemma for nonterminal bounded languages
Boonyavatana, R. ; Slutzki, G.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986), p. 457-471 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1986-01-01
@article{ITA_1986__20_4_457_0,
     author = {Boonyavatana, R. and Slutzki, G.},
     title = {Ogden's lemma for nonterminal bounded languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {20},
     year = {1986},
     pages = {457-471},
     mrnumber = {880847},
     zbl = {0631.68065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1986__20_4_457_0}
}

Boonyavatana, R.; Slutzki, G. Ogden's lemma for nonterminal bounded languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986) pp. 457-471. http://gdmltest.u-ga.fr/item/ITA_1986__20_4_457_0/

1. A. V. Aho, and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vol. 1, Prentice-Hall, 1972. | MR 408321

2. J. Berstel, Transductions and Context-Free Languages, Teubner, Stuttgart 1979. | MR 549481 | Zbl 0424.68040

3. L. Boasson and S. Horváth, On languages satisfying Ogder's lemma, RAIRO Informatique Théorique, Vol. 12 (3), 1978, pp. 201-202. | Numdam | MR 510637 | Zbl 0387.68054

4. R. Boonyavatana and G. Slutzki, A pumping lemma for Nonterminal Bounded Languages, manuscript, 1984.

5. S. A. Greibach, Linearity is Polynomially Decidable for Realtime Pushdown Store Automata, Inform. Contr., Vol. 42, 1979, p. 27-37. | MR 538377 | Zbl 0413.68086

6. S. A. Greibach, The Unsolvability of the Recognition of Linear Context-Free Languages, JACM, Vol. 13, (4), 1966, pp. 582-587. | MR 205770 | Zbl 0148.00901

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

8. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory Languages and Computation, Addison-Wesley, Reading, Mass, 1979. | MR 645539 | Zbl 0426.68001

9. W. Ogden, A Helpful Result for Proving Inherent Ambiguity. Math. Syst Theory, Vol. 2 (3), pp. 191-194. | MR 233645 | Zbl 0175.27802