Erasing automata recognize more than context-free languages
Acta Mathematica et Informatica Universitatis Ostraviensis (1995)
- Volume: 03, Issue: 1, page 77-(85)
- ISSN: 1804-1388
Access Full Article
top
How to cite
topMráz, František, and Plátek, Martin. "Erasing automata recognize more than context-free languages." Acta Mathematica et Informatica Universitatis Ostraviensis 03.1 (1995): 77-(85). <http://eudml.org/doc/23768>.
@article{Mráz1995,
author = {Mráz, František, Plátek, Martin},
journal = {Acta Mathematica et Informatica Universitatis Ostraviensis},
keywords = {erasing automaton; linear bounded Turing machine},
language = {eng},
number = {1},
pages = {77-(85)},
publisher = {University of Ostrava},
title = {Erasing automata recognize more than context-free languages},
url = {http://eudml.org/doc/23768},
volume = {03},
year = {1995},
}
TY - JOUR
AU - Mráz, František
AU - Plátek, Martin
TI - Erasing automata recognize more than context-free languages
JO - Acta Mathematica et Informatica Universitatis Ostraviensis
PY - 1995
PB - University of Ostrava
VL - 03
IS - 1
SP - 77
EP - (85)
LA - eng
KW - erasing automaton; linear bounded Turing machine
UR - http://eudml.org/doc/23768
ER -
References
top- 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) MR0568095
- Hopcroft J. E., Ullman J. D., Formal languages and their relation to automata, Addison-Wesley, Reading, Massachusetts, 1969. (1969) Zbl0196.01701MR0237243
- Immerman N., Nondeterministic space is closed under complement, Proceedings of the 3rd Annual Conference Structure in Complexity Theory (June 1988), 14-17. (1988) MR0961049
- 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) MR1250928
- 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) MR1255145
- 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) MR1265088
- 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) MR0845522
- 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) Zbl0605.68077MR0827542
- Szelepcsényi R., 10.1007/BF00299636, Acta Informatica 26 (3) (November 1988), 279-284. (1988) MR0975334DOI10.1007/BF00299636
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.