Geodesic
Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Communications in Mathematics, Tome 1 (1993) no. 1, pp. 67-73 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 68Q45, 68Q70 
@article{COMIM_1993_1_1_a7,
     author = {Jan\v{c}ar, Petr},
     title = {Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata},
     journal = {Communications in Mathematics},
     pages = {67--73},
     year = {1993},
     volume = {1},
     number = {1},
     mrnumber = {1250928},
     zbl = {0853.68118},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/COMIM_1993_1_1_a7/}
}
TY  - JOUR
AU  - Jančar, Petr
TI  - Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
JO  - Communications in Mathematics
PY  - 1993
SP  - 67
EP  - 73
VL  - 1
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/COMIM_1993_1_1_a7/
LA  - en
ID  - COMIM_1993_1_1_a7
ER  - 
%0 Journal Article
%A Jančar, Petr
%T Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
%J Communications in Mathematics
%D 1993
%P 67-73
%V 1
%N 1
%U http://geodesic.mathdoc.fr/item/COMIM_1993_1_1_a7/
%G en
%F COMIM_1993_1_1_a7
Jančar, Petr. Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata. Communications in Mathematics, Tome 1 (1993) no. 1, pp. 67-73. http://geodesic.mathdoc.fr/item/COMIM_1993_1_1_a7/

[1] 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. | MR

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

[3] 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. | MR

[4] 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). | MR

[5] Savitch W. J.: Relationships between nondeterministic and deterministic tape complexities. J. of Computer and System Sciences 4 (1970), 177-192. | DOI | MR | Zbl