Journalartikel

Jahr der Veröffentlichung: 2019

Seiten: 78-94

Zeitschrift: Theoretical Computer Science

Bandnummer: 798

ISSN: 0304-3975

eISSN: 1879-2294

Open Access Status: Green

DOI Link: https://doi.org/10.1016/j.tcs.2019.03.044

Verlag: Elsevier

Abstract: 
Right one-way jumping finite automata (ROWJFAs), were recently introduced in H. Chiga-hara et al. (2016) [3] 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 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 families of the Chomsky-hierarchy and related families. We also give more characterizations of languages accepted by ROWJFAs in the case that the language is given as the concatenation of two languages. (C) 2019 Published by Elsevier B.V.

Harvard-Zitierstil: Beier, S. and Holzer, M. (2019) Properties of right one-way jumping finite automata, Theoretical Computer Science, 798, pp. 78-94. https://doi.org/10.1016/j.tcs.2019.03.044

APA-Zitierstil: Beier, S., & Holzer, M. (2019). Properties of right one-way jumping finite automata. Theoretical Computer Science. 798, 78-94. https://doi.org/10.1016/j.tcs.2019.03.044