Space classes, intersection of languages and bounded erasing homomorphisms
Brandstädt, Andreas
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983), p. 121-130 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1983-01-01
@article{ITA_1983__17_2_121_0,
     author = {Brandst\"adt, Andreas},
     title = {Space classes, intersection of languages and bounded erasing homomorphisms},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {17},
     year = {1983},
     pages = {121-130},
     mrnumber = {713225},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1983__17_2_121_0}
}

Brandstädt, Andreas. Space classes, intersection of languages and bounded erasing homomorphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983) pp. 121-130. http://gdmltest.u-ga.fr/item/ITA_1983__17_2_121_0/

1. A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation and Compiling, Vol. 1, Prentice-Hall, Englewood Cliffs N.J., 1972. | MR 408321

2. B. S. Baker and R. V. Book, Reversal-Bounded Multipushdown Machines, J. Comp. System Sc., Vol. 8, 1974, pp. 315-332. | MR 375844 | Zbl 0309.68043

3. R. V. Book, Translational Lemmas, Polynomial Time and (log n) j-Space, Theor. Comp. Sc., 1976, pp. 215-226. | MR 405918 | Zbl 0326.68030

4. R. V. Book, Complexity Classes of Formal Languages, MFCS, 1979, pp. 43-56, Lecture Notes in Comp. Sc., No. 74. | MR 570974 | Zbl 0413.68045

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. | MR 592764 | Zbl 0446.68040

6. R. V. Book and S. A. Greibach, Quasi-Realtime Languages, Math. Syst. Theory, Vol. 4, No. 2, 1970, pp. 97-111. | MR 276019 | Zbl 0188.33102

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. | MR 267993 | Zbl 0206.28702

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. | MR 433992 | Zbl 0292.68023

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. K. Culik Ii and N. O. Diamond, A Homomorphic Characterization of Time and Space Complexity Classes of Languages, Internat. J. Computer Math. (to appear). | MR 585410 | Zbl 0444.68035

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. | MR 235932 | Zbl 0165.32002

12. S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, 1975. | MR 443446 | Zbl 0325.68002

13. S. A Greibach, Remarks on the Complexity of Nondeterministic Counter Languages, Theor. Comp. Sc., Vol. 1, 1976, pp. 269-288. | MR 411257 | Zbl 0332.68039

14. J. Hartmanis, Context-Free Languages and Turing Machine Computations, Proc. Symp. Applied Math., Vol. 19, 1967, pp. 42-51. | MR 235938 | Zbl 0189.29101

15. O. M. Ibarra, Characterizations of Transductions Deflned by Abstract Families of Transducers Math. Syst. Theory, Vol. 5, 1971, pp. 271-281. | MR 305949 | Zbl 0221.94077

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. | MR 284290 | Zbl 0255.68012

17. I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, J. Assoc. Comp. Mach., Vol. 25, 1978, pp. 405-414. | MR 498563 | Zbl 0379.68054