| Title:
|
Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata (English) |
| Author:
|
Jančar, Petr |
| Language:
|
English |
| Journal:
|
Acta Mathematica et Informatica Universitatis Ostraviensis |
| ISSN:
|
1211-4774 |
| Volume:
|
1 |
| Issue:
|
1 |
| Year:
|
1993 |
| Pages:
|
67-73 |
| . |
| Category:
|
math |
| . |
| MSC:
|
68Q45 |
| MSC:
|
68Q70 |
| idZBL:
|
Zbl 0853.68118 |
| idMR:
|
MR1250928 |
| . |
| Date available:
|
2009-01-30T09:00:57Z |
| Last updated:
|
2013-10-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/120475 |
| . |
| Reference:
|
[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 0568095 |
| Reference:
|
[2] Hopcroft J., Ullman J.: Formal languages and their relation to automata.Addison-Wesley, 1969. Zbl 0196.01701, MR 0237243 |
| Reference:
|
[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 1255145 |
| Reference:
|
[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 1265088 |
| Reference:
|
[5] Savitch W. J.: Relationships between nondeterministic and deterministic tape complexities.J. of Computer and System Sciences 4 (1970), 177-192. Zbl 0188.33502, MR 0266702, 10.1016/S0022-0000(70)80006-X |
| . |
