Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

FORGETTING AUTOMATA AND UNARY LANGUAGES

JENS GLÖCKLER

Institut für Informatik, Universität Giessen, Arndtstr. 2, D-35392 Giessen, Germany

https://doi.org/10.1142/S0129054107004991Cited by:2 (Source: Crossref)

Abstract

We consider forgetting automata, i.e., linear bounded automata which can only use the operations "move", "erase" (rewrite with a blank symbol) and "delete" (remove completely). A classification of the families of languages corresponding to the possible combinations of operations has been given in [1], here we address some of the problems left open. Furthermore the unary case is being investigated.

Keywords:

AMSC: 68Q45

References

P. Jančar, F. Mráz and M. Plátek, A taxonomy of forgetting automata, Proc. MFCS 1993, LNCS 711 (Springer-Verlag, 1993) pp. 527–536. Google Scholar
P. Jančar, F. Mráz and M. Plátek, Characterization of context-free languages by erasing automata, Proc. MFCS 1992, LNCS 629 (Springer-Verlag, 1992) pp. 305–314. Google Scholar
F. Mráz and M. Plátek, Acta Mathematica et Informatica Universitatis Ostraviensis 3, 77 (1995). Google Scholar
B. von Braunmühl and R. Verbeek, Finite change automata, Proceedings of the Fourth GI Conference on Theoretical Computer Science, LNCS 67 (Springer-Verlag, 1979) pp. 91–100. Google Scholar
M. Plátek and J. Vogel, The Prague bulletin of mathematical linguistics 45, 27 (1986). Google Scholar
M. P. Chytil, M. Plátek and J. Vogel, Bulletin of the EATCS 27, 23 (1985). Web of Science, Google Scholar
P. Jančar, F. Mráz and M. Plátek, Acta Informatica 33, 409 (1996). Crossref, Web of Science, Google Scholar
P. Jančar, Acta Mathematica et Informatica Universitatis Ostraviensis 1, 67 (1993). Google Scholar
P. Jančar, F. Mráz and M. Plátek, Forgetting automata and the Chomsky hierarchy, Proc. SOFSEM 1992 (Masaryk University, Brno, Institute of Computer Science, 1992) pp. 41–44. Google Scholar
S. A. Greibach, Information and Control 29, 301 (1975), DOI: 10.1016/S0019-9958(75)80002-7. Crossref, Google Scholar
B. Monien, RAIRO - Theoretical Informatics and Applications 14, 67 (1980). Web of Science, Google Scholar
O. H. Ibarra and N. Q. Trân, Theoretical Computer Science 112, 391 (1993), DOI: 10.1016/0304-3975(93)90028-R. Crossref, Web of Science, Google Scholar
F. Mráz and M. Plátek, A remark about forgetting automata, Proc. SOFSEM 1993 (Masaryk University, Brno, Institute of Computer Science, 1993) pp. 63–66. Google Scholar