Non-Returning Finite Automata With Translucent Letters

František Mráz
(Charles University)
Friedrich Otto
(Universität Kassel)

Here we propose a variant of the nondeterministic finite automaton with translucent letters (NFAwtl) which, after reading and deleting a letter, does not return to the left end of its tape, but rather continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, to reject, or to continue, which means that it again reads the remaining tape contents from the beginning. This type of automaton, called a non-returning finite automaton with translucent letters or an nrNFAwtl, is strictly more expressive than the NFAwtl. We study the expressive capacity of this type of automaton and that of its deterministic variant. Also we are interested in closure properties of the resulting classes of languages and in decision problems.

In Henning Bordihn, Géza Horváth and György Vaszil: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2022), Debrecen, Hungary, August 26-27, 2022, Electronic Proceedings in Theoretical Computer Science 367, pp. 143–159.
Published: 27th August 2022.

ArXived at: https://dx.doi.org/10.4204/EPTCS.367.10 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org