Title: On Store Languages of Language Acceptors,
Abstract: It is well known that the "store language" of every pushdown automaton -- the
set of store configurations (state and stack contents) that can appear as an
intermediate step in accepting computations -- is a regular language. Here many
models of language acceptors with various data structures are examined, along
with a study of their store languages. For each model, an attempt is made to
find the simplest model that accepts their store languages. Some connections
between store languages of one-way and two-way machines generally are
demonstrated, as with connections between nondeterministic and deterministic
machines. A nice application of these store language results is also presented,
showing a general technique for proving families accepted by many deterministic
models are closed under right quotient with regular languages, resolving some
open questions (and significantly simplifying proofs for others that are known)
in the literature. Lower bounds on the space complexity for recognizing store
languages for the languages to be non-regular are obtained.