Single-tape reset machines

S. A. Greibach; C. Wrathall

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1986)

  • Volume: 20, Issue: 1, page 55-77
  • ISSN: 0988-3754

How to cite

top

Greibach, S. A., and Wrathall, C.. "Single-tape reset machines." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 20.1 (1986): 55-77. <http://eudml.org/doc/92246>.

@article{Greibach1986,
author = {Greibach, S. A., Wrathall, C.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {reset tape; circular tape; writing circular tape; Turing machine; nondeterministic on-line machines},
language = {eng},
number = {1},
pages = {55-77},
publisher = {EDP-Sciences},
title = {Single-tape reset machines},
url = {http://eudml.org/doc/92246},
volume = {20},
year = {1986},
}

TY - JOUR
AU - Greibach, S. A.
AU - Wrathall, C.
TI - Single-tape reset machines
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1986
PB - EDP-Sciences
VL - 20
IS - 1
SP - 55
EP - 77
LA - eng
KW - reset tape; circular tape; writing circular tape; Turing machine; nondeterministic on-line machines
UR - http://eudml.org/doc/92246
ER -

References

top
  1. 1. E. K. BLUM, A Note on Free Subsemigroups with Two Generators, Bull. Amer. Math. Soc., Vol. 71, 1965, pp. 678-679. Zbl0131.02004MR177046
  2. 2. L. BOASSON and M. NIVAT, Sur diverses familles de langages fermés par transduction rationnelle, Acta Inf., Vol. 2, 1973, pp. 180-188. Zbl0242.68037MR331873
  3. 3. R. BOOK, S. GREIBACH and C. WRATHALL, Reset Machines, J. Comput. Syst. Sc., Vol 19, 1979, pp. 256-276. Zbl0427.03029MR556604
  4. 4. S. GINSBURG and E. H. SPANIER, Bounded Regular Sets, Proc. Amer. Math. Soc., Vol. 17, 1966, pp. 1043-1049. Zbl0147.25301MR201310
  5. 5. S. GINSBURG and E. H. SPANIER, Bounded Algol-Like Languages, Trans. Amer. Math. Soc., Vol. 113, 1964, pp. 333-368. Zbl0142.24803MR181500
  6. 6. S. GINSBURG and S. GREIBACH, Principal AFL, J. Comput. Syst. Sc., Vol. 4, 1970, pp. 308-338. Zbl0198.03102MR286599
  7. 7. S. GREIBACH, Erasable Context-Free Languages, Inf. Control, Vol. 29, 1975, pp. 301-326. Zbl0317.68059MR386358
  8. 8. S. GREIBACH, Erasing in Context-Free AFLs, Inf. Control, Vol. 21, 1972, pp. 436-465. Zbl0248.68036MR331876
  9. 9. R. HULL, Reset Languages, Ph. D. dissertation, University of California at Berkeley, 1979. 
  10. 10. K. KLINGENSTEIN, Structures of Bounded Languages in Certain Families of Languages, Ph. D. dissertation, University of California at Berkeley, 1975. 
  11. 11. M. LATTEUX, Cônes rationnels commutativement clos, R.A.I..R.O.-Informatique théorique, Vol. 11, 1977, pp. 29-51. Zbl0354.68103MR478782
  12. 12. M. LOTHAIRE, ed., Combinatorics on Words, Addison-Wesley, Reading, Mass., 1982. Zbl0514.20045MR675953
  13. 13. R. SIROMONEY, On Equal Matrix Languages, Inf. Control, Vol. 14, 1969, pp. 135-151. Zbl0169.31402MR253838
  14. 14. S. GINSBURG and E. H. SPANIER, AFL with the Semilinear Property, J. Comput. Syst. Sc., Vol. 5, 1971, pp. 365-396. Zbl0235.68029MR339558
  15. 15. R. SIROMONEY, Finite-Turn Checking Automata, J. Comput. Syst. Sc., Vol. 5, 1971, pp. 549-559. Zbl0231.68032MR366565
  16. 16. O. IBARRA, Simple Matrix Languages, Inf. Control, Vol. 17, 1970, pp. 359-394. Zbl0221.68041MR274232
  17. 17. S. GINSBURG and S. GREIBACH, On AFL Generators for Finitely Encoded AFA, J. Comput. Syst. Sc., Vol. 7, 1973, pp. 1-27. Zbl0249.68025MR327088
  18. 18. F.-J. BRANDENBURG, Multiple Equality Sets and Post Machines, J. Comput. Syst. Sc., Vol. 21, 1980, pp. 292-316. Zbl0452.68086MR603586

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.