Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Properties of right one-way jumping finite automata

Beier, Simon ; Holzer, Markus

Zum Volltext im pdf-Format: Dokument 1.pdf (1.043 KB)

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-135162

Bookmark bei

Freie Schlagwörter (Englisch): jumping finite automata , one-way restriction , characterizations , inclusion relations , closure properties
MSC - Klassifikation: 68Q45
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1802
Sprache: Englisch
Erstellungsjahr: 2018
Publikationsdatum: 24.04.2018
Kurzfassung auf Englisch: Right one-way jumping finite automata (ROWJFAs), were recently introduced in [H. Chigahara, S.Z. Fazekas, A. Yamamura: One-Way Jumping Finite Automata, Internat. J. Found. Comput. Sci., 27(3), 2016] and are jumping automata that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We solve most of the open problems of these devices. In particular, we characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to other language families. We also give more characterizations of languages accepted by ROWJFAs for some interesting cases.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand