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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jančar, P., Mráz, F., Plátek, M.: A taxonomy of forgetting automata. In: Borzyszkowski, A.M., Sokolowski, S. (eds.) MFCS 1993. LNCS, vol. 711, pp. 527–536. Springer, Heidelberg (1993)
Jančar, P., Mráz, F., Plátek, M.: Characterization of context-free languages by erasing automata. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 305–314. Springer, Heidelberg (1992)
Mráz, F., Plátek, M.: Erasing automata recognize more than context-free languages. Acta Mathematica et Informatica Universitatis Ostraviensis 3, 77–85 (1995)
von Braunmühl, B., Verbeek, R.: Finite change automata. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol. 67, pp. 91–100. Springer, Heidelberg (1979)
Plátek, M., Vogel, J.: Deterministic list automata and erasing graphs. The Prague bulletin of mathematical linguistics 45, 27–50 (1986)
Chytil, M.P., Plátek, M., Vogel, J.: A note on the Chomsky hierarchy. Bulletin of the EATCS 27, 23–30 (1985)
Jančar, P., Mráz, F., Plátek, M.: Forgetting automata and context-free languages. Acta Informatica 33, 409–420 (1996)
Jančar, P.: Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata. Acta Mathematica et Informatica Universitatis Ostraviensis 1, 67–74 (1993)
Jančar, P., Mráz, F., Plátek, M.: Forgetting automata and the Chomsky hierarchy. In: Proc. SOFSEM 1992, pp. 41–44 (1992)
Greibach, S.A.: Erasable context-free languages. Information and Control 29, 301–326 (1975)
Monien, B.: Two-way multihead automata over a one-letter alphabet. RAIRO – Theoretical Informatics and Applications 14, 67–82 (1980)
Ibarra, O.H., Trân, N.Q.: A note on simple programs with two variables. Theoretical Computer Science 112, 391–397 (1993)
Mráz, F., Plátek, M.: A remark about forgetting automata. In: Proc. SOFSEM 1993, pp. 63–66 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Glöckler, J. (2006). Forgetting Automata and Unary Languages. In: Ibarra, O.H., Yen, HC. (eds) Implementation and Application of Automata. CIAA 2006. Lecture Notes in Computer Science, vol 4094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11812128_18
Download citation
DOI: https://doi.org/10.1007/11812128_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37213-4
Online ISBN: 978-3-540-37214-1
eBook Packages: Computer ScienceComputer Science (R0)