Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Petr Jančar · Czech digital mathematics library · 1993
A complete proof of a result briefly mentioned in [4] is given.Forgetting automata are nondeterministic linear bounded automata with restricted rewriting capability: any input symbol can only be "erased" (rewritten by a speciál symbol) or completely "deleted".They are, in fact, a speciál čase of 2-change automata introduced in [1],This páper 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).