Space classes, intersection of languages and bounded erasing homomorphisms
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983) no. 2, pp. 121-130.
@article{ITA_1983__17_2_121_0,
title = {Space classes, intersection of languages and bounded erasing homomorphisms},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {121--130},
publisher = {EDP-Sciences},
volume = {17},
number = {2},
year = {1983},
mrnumber = {713225},
language = {en},
url = {http://www.numdam.org/item/ITA_1983__17_2_121_0/}
}
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
DA  - 1983///
SP  - 121
EP  - 130
VL  - 17
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1983__17_2_121_0/
UR  - https://www.ams.org/mathscinet-getitem?mr=713225
LA  - en
ID  - ITA_1983__17_2_121_0
ER  - 
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) no. 2, pp. 121-130. http://www.numdam.org/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