| Title:
|
Erasing automata recognize more than context-free languages (English) |
| Author:
|
Mráz, František |
| Author:
|
Plátek, Martin |
| Language:
|
English |
| Journal:
|
Acta Mathematica et Informatica Universitatis Ostraviensis |
| ISSN:
|
1211-4774 |
| Volume:
|
3 |
| Issue:
|
1 |
| Year:
|
1995 |
| Pages:
|
77-(85) |
| . |
| Category:
|
math |
| . |
| MSC:
|
68Q45 |
| MSC:
|
68Q68 |
| idZBL:
|
Zbl 0856.68089 |
| idMR:
|
MR1474070 |
| . |
| Date available:
|
2009-01-30T09:02:39Z |
| Last updated:
|
2013-10-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/120489 |
| . |
| Reference:
|
[1] 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. MR 0568095 |
| Reference:
|
[2] Hopcroft J. E., Ullman J. D.: Formal languages and their relation to automata.Addison-Wesley, Reading, Massachusetts, 1969. Zbl 0196.01701, MR 0237243 |
| Reference:
|
[3] Immerman N.: Nondeterministic space is closed under complement.Proceedings of the 3rd Annual Conference Structure in Complexity Theory (June 1988), 14-17. MR 0961049 |
| Reference:
|
[4] Jančar P.: Nondeterministic forgetting automata are less powerfull than deterministic linear bounded automata.Acta Mathematica et Informatica Universitatis Ostraviensis 1 (1993), 67-74. MR 1250928 |
| Reference:
|
[5] 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. MR 1255145 |
| Reference:
|
[6] Jančar P., Mráz F., Plátek M.: Forgetting automata and the Chomsky hierarchy.SOFSEM '92, 1992. |
| Reference:
|
[7] 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. MR 1265088 |
| Reference:
|
[8] Mráz F., Plátek M.: Erasing automata recognize more than context-free languages.in SOFSEM '91, Jasná pod Chopkom, Nízké Tatry 1991. |
| Reference:
|
[9] Mráz F., Plátek M.: A remark about forgetting automata.in SOFSEM'93, Hrdoňov, 63-66, 1993. |
| Reference:
|
[10] Plátek M., Vogel J.: Deterministic list automata and erasing graphs.The Prague Bulletin of Mathematical Linguistics, Prague 45 (1986), 27-50. MR 0845522 |
| Reference:
|
[11] 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. Zbl 0605.68077, MR 0827542 |
| Reference:
|
[12] Szelepcsényi R.: The method of forced enumeration for nondeterministic automata.Acta Informatica 26 (3) (November 1988), 279-284. MR 0975334, 10.1007/BF00299636 |
| . |
