| Title:
|
Two new proof techniques for investigating the computational power of two-way computing devices [Abstract of thesis] (English) |
| Author:
|
Ďuriš, Pavol |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
30 |
| Issue:
|
1 |
| Year:
|
1989 |
| Pages:
|
197-198 |
| . |
| Category:
|
math |
| . |
| MSC:
|
03D15 |
| MSC:
|
03D60 |
| MSC:
|
68Q05 |
| idZBL:
|
Zbl 0682.68064 |
| . |
| Date available:
|
2008-06-05T21:37:46Z |
| Last updated:
|
2012-04-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/106728 |
| . |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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 0719444 |
| Reference:
|
[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. Zbl 0356.68064, MR 0438812 |
| Reference:
|
[5] Chan T.: Reversal complexity of counter machines.Proc. 13th ACM STOC, Milwauke (1981), 146-157. |
| Reference:
|
[6] Chrobak M.: Variations on the technique of Ďurš and Galil.J. Comput. and Syst. Sci. 30 (1985), 77-85. MR 0788832 |
| Reference:
|
[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 Zbl 0413.68085, MR 0563679 |
| Reference:
|
[8] Yao A. C., Rivest R. L.: $K+1$ heads are better than k.Journal of ACM 25 (1978), 337-340. Zbl 0372.68017, MR 0483728 |
| . |
