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

How to cite

top

Bebjá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
  1. 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
  2. J. Hartmanis, Tape reversal bounded Turing machines computations, J. Comput. System Sci. 19 (1979), 145-162. (1979) MR0243947
  3. J. Hromkovič, One-way multihead deterministic finite automata, Acta Inform. 19 (1983), 377-384. (1983) MR0717992
  4. J. Hromkovič, Fooling a two-way nondeterministic multihead automaton with reversal number restriction, Acta Inform. 22 (1985), 589-594. (1985) MR0822328
  5. T. Kameda, R. Vollmar, Note on tape-reversal complexity of languages, Inform. and Control 17 (1970), 203-215. (1970) Zbl0196.01801MR0272565
  6. T. F. Piatkowski, N-head Finite State Machines, Ph. D. Dissertation. University of Michigan 1963. (1963) 
  7. I. H. Sudborough, One-way multihead writing finite automata, Inform. and Control 30 (1976), 1-20. (1976) Zbl0337.02023MR0400819
  8. A. C. Yao, R. L. Rivest, K + 1 heads are better than K , J. Assoc. Comput. Mach. 25 (1978), 337-340. (1978) Zbl0372.68017MR0483728

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.