# 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) Zbl0478.68061
- 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) Zbl0462.68011
- Ď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) Zbl0485.68079MR0719444
- 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) Zbl0576.68061MR0788832
- 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., $K+1$ heads are better than k, Journal of ACM 25 (1978), 337-340. (1978) Zbl0372.68017MR0483728

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.