Geodesic
Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 1, pp. 197-198 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 03D15, 03D60, 68Q05 
@article{CMUC_1989_30_1_a30,
     author = {\v{D}uri\v{s}, Pavol},
     title = {Two new proof techniques for investigating the computational power of two-way computing devices {[Abstract} of thesis]},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {197--198},
     year = {1989},
     volume = {30},
     number = {1},
     zbl = {0682.68064},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a30/}
}
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
SP  - 197
EP  - 198
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a30/
LA  - en
ID  - CMUC_1989_30_1_a30
ER  - 
%0 Journal Article
%A Ďuriš, Pavol
%T Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]
%J Commentationes Mathematicae Universitatis Carolinae
%D 1989
%P 197-198
%V 30
%N 1
%U http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a30/
%G en
%F CMUC_1989_30_1_a30
Ďuriš, Pavol. Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis]. Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 1, pp. 197-198. http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a30/

[1] 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.

[2] 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.

[3] Ď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. | MR

[4] 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. | MR | Zbl

[5] Chan T.: Reversal complexity of counter machines. Proc. 13th ACM STOC, Milwauke (1981), 146-157.

[6] Chrobak M.: Variations on the technique of Ďurš and Galil. J. Comput. and Syst. Sci. 30 (1985), 77-85. | MR

[7] 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 | MR | Zbl

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