Deterministic Pushdown Automata with Translucent Input Letters

The use of translucent input letters is a variant of a dis- continuous input processing in automata. In detail, the automaton per- forms several sweeps from left to right on the input. Depending on the current state of the automaton, some symbols are visible and can be processed, whereas some other symbols are invisible, and may be pro- cessed in another sweep. We also distinguish between the returning and non-returning mode, which differ from the fact that a new sweep starts or not, respectively, immediately after processing a visible input symbol. Here, we investigate deterministic pushdown automata with translucent letters both in the returning and non-returning mode. It turns out that the families of the languages accepted by these two types of devices can properly be ranked between the deterministic context-free languages and the deterministic context-sensitive languages. Moreover, both families are incomparable with the families of Church-Rosser languages, context-free languages, and growing context-sensitive languages. Finally, we study the closure of both language families under the Boolean operations and we obtain for both families the closure under complementation, and the non-closure under union and intersection.