Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
Commentationes Mathematicae Universitatis Carolinae (1989)
- Volume: 030, Issue: 1, page 197-198
- ISSN: 0010-2628
Access Full Article
top
How to cite
topĎuriš, Pavol. "Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]." Commentationes Mathematicae Universitatis Carolinae 030.1 (1989): 197-198. <http://eudml.org/doc/17722>.
@article{Ďuriš1989,
author = {Ďuriš, Pavol},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {two-way deterministic pushdown automata; two-way deterministic counter automata; Turing machines with two read heads},
language = {eng},
number = {1},
pages = {197-198},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]},
url = {http://eudml.org/doc/17722},
volume = {030},
year = {1989},
}
TY - JOUR
AU - Ďuriš, Pavol
TI - Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1989
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 030
IS - 1
SP - 197
EP - 198
LA - eng
KW - two-way deterministic pushdown automata; two-way deterministic counter automata; Turing machines with two read heads
UR - http://eudml.org/doc/17722
ER -
References
top- Borodin A. B., Cook S. A., A time-space tradeoff for sorting on a general sequential model of computation, Proc. 12th ACM STOC, Los Angeles, Calif. (1980), 294-301. (1980)
- Borodin A. B., Fischer M. J., Kirkpatrick D. G., Lynch N. A., Tompa M., A time-space tradeoff for sorting on non-obliviona machines, Proc. 20th IEEE Symp. on FOCS, San Juan, Puerto Rico (1979), 319-327. (1979)
- Ďuriš P., Galil Z., On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store, Information and Control 54 (1982), 217-227. (1982) MR0719444
- Galil Z., Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Math. Systems Th. 10 (1977), 211-228. (1977) Zbl0356.68064MR0438812
- Chan T., Reversal complexity of counter machines, Proc. 13th ACM STOC, Milwauke (1981), 146-157. (1981)
- Chrobak M., Variations on the technique of Ďurš and Galil, J. Comput. and Syst. Sci. 30 (1985), 77-85. (1985) MR0788832
- Janiga L., Real-time computations of two-way multihead finite automata, in "L. Budach, Ed.: Fundamentals of computation theory FCT 79", Akademie Verlag, Berlin, 1979, 214-218 (1979) Zbl0413.68085MR0563679
- Yao A. C., Rivest R. L., heads are better than k, Journal of ACM 25 (1978), 337-340. (1978) Zbl0372.68017MR0483728
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.