On some Open Problems for Finite Automata with Translucent Input Letters

Martin Kutrib, Andreas Malcher, Matthias Wendlandt · 2026

Read On some Open Problems for Finite Automata with Translucent Input Letters by Martin Kutrib, Andreas Malcher, Matthias Wendlandt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26683.txt.

Introduction

Martin Kutrib, Andreas Malcher, and Matthias Wendlandt settle open questions about finite automata with translucent letters. A finite automaton reads input symbols through its current state. In this variant, some symbols are translucent in each state and get skipped. Only visible symbols are processed. Variants differ in determinism and in how scanning restarts.

Much was known about these machines' power, closures, and decidability. Several questions stayed open for years. The authors answer some of them here. Among the results, the language families are shown not to be closed under concatenation, joining languages end to end. Further answers concern how the deterministic and nondeterministic, returning and non-returning variants relate. The work closes gaps in a theory of discontinuous input processing, where a reader repeatedly skims past what it cannot yet use.

Catalog record

CREATORMartin Kutrib, Andreas Malcher, Matthias Wendlandt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26683

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On some Open Problems for Finite Automata with Translucent Input Letters Martin Kutrib, Andreas Malcher, Matthias Wendlandt Abstract 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 Mráz 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. 1 Introduction An automaton model typically processes its input in a continuous way, namely from left to right in models with one-way motion of the input head. In addition, one symbol is read at one time step and the input is accepted or rejected when the end of the input is reached. This “standard” input mode has been extended in the literature in several directions. For example, two-way motion of the input head, stationary moves of the input head, rotating the input head, or restarting modes have been considered for a wide variety of machines (the reader is referred to, e.g., [ 3 , 7 , 8 , 28 ] for an overview of these and other models). In all these extensions studied, consequences on the computational and descriptional power of the machines could be observed. Thus, the way of processing the input can be considered as a computational resource that then can be used to tune computational and descriptional power. In recent literature several variants of discontinuous input processing have been introduced and investigated. One of these variants is the “jumping” paradigm which means that jumping to any position inside the input string is allowed at any move. This paradigm has been introduced for finite automata in [ 16 ] , where it is shown that this discontinuous way of input processing may increase the computational power since it allows to accept some non-context-free languages, but also may decrease the computational power since it is known that some regular languages are not accepted by jumping finite automata [ 16 ] . “Right one-way jumping” automata which are a restricted variant of jumping finite automata are investigated in depth in [ 2 , 4 ] . Another discontinuous way of input processing is to make some parts of the input, depending on the state, invisible . This concept of translucent letters has been introduced by Nagy and Otto in [ 21 ] for deterministic and nondeterministic finite automata and the basic idea for such devices is to provide a translucency function that defines in which states which letters of the input are translucent. At each move, the device skips (by looking through) the translucent portion of the input, from the current input head position up to the first non-translucent letter (thus realizing a jump). After processing the non-translucent symbol, in the returning mode the input head returns to the left end of the input while, in the non-returning mode , the input head continues to process the input according to its updated current state and the corresponding translucent symbols. In both modes, the input head returns to the left end when the right end of the input is reached. Deterministic and nondeterministic finite automata with translucent input letters have deeply been investigated in the literature (see, e.g., [ 18 , 22 , 27 ] ). However, many questions are still open, but some of them will be answered in the present paper. Automata with translucent letters are an active area of research and many extensions and variants of the original model are currently investigated. Recently studied extensions are finite automata with translucent words [ 25 ] and finite automata with translucent letters and two-way motion of the input head [ 11 ] . Pushdown automata with translucent input letters in the returning mode are originally studied in [ 20 , 23 ] in terms of certain cooperating distributed systems of restarting automata with additional pushdown store. However, in their model \lambda -transitions are not allowed and acceptance is defined by empty pushdown. General pushdown automata with translucent input letters working in the returning mode as well as in the non-returning mode are introduced and studied in [ 12 , 13 ] . In [ 26 ] the paradigm of input-driven languages was imposed to certain cooperating distributed systems of restarting automata with additional pushdown store with regard to characterizing certain trace languages. A general definition of input-driven pushdown automata with translucent input letters and many results concerning their computational capacity, closure properties, decidability questions has been given in [ 14 ] . The jump complexity of finite automata with translucent input letters is studied in [ 6 , 17 ] , whereas subsequence matching problems of such automata are investigated in [ 5 ] . In this paper, we are going to investigate some problems on returning and non-returning finite automata with translucent input letters that have been left open in [ 18 , 22 ] . These open problems concern closure properties as well as decidability questions and will be answered in the present paper which is organized as follows. After giving the necessary definitions in the next section, we study in Section 3 several open problems on closure properties. For non-returning deterministic and nondeterministic finite automata with translucent input letters we can prove that the corresponding language families are not closed under concatenation, Kleene star, inverse homomorphism, and reversal. These questions have been left open in [ 18 ] . We further obtain the non-closure under complementation for non-returning nondeterministic finite automata with translucent input letters and the non-closure under inverse homomorphism for returning deterministic and nondeterministic finite automata with translucent input letters. The latter question has been left open in [ 22 ] . In Section 4 , we look at the emptiness problem for deterministic and nondeterministic finite automata with translucent input letters. It is known that this problem is decidable for the returning variants, whereas its decidability status for the non-returning case is left open in [ 18

Read the complete text