Non-returning deterministic and nondeterministic finite automata with translucent letters
Authors:
Open Access
- 18 October 2023
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 57, 8
Abstract
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 instead continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, reject, or continue, which means that it reads the remaining tape contents again 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, comparing them to various other types of finite automata that do not simply read their input from left to right. Also, we are interested in the closure properties of the resulting classes of languages and in the complexity of the fixed membership problem.Keywords
This publication has 17 references indexed in Scilit:
- Globally deterministic CD-systems of stateless R-automata with window size 1International Journal of Computer Mathematics, 2013
- JUMPING FINITE AUTOMATAInternational Journal of Foundations of Computer Science, 2012
- On CD-systems of stateless deterministic R-automata with window size oneJournal of Computer and System Sciences, 2012
- Globally Deterministic CD-Systems of Stateless R(1)-Automata2011
- CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages2010
- On input-revolving deterministic and nondeterministic finite automataInformation and Computation, 2009
- On 5′→3′ Sensing Watson-Crick Finite Automata2008
- Linear Context Free LanguagesLecture Notes in Computer Science, 2007
- Growing Context-Sensitive Languages and Church–Rosser LanguagesInformation and Computation, 1998
- Restarting automata1995