Pumping and pushdown machines
Salomaa, Kai ; Wood, D. ; Yu, Sheng
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 221-232 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_3-4_221_0,
     author = {Salomaa, Kai and Wood, D. and Yu, Sheng},
     title = {Pumping and pushdown machines},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {221-232},
     mrnumber = {1282445},
     zbl = {0883.68093},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_3-4_221_0}
}

Salomaa, Kai; Wood, D.; Yu, Sheng. Pumping and pushdown machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 221-232. http://gdmltest.u-ga.fr/item/ITA_1994__28_3-4_221_0/

1. R. W. Floyd and R. Beigel, The Language of Machines: An Introduction to Computability and Formal Language Theory, Francisco, CA, 1994.

2. J. Goldstdsfe, Automata with data storage, In Proceedings of the Conference on Theoretical Computer Science, Waterloo, Canada, 1977, , University of Waterloo, pp. 239-246. | MR 495212 | Zbl 0416.68044

3. J. Goldstine, A rational theory of AFLs, In Proceedings of the Sixth Colloquium on Automata, Languages, and Programming, Volume 71 of Lecture Notes in Computer Science, NewYork, NY, 1979, Springer-Verlag, pp. 271-281. | MR 573244 | Zbl 0415.68041

4. J. Goldstine, Formal languages and their relation to automata: What Hopcroft & Ullman didn't tell us, In R.V. Book, Editor, Formal Language Theory: Perspectives and Open Problems, NewYork, NY, 1980, Academic Press, pp. 109-140.

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

6. R. Kurki-Suonio, Describing automata in terms of languages associated with their peripheral devices, Technical Report STAN-CS-75-493, Computer Science Department, Stanford University, Stanford, CA, 1975.

7. K. Salomaa and S. Yu, Degrees of nondeterminism for pushdown automata, In Proceedings of the 8th Fundamentals of Computation Theory Conference, Volume 529 of Lecture Notes in Computer Science, New York, NY, 1991. .Springer-Verlag, pp. 380-389. | MR 1136100 | Zbl 0925.03175

8. K. Salomaa and S. Yu, Limited nondeterminism for pushdown automata, Bulletin of the European Association for Theoretical Computer Science, 1993, 50, pp. 186-193. | Zbl 1023.68621

9. K. Salomaa and S. Yu, Measures of nondeterminism forpushdown automata, Journal of Computer and System Sciences, to appear. | MR 1466197 | Zbl 0822.68070

10. D. Vermeir and W. Savitch, On the amount of nondeterminism in pushdown automata, Fundamenta Informaticae, 1981, 4, pp. 401-418. | MR 645247 | Zbl 0528.68034

11. D. Wood, Theory of Computation, John Wiley & Sons, Inc., New York, NY, second edition, 1993, In preparation. | Zbl 0734.68001