Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Two-Way Jumping Automata
verfasst von : Szilárd Zsolt Fazekas, Kaito Hoshi, Akihiro Yamamura
Erschienen in: Frontiers in Algorithmics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The recently introduced one-way jumping automata are strictly more powerful than classical finite automata (FA) while maintaining decidability in most of the important cases. We investigate the extension of the new processing mode to two-way deterministic finite automata (2DFA), resulting in deterministic finite automata which can jump to the nearest letter they can read, with jumps allowed in either direction. We show that two-way jumping automata are strictly more powerful than one-way jumping ones and that alternative extensions of 2DFA with jumping mode lead to equivalent machines. We also prove that the class of languages accepted by the new model is not closed under the usual language operations. Finally we show how one could change the model to terminate on every input.