Pumping and pushdown machines

Kai Salomaa; D. Wood; Sheng Yu

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

  • Volume: 28, Issue: 3-4, page 221-232
  • ISSN: 0988-3754

How to cite


Salomaa, Kai, Wood, D., and Yu, Sheng. "Pumping and pushdown machines." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.3-4 (1994): 221-232. <http://eudml.org/doc/92477>.

author = {Salomaa, Kai, Wood, D., Yu, Sheng},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {context-free pumping lemmas; pushdown machines},
language = {eng},
number = {3-4},
pages = {221-232},
publisher = {EDP-Sciences},
title = {Pumping and pushdown machines},
url = {http://eudml.org/doc/92477},
volume = {28},
year = {1994},

AU - Salomaa, Kai
AU - Wood, D.
AU - Yu, Sheng
TI - Pumping and pushdown machines
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 3-4
SP - 221
EP - 232
LA - eng
KW - context-free pumping lemmas; pushdown machines
UR - http://eudml.org/doc/92477
ER -


  1. 1. R. W. FLOYD and R. BEIGEL, The Language of Machines: An Introduction to Computability and Formal Language Theory, Francisco, CA, 1994. 
  2. 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. Zbl0416.68044MR495212
  3. 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. Zbl0415.68041MR573244
  4. 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. 5. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, MA, 1978. Zbl0411.68058MR526397
  6. 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. 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. Zbl0925.03175MR1136100
  8. 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. Zbl1023.68621
  9. 9. K. SALOMAA and S. YU, Measures of nondeterminism forpushdown automata, Journal of Computer and System Sciences, to appear. Zbl0822.68070MR1466197
  10. 10. D. VERMEIR and W. SAVITCH, On the amount of nondeterminism in pushdown automata, Fundamenta Informaticae, 1981, 4, pp. 401-418. Zbl0528.68034MR645247
  11. 11. D. WOOD, Theory of Computation, John Wiley & Sons, Inc., New York, NY, second edition, 1993, In preparation. Zbl0734.68001

NotesEmbed ?


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.