A Two-Dimensional Infinite Hierarchy for Finite Automata with Translucent Words
Benedek Nagy, Friedrich Otto · Journal of automata, languages and combinatorics · 2026
Here we generalize the deterministic and the nondeterministic finite automaton with translucent letters (DFAwtl and NFAwtl) by extending the sets of translucent letters to sets of translucent words, where we require that each such set is a finite prefix code. The classes of languages accepted by these automata properly extend the language classes that are accepted by DFAwtls and by NFAwtls. We then parameterize the finite automata with translucent words by restricting the cardinality of the admitted sets of translucent words and the maximal length of these words. These two parameters induce an infinite strictly ascending two-dimensional hierarchy of language classes in the deterministic as well as in the nondeterministic case. In addition, we study closure properties for these language classes and consider the membership problem and some other decision problems.