Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Jančar, Petr
Acta Mathematica et Informatica Universitatis Ostraviensis, Tome 01 (1993), p. 67-73 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1993-01-01
Classification:  68Q45,  68Q70 
@article{120475,
     author = {Petr Jan\v car},
     title = {Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata},
     journal = {Acta Mathematica et Informatica Universitatis Ostraviensis},
     volume = {01},
     year = {1993},
     pages = {67-73},
     zbl = {0853.68118},
     mrnumber = {1250928},
     language = {en},
     url = {http://dml.mathdoc.fr/item/120475}
}

Jančar, Petr. Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata. Acta Mathematica et Informatica Universitatis Ostraviensis, Tome 01 (1993) pp. 67-73. http://gdmltest.u-ga.fr/item/120475/

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) | MR 0568095

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

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) | MR 1255145

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) | MR 1265088

Savitch W. J. Relationships between nondeterministic and deterministic tape complexities, J. of Computer and System Sciences 4 (1970), 177-192. (1970) | Article | MR 0266702 | Zbl 0188.33502