
We introduce a model of oneway language acceptors (a variant of a checking
stack automaton) and show the following decidability properties: (1) The
deterministic version has a decidable membership problem but has an undecidable
emptiness problem. (2) The nondeterministic version has an undecidable
membership problem and emptiness problem. There are many models of accepting
devices for which there is no difference with these problems between
deterministic and nondeterministic versions, and the same holds for the
emptiness problem. As far as we know, the model we introduce above is the first
oneway model to exhibit properties (1) and (2). We define another family of
oneway acceptors where the nondeterministic version has an undecidable
emptiness problem, but the deterministic version has a decidable emptiness
problem. We also know of no other model with this property in the literature.
We also investigate decidability properties of other variations of checking
stack automata (e.g., allowing multiple stacks, twoway input, etc.).
Surprisingly, twoway deterministic machines with multiple checking stacks and
multiple reversalbounded counters are shown to have a decidable membership
problem, a very general model with this property.

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 oneway and twoway 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 nonregular are obtained.

The complexity and decidability of various decision problems involving the
shuffle operation are studied. The following three problems are all shown to be
$NP$complete: given a nondeterministic finite automaton (NFA) $M$, and two
words $u$ and $v$, is $L(M)$ not a subset of $u$ shuffled with $v$, is $u$
shuffled with $v$ not a subset of $L(M)$, and is $L(M)$ not equal to $u$
shuffled with $v$? It is also shown that there is a polynomialtime algorithm
to determine, for $NFA$s $M_1, M_2$ and a deterministic pushdown automaton
$M_3$, whether $L(M_1)$ shuffled with $L(M_2)$ is a subset of $L(M_3)$. The
same is true when $M_1, M_2,M_3$ are oneway nondeterministic
$l$reversalbounded $k$counter machines, with $M_3$ being deterministic.
Other decidability and complexity results are presented for testing whether
given languages $L_1, L_2$ and $R$ from various languages families satisfy
$L_1$ shuffled with $L_2$ is a subset of $R$, and $R$ is a subset of $L_1$
shuffled with $L_2$. Several closure results on shuffle are also shown.

The family, L(INDLIN), of languages generated by linear indexed grammars has
been studied in the literature. It is known that the Parikh image of every
language in L(INDLIN) is semilinear. However, there are bounded semi linear
languages that are not in L(INDLIN). Here, we look at larger families of
(restricted) indexed languages and study their properties, their relationships,
and their decidability properties.

Many different deletion operations are investigated applied to languages
accepted by oneway and twoway deterministic reversalbounded multicounter
machines, deterministic pushdown automata, and finite automata. Operations
studied include the prefix, suffix, infix and outfix operations, as well as
left and right quotient with languages from different families. It is often
expected that language families defined from deterministic machines will not be
closed under deletion operations. However, here, it is shown that oneway
deterministic reversalbounded multicounter languages are closed under right
quotient with languages from many different language families; even those
defined by nondeterministic machines such as the contextfree languages. Also,
it is shown that when starting with oneway deterministic machines with one
counter that makes only one reversal, taking the left quotient with languages
from many different language families  again including those defined by
nondeterministic machines such as the contextfree languages  yields only
oneway deterministic reversalbounded multicounter languages (by increasing
the number of counters). However, if there are two more reversals on the
counter, or a second 1reversalbounded counter, taking the left quotient (or
even just the suffix operation) yields languages that can neither be accepted
by deterministic reversalbounded multicounter machines, nor by 2way
nondeterministic machines with one reversalbounded counter.