Space classes, intersection of languages and bounded erasing homomorphisms

Andreas Brandstädt

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

  • Volume: 17, Issue: 2, page 121-130
  • ISSN: 0988-3754

How to cite

top

Brandstädt, Andreas. "Space classes, intersection of languages and bounded erasing homomorphisms." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 17.2 (1983): 121-130. <http://eudml.org/doc/92180>.

@article{Brandstädt1983,
author = {Brandstädt, Andreas},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {space complexity classes; one-counter languages; context-free languages; checking stack languages; erasing bounded transducers},
language = {eng},
number = {2},
pages = {121-130},
publisher = {EDP-Sciences},
title = {Space classes, intersection of languages and bounded erasing homomorphisms},
url = {http://eudml.org/doc/92180},
volume = {17},
year = {1983},
}

TY - JOUR
AU - Brandstädt, Andreas
TI - Space classes, intersection of languages and bounded erasing homomorphisms
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1983
PB - EDP-Sciences
VL - 17
IS - 2
SP - 121
EP - 130
LA - eng
KW - space complexity classes; one-counter languages; context-free languages; checking stack languages; erasing bounded transducers
UR - http://eudml.org/doc/92180
ER -

References

top
  1. 1. A. V. AHO and J. D. ULLMAN, The Theory of Parsing, Translation and Compiling, Vol. 1, Prentice-Hall, Englewood Cliffs N.J., 1972. Zbl0264.68032MR408321
  2. 2. B. S. BAKER and R. V. BOOK, Reversal-Bounded Multipushdown Machines, J. Comp. System Sc., Vol. 8, 1974, pp. 315-332. Zbl0309.68043MR375844
  3. 3. R. V. BOOK, Translational Lemmas, Polynomial Time and (log n) j-Space, Theor. Comp. Sc., 1976, pp. 215-226. Zbl0326.68030MR405918
  4. 4. R. V. BOOK, Complexity Classes of Formal Languages, MFCS, 1979, pp. 43-56, Lecture Notes in Comp. Sc., No. 74. Zbl0413.68045MR570974
  5. 5. R. V. BOOK and F.-J. BRANDENBURG, Equality Sets and Complexity Classes, S.I.A.M. J. Computing, Vol. 9, No. 4, 1980, pp. 729-743. Zbl0446.68040MR592764
  6. 6. R. V. BOOK and S. A. GREIBACH, Quasi-Realtime Languages, Math. Syst. Theory, Vol. 4, No. 2, 1970, pp. 97-111. Zbl0188.33102MR276019
  7. 7. R. V. BOOK, S. A. GREIBACH and B. WEGBREIT, Time- and Tape-Bouded Turing Acceptors and AFLs, J. Comp. System Sc., Vol. 4, No. 6, 1970, pp. 606-621. Zbl0206.28702MR267993
  8. 8. R. V. BOOK, M. NIVAT and M. PATERSON, Reversal-Bounded Acceptors and Intersections of Linear Languages, S.I.A.M. J. Computing, Vol. 3, No. 4, 1974, pp. 283-295. Zbl0292.68023MR433992
  9. 9. K. CULIK II, Homomorphisms; Decidability, Equality and Test Sets; Formal Language Theory, Perspectives and Open Problems, R. V. Book, Ed., Academic Press, 1980. 
  10. 10. K. CULIK II and N. O. DIAMOND, A Homomorphic Characterization of Time and Space Complexity Classes of Languages, Internat. J. Computer Math. (to appear). Zbl0444.68035MR585410
  11. 11. P. C. FISCHER, A. R. MEYER and A. L. ROSENBERG, Counter Machines and Counter Languages, Math. Syst. Theory, Vol. 2, No. 3, 1968, pp. 265-283. Zbl0165.32002MR235932
  12. 12. S. GINSBURG, Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, 1975. Zbl0325.68002MR443446
  13. 13. S. A GREIBACH, Remarks on the Complexity of Nondeterministic Counter Languages, Theor. Comp. Sc., Vol. 1, 1976, pp. 269-288. Zbl0332.68039MR411257
  14. 14. J. HARTMANIS, Context-Free Languages and Turing Machine Computations, Proc. Symp. Applied Math., Vol. 19, 1967, pp. 42-51. Zbl0189.29101MR235938
  15. 15. O. M. IBARRA, Characterizations of Transductions Deflned by Abstract Families of Transducers Math. Syst. Theory, Vol. 5, 1971, pp. 271-281. Zbl0221.94077MR305949
  16. 16. O. M. IBARRA, Characterization of Some Tape and Time Complexity Classes of Turing Machines in Terms of Multi-Head and Auxiliary Stack Automata, J. Comput. System. Sc., Vol. 5, 1971, pp. 88-117. Zbl0255.68012MR284290
  17. 17. I. H. SUDBOROUGH, On the Tape Complexity of Deterministic Context-Free Languages, J. Assoc. Comp. Mach., Vol. 25, 1978, pp. 405-414. Zbl0379.68054MR498563

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.