  There are many types of automata and grammar models that have been studied in
the literature, and for these models, it is common to determine whether certain
problems are decidable. One problem that has been difficult to answer
throughout the history of automata and formal language theory is to decide
whether a given system $M$ accepts a bounded language (whether there exist
words $w_1, \ldots,w_k$ such that $L(M) \subseteq w_1 \cdots w_k$?).
Decidability of this problem has gone unanswered for the majority of
automata/grammar models in the literature. Boundedness was only known to be
decidable for regular and context-free languages until recently when it was
shown to also be decidable for finite-automata and pushdown automata augmented
with reversal-bounded counters, and for vector addition systems with states.
  In this paper, we develop new techniques to show that the boundedness problem
is decidable for larger classes of one-way nondeterministic automata and
grammar models, by reducing the problem to the decidability of boundedness for
simpler classes of automata. One technique involves characterizing the models
in terms of multi-tape automata. We give new characterizations of finite-turn
Turing machines, finite-turn Turing machines augmented with various storage
structures (like a pushdown, multiple reversal-bounded counters,
partially-blind counters, etc.), and simple matrix grammars. The
characterizations are then used to show that the boundedness problem for these
models is decidable. Another technique uses the concept of the store language
of an automaton. This is used to show that the boundedness problem is decidable
for pushdown automata that can "flip" their pushdown a bounded number of times,
and boundedness remains decidable even if we augment this device with
additional stores.
