On Repetitive Finite Automata with Translucent Words
arXiv:2507.15315 · doi:10.4204/EPTCS.422.5
Abstract
We introduce and study the repetitive variants of the deterministic and the nondeterministic finite automaton with translucent words (DFAwtw and NFAwtw). On seeing the right sentinel, a repetitive NFAwtw need not halt immediately, accepting or rejecting, but it may change into another state and continue with its computation. We establish that a repetitive DFAwtw already accepts a language that is not even semi-linear, which shows that the property of being repetitive increases the expressive capacity of the DFAwtw and the NFAwtw considerably.
arXiv commentIn Proceedings NCMA 2025, arXiv:2507.14082