Erasing automata recognize more than context-free languages
Mráz, František ; Plátek, Martin
Acta Mathematica et Informatica Universitatis Ostraviensis, Tome 03 (1995), p. 77-(85) / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1995-01-01
Classification:  68Q45,  68Q68 
@article{120489,
     author = {Franti\v sek Mr\'az and Martin Pl\'atek},
     title = {Erasing automata recognize more than context-free languages},
     journal = {Acta Mathematica et Informatica Universitatis Ostraviensis},
     volume = {03},
     year = {1995},
     pages = {77-(85)},
     zbl = {0856.68089},
     mrnumber = {1474070},
     language = {en},
     url = {http://dml.mathdoc.fr/item/120489}
}

Mráz, František; Plátek, Martin. Erasing automata recognize more than context-free languages. Acta Mathematica et Informatica Universitatis Ostraviensis, Tome 03 (1995) pp. 77-(85). http://gdmltest.u-ga.fr/item/120489/

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. (1979) | MR 0568095

Hopcroft J. E.; Ullman J. D. Formal languages and their relation to automata, Addison-Wesley, Reading, Massachusetts, 1969. (1969) | MR 0237243 | Zbl 0196.01701

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

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

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. (1992) | MR 1255145

Jančar P.; Mráz F.; Plátek M. Forgetting automata and the Chomsky hierarchy, SOFSEM '92, 1992. (1992)

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. (1993) | MR 1265088

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

Mráz F.; Plátek M. A remark about forgetting automata, in SOFSEM'93, Hrdoňov, 63-66, 1993. (1993)

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

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. (1985) | MR 0827542 | Zbl 0605.68077

Szelepcsényi R. The method of forced enumeration for nondeterministic automata, Acta Informatica 26 (3) (November 1988), 279-284. (1988) | Article | MR 0975334