Abstract
Forgetting automata are nondeterministic linear bounded automata whose rewriting capability is restricted as follows: each cell of the tape can only be “erased” (rewritten by a special symbol) or completely “deleted”.
We consider all classes of languages corresponding to various combinations of operations (erasing and deleting combined with moving the head), classify them according to the Chomsky hierarchy and show (some) other relations among them.
The research presented in this paper was carried out in connection with the COST Project No. 2824 “Language Processing Technologies for Slavic Languages”.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
von Braunmühl B., Verbeek R.: Finite change automata. Proceedings of the Fourth GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol.67, Springer-Verlag, Berlin, 1979, pp. 91–100
Jancar P.: Nondeterministic Forgetting Automata are Less Powerful than Deterministic Linear Bounded Automata, Acta Math. et Inf. Univ. Ostraviensis, 1, Ostrava, 1993 (to appear)
Jancar P., Mráz F., Plátek M.: Characterization of Context-Free Languages by Erasing Automata, in Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science 1992, Lecture Notes in Computer Science, Vol. 629, Springer-Verlag, Berlin 1992, pp.305–314
Jancar P., Mráz F., Plátek M.: Forgetting automata and the Chomsky hierarchy, in Proc. SOFSEM '92, Zdiar, Slovakia, November 1992, pp. 41–44
Jancar P., Mráz F., Plátek M.: A Taxonomy of Forgetting automata, Technical Rep. No. 101, Department of Computer Science, Charles University, Prague, May 1993
Plátek M., Vogel J.: Deterministic List Automata and Erasing Graphs, The Prague bulletin of mathematical linguistics 45, 1986
Plátek M.: Syntactic Error Recovery with Formal Guarantees I., Technical Rep. No. 100, Department of Computer Science, Charles University, Prague, April 1992
Sheperdson, J.C.: The Reduction of two-way automata to one way automata, IBM J. Res. Develop. 3, 1959, pp. 198–200
Savitch, W.J.: Relationships Between Nondeterministic and Deterministic tape Complexities, Jurnal of Computer and System Sciences 4, 1970, pp. 177–192
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jancar, P., Mráz, F., Plátek, M. (1993). A taxonomy of forgetting automata. In: Borzyszkowski, A.M., Sokołowski, S. (eds) Mathematical Foundations of Computer Science 1993. MFCS 1993. Lecture Notes in Computer Science, vol 711. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57182-5_44
Download citation
DOI: https://doi.org/10.1007/3-540-57182-5_44
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57182-7
Online ISBN: 978-3-540-47927-7
eBook Packages: Springer Book Archive