Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Acta Mathematica et Informatica Universitatis Ostraviensis (1993)
- Volume: 01, Issue: 1, page 67-73
- ISSN: 1804-1388
Access Full Article
topHow to cite
topReferences
top- von Braunmühl B., Verbeek R., Finite change automata, Proc. of 4th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science (LNCS) 67, Springer, Berlin (1979), 91-100. (1979) MR0568095
- Hopcroft J., Ullman J., Formal languages and their relation to automata, Addison-Wesley, 1969. (1969) Zbl0196.01701MR0237243
- Jančar P., Mráz F., Plátek M., Characterization of context-free languages by erasing automata, Proc. of the symp. Mathematical Foundations of Computer Science (MFCS) 1992, Prague, Czechoslovakia, LNCS 629, Springer (1992), 307-314. (1992) MR1255145
- Jančar P., Mráz F., Plátek M., A taxonomy of forgetting automata, accepted to MFCS'93, Gdansk, Poland, to appear in LNCS, Springer (1993). (1993) MR1265088
- Savitch W. J., 10.1016/S0022-0000(70)80006-X, J. of Computer and System Sciences 4 (1970), 177-192. (1970) Zbl0188.33502MR0266702DOI10.1016/S0022-0000(70)80006-X