On Properties of Languages Accepted by Deterministic Pushdown Automata with Translucent Input Letters

We study deterministic pushdown automata operating with translucent input letters. These devices can be obtained by equipping classical deterministic pushdown automata with a translucency function which, depending on the current state, establishes the set of invisible input symbols: such symbols are skipped in the current move and dealt with in subsequent sweeps, while the first visible symbol from the current input head position is processed. Translucent deterministic pushdown automata can be returning, meaning that a new input sweep starts from the leftmost input symbol immediately after processing a visible symbol, or not. We show some incomparability results between the acceptance capability of returning and non-returning translucent deterministic push- down automata and that of non-returning translucent deterministic and nondeterministic finite state automata. Then, we prove the non-closure of families of languages accepted by returning and non-returning translu- cent deterministic pushdown automata under concatenation, Kleene star, length-preserving and inverse homomorphism, reversal, and intersection with regular languages. In particular, arguments used to prove non- closure under this last language operation, enable us to answer a ques- tion on non-returning translucent deterministic finite state automata left open in the literature.