| Title:
|
Nondeterminism is essential for reversal-bounded two-way multihead finite automata (English) |
| Author:
|
Bebják, Andrej |
| Author:
|
Štefáneková, Ivana |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
24 |
| Issue:
|
1 |
| Year:
|
1988 |
| Pages:
|
65-71 |
| . |
| Category:
|
math |
| . |
| MSC:
|
03D10 |
| MSC:
|
03D15 |
| MSC:
|
68Q05 |
| MSC:
|
68Q15 |
| MSC:
|
68Q25 |
| idZBL:
|
Zbl 0648.68063 |
| idMR:
|
MR936556 |
| . |
| Date available:
|
2009-09-24T18:04:30Z |
| Last updated:
|
2012-06-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124429 |
| . |
| Reference:
|
[1] P. C. Fischer: The reduction of tape reversals for off-line one-tape Turing machines.J. Comput. System Sci. 2 (1968), 136-147. Zbl 0199.31001, MR 0245378 |
| Reference:
|
[2] J. Hartmanis: Tape reversal bounded Turing machines computations.J. Comput. System Sci. 19 (1979), 145-162. MR 0243947 |
| Reference:
|
[3] J. Hromkovič: One-way multihead deterministic finite automata.Acta Inform. 19 (1983), 377-384. MR 0717992 |
| Reference:
|
[4] J. Hromkovič: Fooling a two-way nondeterministic multihead automaton with reversal number restriction.Acta Inform. 22 (1985), 589-594. MR 0822328 |
| Reference:
|
[5] T. Kameda, R. Vollmar: Note on tape-reversal complexity of languages.Inform. and Control 17 (1970), 203-215. Zbl 0196.01801, MR 0272565 |
| Reference:
|
[6] T. F. Piatkowski: N-head Finite State Machines.Ph. D. Dissertation. University of Michigan 1963. |
| Reference:
|
[7] I. H. Sudborough: One-way multihead writing finite automata.Inform. and Control 30 (1976), 1-20. Zbl 0337.02023, MR 0400819 |
| Reference:
|
[8] A. C. Yao, R. L. Rivest: $K + 1$ heads are better than $K$.J. Assoc. Comput. Mach. 25 (1978), 337-340. Zbl 0372.68017, MR 0483728 |
| . |
