Nondeterminism is essential for reversal-bounded two-way multihead finite automata
Andrej Bebják; Ivana Štefáneková
Kybernetika (1988)
- Volume: 24, Issue: 1, page 65-71
- ISSN: 0023-5954
Access Full Article
topHow to cite
topBebják, Andrej, and Štefáneková, Ivana. "Nondeterminism is essential for reversal-bounded two-way multihead finite automata." Kybernetika 24.1 (1988): 65-71. <http://eudml.org/doc/27584>.
@article{Bebják1988,
author = {Bebják, Andrej, Štefáneková, Ivana},
journal = {Kybernetika},
keywords = {two-way finite automata; multihead automata; reversal complexity; nondeterminism},
language = {eng},
number = {1},
pages = {65-71},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Nondeterminism is essential for reversal-bounded two-way multihead finite automata},
url = {http://eudml.org/doc/27584},
volume = {24},
year = {1988},
}
TY - JOUR
AU - Bebják, Andrej
AU - Štefáneková, Ivana
TI - Nondeterminism is essential for reversal-bounded two-way multihead finite automata
JO - Kybernetika
PY - 1988
PB - Institute of Information Theory and Automation AS CR
VL - 24
IS - 1
SP - 65
EP - 71
LA - eng
KW - two-way finite automata; multihead automata; reversal complexity; nondeterminism
UR - http://eudml.org/doc/27584
ER -
References
top- P. C. Fischer, The reduction of tape reversals for off-line one-tape Turing machines, J. Comput. System Sci. 2 (1968), 136-147. (1968) Zbl0199.31001MR0245378
- J. Hartmanis, Tape reversal bounded Turing machines computations, J. Comput. System Sci. 19 (1979), 145-162. (1979) MR0243947
- J. Hromkovič, One-way multihead deterministic finite automata, Acta Inform. 19 (1983), 377-384. (1983) MR0717992
- J. Hromkovič, Fooling a two-way nondeterministic multihead automaton with reversal number restriction, Acta Inform. 22 (1985), 589-594. (1985) MR0822328
- T. Kameda, R. Vollmar, Note on tape-reversal complexity of languages, Inform. and Control 17 (1970), 203-215. (1970) Zbl0196.01801MR0272565
- T. F. Piatkowski, N-head Finite State Machines, Ph. D. Dissertation. University of Michigan 1963. (1963)
- I. H. Sudborough, One-way multihead writing finite automata, Inform. and Control 30 (1976), 1-20. (1976) Zbl0337.02023MR0400819
- A. C. Yao, R. L. Rivest, heads are better than , J. Assoc. Comput. Mach. 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.