Sweeping Input-Driven Pushdown Automata

Input-driven pushdown automata ([Formula: see text]) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the current input symbol. Here, we introduce sweeping input-driven pushdown automata that process the input in multiple passes (also sweeps). That is, a sweeping input-driven pushdown automaton is a two-way device that may change the input head direction only at the endmarkers. First we show that, given an arbitrary [Formula: see text], an equivalent [Formula: see text] that halts on any input can effectively be constructed. From this result further properties follow. Then we address the determinization of [Formula: see text]s and its descriptional complexity. Furthermore, the computational capacity of [Formula: see text]s is studied. To this end, we compare the family [Formula: see text] with other well-known language families. In particular, we are interested in families that have strong relations to some kind of pushdown machines. Finally, we explore several decidability problems and show that emptiness and several other problems are non-semidecidable by reductions of non-semidecidable problems of deterministic, linearly space bounded, one-tape, one-head Turing machines.