Geodesic
Erasing automata recognize more than context-free languages
Communications in Mathematics, Tome 3 (1995) no. 1, pp. 77-85 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 68Q45, 68Q68 
@article{COMIM_1995_3_1_a9,
     author = {Mr\'az, Franti\v{s}ek and Pl\'atek, Martin},
     title = {Erasing automata recognize more than context-free languages},
     journal = {Communications in Mathematics},
     pages = {77--85},
     year = {1995},
     volume = {3},
     number = {1},
     mrnumber = {1474070},
     zbl = {0856.68089},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/COMIM_1995_3_1_a9/}
}
TY  - JOUR
AU  - Mráz, František
AU  - Plátek, Martin
TI  - Erasing automata recognize more than context-free languages
JO  - Communications in Mathematics
PY  - 1995
SP  - 77
EP  - 85
VL  - 3
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/COMIM_1995_3_1_a9/
LA  - en
ID  - COMIM_1995_3_1_a9
ER  - 
%0 Journal Article
%A Mráz, František
%A Plátek, Martin
%T Erasing automata recognize more than context-free languages
%J Communications in Mathematics
%D 1995
%P 77-85
%V 3
%N 1
%U http://geodesic.mathdoc.fr/item/COMIM_1995_3_1_a9/
%G en
%F COMIM_1995_3_1_a9
Mráz, František; Plátek, Martin. Erasing automata recognize more than context-free languages. Communications in Mathematics, Tome 3 (1995) no. 1, pp. 77-85. http://geodesic.mathdoc.fr/item/COMIM_1995_3_1_a9/

[1] von Braunmühl B., Verbeek R.: Finite change automata. Proceedings of the Fourth GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Springer-Verlag 67 (1979), 91-100. | MR

[2] Hopcroft J. E., Ullman J. D.: Formal languages and their relation to automata. Addison-Wesley, Reading, Massachusetts, 1969. | MR | Zbl

[3] Immerman N.: Nondeterministic space is closed under complement. Proceedings of the 3rd Annual Conference Structure in Complexity Theory (June 1988), 14-17. | MR

[4] Jančar P.: Nondeterministic forgetting automata are less powerfull than deterministic linear bounded automata. Acta Mathematica et Informatica Universitatis Ostraviensis 1 (1993), 67-74. | MR

[5] Jančar P., Mráz F., Plátek M.: Characterization of context-free languages by erasing automata. in Proceedings of MFCS'92, Lecture Notes in Computer Science, Springer-Verlag 629 (August 1992), 307-314. | MR

[6] Jančar P., Mráz F., Plátek M.: Forgetting automata and the Chomsky hierarchy. SOFSEM '92, 1992.

[7] Jančar P., Mráz F., Plátek M.: A taxonomy of forgetting automata. in Proceedings of MFCS '93, Lecture Notes in Computer Science, Springer-Verlag 711 (August 1993), 527-536. | MR

[8] Mráz F., Plátek M.: Erasing automata recognize more than context-free languages. in SOFSEM '91, Jasná pod Chopkom, Nízké Tatry 1991.

[9] Mráz F., Plátek M.: A remark about forgetting automata. in SOFSEM'93, Hrdoňov, 63-66, 1993.

[10] Plátek M., Vogel J.: Deterministic list automata and erasing graphs. The Prague Bulletin of Mathematical Linguistics, Prague 45 (1986), 27-50. | MR

[11] Rytter W.: On the recognition of context-free languages. in proceedings of Fifth Symposium on Computation Theory, Lecture Notes in computer Science, Springer-Verlag 208 (1985), 318-325. | MR | Zbl

[12] Szelepcsényi R.: The method of forced enumeration for nondeterministic automata. Acta Informatica 26 (3) (November 1988), 279-284. | DOI | MR