@article{ITA_1983__17_2_121_0, author = {Brandst\"adt, Andreas}, title = {Space classes, intersection of languages and bounded erasing homomorphisms}, journal = {RAIRO. Informatique th\'eorique}, pages = {121--130}, publisher = {EDP-Sciences}, volume = {17}, number = {2}, year = {1983}, mrnumber = {713225}, language = {en}, url = {http://archive.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. Informatique théorique PY - 1983 SP - 121 EP - 130 VL - 17 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_1983__17_2_121_0/ LA - en ID - ITA_1983__17_2_121_0 ER -
Brandstädt, Andreas. Space classes, intersection of languages and bounded erasing homomorphisms. RAIRO. Informatique théorique, Tome 17 (1983) no. 2, pp. 121-130. http://archive.numdam.org/item/ITA_1983__17_2_121_0/
1. The Theory of Parsing, Translation and Compiling, Vol. 1, Prentice-Hall, Englewood Cliffs N.J., 1972. | MR
and ,2. Reversal-Bounded Multipushdown Machines, J. Comp. System Sc., Vol. 8, 1974, pp. 315-332. | MR | Zbl
and ,3. Translational Lemmas, Polynomial Time and (log n) j-Space, Theor. Comp. Sc., 1976, pp. 215-226. | MR | Zbl
,4. Complexity Classes of Formal Languages, MFCS, 1979, pp. 43-56, Lecture Notes in Comp. Sc., No. 74. | MR | Zbl
,5. Equality Sets and Complexity Classes, S.I.A.M. J. Computing, Vol. 9, No. 4, 1980, pp. 729-743. | MR | Zbl
and ,6. Quasi-Realtime Languages, Math. Syst. Theory, Vol. 4, No. 2, 1970, pp. 97-111. | MR | Zbl
and ,7. Time- and Tape-Bouded Turing Acceptors and AFLs, J. Comp. System Sc., Vol. 4, No. 6, 1970, pp. 606-621. | MR | Zbl
, and ,8. Reversal-Bounded Acceptors and Intersections of Linear Languages, S.I.A.M. J. Computing, Vol. 3, No. 4, 1974, pp. 283-295. | MR | Zbl
, and ,9. Homomorphisms; Decidability, Equality and Test Sets; Formal Language Theory, Perspectives and Open Problems, R. V. Book, Ed., Academic Press, 1980.
,10. A Homomorphic Characterization of Time and Space Complexity Classes of Languages, Internat. J. Computer Math. (to appear). | MR | Zbl
and ,11. Counter Machines and Counter Languages, Math. Syst. Theory, Vol. 2, No. 3, 1968, pp. 265-283. | MR | Zbl
, and ,12. Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, 1975. | MR | Zbl
,13. Remarks on the Complexity of Nondeterministic Counter Languages, Theor. Comp. Sc., Vol. 1, 1976, pp. 269-288. | MR | Zbl
,14. Context-Free Languages and Turing Machine Computations, Proc. Symp. Applied Math., Vol. 19, 1967, pp. 42-51. | MR | Zbl
,15. Characterizations of Transductions Deflned by Abstract Families of Transducers Math. Syst. Theory, Vol. 5, 1971, pp. 271-281. | MR | Zbl
,16. 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 | Zbl
,17. On the Tape Complexity of Deterministic Context-Free Languages, J. Assoc. Comp. Mach., Vol. 25, 1978, pp. 405-414. | MR | Zbl
,