2026/06/25 by Martin Kutrib, Andreas Malcher, Matthias Wendlandt · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #Automaton #Closure (psychology) #DNA and Biological Computing #Decidability #Deterministic automaton #Deterministic finite automaton #Formal Methods in Verification #Homomorphism #Nested word #Nondeterministic algorithm #Nondeterministic finite automaton #cs.FL #semigroups and automata theory
paper · pdf · open access · doi:10.4204/eptcs.446.5
published in Electronic Proceedings in Theoretical Computer Science 446, 73-87 (Open Publishing Association)
openalex publication_date 2026/06/25 · arxiv published 2026/06/25 · arxiv updated 2026/06/25 · openalex created_date 2026/06/28 · openalex updated_date 2026/08/01
Finite automata with translucent input letters are a recent model of discontinuous input processing. Basically, classical finite automata are equipped with a translucency function that defines, depending on the state, the set of translucent input symbols. While processing the input, translucent symbols are skipped and only visible symbols are read and processed. It is distinguished between deterministic and nondeterministic models and, in addition, between returning and non-returning models. In the former case, the automaton restarts from the left end of the input after having consumed some visible symbol, whereas in the latter case the automaton restarts from the left end of the input when the right endmarker symbol is seen. Returning finite automata with translucent letters have been introduced by Nagy and Otto and its non-returning variant has been introduced by Mraz and Otto. Many results concerning the computational capacity, relations between deterministic and nondeterministic models, and relations between returning and non-returning models are known. Moreover, some results on closure properties and decidability questions have been obtained as well. However, some questions have still been open since many years. In this paper, we will give answers to some of these open questions. In particular, we show the non-closure under concatenation, Kleene star, reversal, and inverse homomorphism for the non-returning deterministic as well as nondeterministic model. We also obtain non-closure under inverse homomorphism for the returning deterministic and nondeterministic model. Finally, we investigate the emptiness problem for non-returning finite automata with translucent input letters and show the decidability of the problem in case of deterministic as well as nondeterministic automata.