zbMATH — the first resource for mathematics

Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata. (English) Zbl 0853.68118
Summary: Forgetting automata are nondeterministic linear bounded automata with restricted rewriting capability: any input symbol can only be “erased” (rewritten by a special symbol) or completely “deleted”. They are, in fact, a special case of 2-change automata introduced by B. von Braunmühl and R. Verbeek [Lect. Notes Comput. Sci. 67, 91-100 (1979; Zbl 0404.68081)].
This paper shows by the method of diagonalization that, for any \(k\), \(k\)-change automata with a fixed (work) alphabet recognize a proper subclass of the class of languages recognizable by deterministic linear bounded automata (i.e. deterministic context-sensitive languages).

68Q45 Formal languages and automata
Full Text: EuDML
[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. · Zbl 0404.68081
[2] Hopcroft J., Ullman J.: Formal languages and their relation to automata. Addison-Wesley, 1969. · Zbl 0196.01701
[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.
[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). · Zbl 0925.68320
[5] Savitch W. J.: Relationships between nondeterministic and deterministic tape complexities. J. of Computer and System Sciences 4 (1970), 177-192. · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.