Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
Ďuriš, Pavol
Commentationes Mathematicae Universitatis Carolinae, Tome 030 (1989), p. 197-198 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1989-01-01
Classification:  03D15,  03D60,  68Q05 
@article{106728,
     author = {Pavol \v Duri\v s},
     title = {Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {030},
     year = {1989},
     pages = {197-198},
     zbl = {0682.68064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/106728}
}

Ďuriš, Pavol. Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]. Commentationes Mathematicae Universitatis Carolinae, Tome 030 (1989) pp. 197-198. http://gdmltest.u-ga.fr/item/106728/

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) | MR 0719444

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) | MR 0438812 | Zbl 0356.68064

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) | MR 0788832

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) | MR 0563679 | Zbl 0413.68085

Yao A. C.; Rivest R. L. $K+1$ heads are better than k, Journal of ACM 25 (1978), 337-340. (1978) | MR 0483728 | Zbl 0372.68017