  We introduce and study input-driven deterministic and nondeterministic
double-head pushdown automata. A double-head pushdown automaton is a slight
generalization of an ordinary pushdown automaton working with two input heads
that move in opposite directions on the common input tape. In every step one
head is moved and the automaton decides on acceptance if the heads meet.
Demanding the automaton to work input-driven it is required that every input
symbol uniquely defines the action on the pushdown store (push, pop, state
change). Normally this is modeled by a partition of the input alphabet and is
called a signature. Since our automaton model works with two heads either both
heads respect the same signature or each head owes its own signature. This
results in two variants of input-driven double-head pushdown automata. The
induced language families on input-driven double-head pushdown automata are
studied from the perspectives of their language describing capability, their
closure properties, and decision problems.
