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
Access Full Article
top
How to cite
topSalomaa, 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>.
@article{Salomaa1994,
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},
}
TY - JOUR
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 -
References
top- 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. Zbl0416.68044MR495212
- 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. 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. Zbl0411.68058MR526397
- 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. Zbl0925.03175MR1136100
- 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. K. SALOMAA and S. YU, Measures of nondeterminism forpushdown automata, Journal of Computer and System Sciences, to appear. Zbl0822.68070MR1466197
- 10. D. VERMEIR and W. SAVITCH, On the amount of nondeterminism in pushdown automata, Fundamenta Informaticae, 1981, 4, pp. 401-418. Zbl0528.68034MR645247
- 11. D. WOOD, Theory of Computation, John Wiley & Sons, Inc., New York, NY, second edition, 1993, In preparation. Zbl0734.68001
NotesEmbed ?
topYou 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.