Hierarchy of reversal bounded one-way multicounter machines

Juraj Hromkovič

Kybernetika (1986)

  • Volume: 22, Issue: 2, page 200-206
  • ISSN: 0023-5954

How to cite

top

Hromkovič, Juraj. "Hierarchy of reversal bounded one-way multicounter machines." Kybernetika 22.2 (1986): 200-206. <http://eudml.org/doc/28171>.

@article{Hromkovič1986,
author = {Hromkovič, Juraj},
journal = {Kybernetika},
keywords = {multipushdown machine; reversal bounded hierarchy; one-way multicounter machine},
language = {eng},
number = {2},
pages = {200-206},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Hierarchy of reversal bounded one-way multicounter machines},
url = {http://eudml.org/doc/28171},
volume = {22},
year = {1986},
}

TY - JOUR
AU - Hromkovič, Juraj
TI - Hierarchy of reversal bounded one-way multicounter machines
JO - Kybernetika
PY - 1986
PB - Institute of Information Theory and Automation AS CR
VL - 22
IS - 2
SP - 200
EP - 206
LA - eng
KW - multipushdown machine; reversal bounded hierarchy; one-way multicounter machine
UR - http://eudml.org/doc/28171
ER -

References

top
  1. T. Chan, Reversal complexity of counter machines, In: Proc. IEEE Symposium on Theory of Computing 1981, IEEE, New York, 146-157. (1981) 
  2. P. Ďuriš, J. Hromkovič, One-way simple multihead finite automata are not closed under concatenation, Theoret. Comput. Sci. 27 (1983), 121 - 225. (1983) MR0742281
  3. P. Ďuriš, Z. Galil, On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store, Inform, artd Control 54 (1982), 3, 217-227. (1982) MR0719444
  4. S. Ginsburg, Algebraic and Automata - Theoretic Properties of Formal Languages, North-Holland Publ. Comp., Amsterdam 1975. (1975) Zbl0325.68002MR0443446
  5. S. A. Greibach, Remarks on blind and partially blind one-way multicounter machines, Theoret. Comput. Sci. 7 (1978), 311-324. (1978) Zbl0389.68030MR0513714
  6. M. Hack, Petri Net Languages, Computation Structures, Group Memo 124, Project MAC, MIT, 1975. (1975) 
  7. J. Hromkovič, Closure properties of the family of languages recognized by one-way two-head deterministic finite state automata, In: Mathematical Foundations of Computer Science 1981 - Proc. 10th Symposium, Štrbské pleso, Czechoslovakia, August 31 - September 4, 1981 (J. Gruska, M. Chytil, eds.). (Lecture Notes in Computer Science 118.) Springer-Verlag, Berlin-Heidelberg-New York 1981, 304-313. (1981) MR0652763
  8. J. Hromkovič, Hierarchy of reversal and zerotesting bounded multicounter machines, In: Mathematical Foundations of Computer Science 1984 - Proc. 11th Symposium, Prague, Czechoslovakia, September 3 - 7, 1984 (M. P. Chytil, V. Koubek, eds.). (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, 312-321. (1984) MR0783460
  9. J. Hromkovič, Reversal bounded multicounter machines, Computers and Artificial Intelligence 4 (1985), 4, 361-366. (1985) 
  10. O. H. Ibarra, Reversal-bounded multicounter machines and their decision problems, J. Assoc. Comput. Mach. 25 (1978), 116-133. (1978) Zbl0365.68059MR0461988

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.