Finite Automata with Sets of Translucent Words

Abstract

Here we study some restrictions and extensions of deterministic and nondeterministic finite automata with translucent letters (DFAwtl and NFAwtl). On the one hand, we restrict the cardinality of the sets of translucent letters, while, on the other hand, we introduce finite automata for which each state has an associated set of words that are translucent for that state. Here we require that each such set is a finite prefix code. We expect that, based on the cardinality of the sets of translucent words and the length of the longest word admitted in any set of this form, a strictly increasing two-dimensional hierarchy of language classes is obtained. In addition, we study closure and non-closure properties for the resulting language classes.