Properties of Right One-Way Jumping Finite Automata

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905638
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:39 AM
Last modification on : Friday, October 26, 2018 - 8:05:06 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:30:03 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Simon Beier, Markus Holzer. Properties of Right One-Way Jumping Finite Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.11-23, ⟨10.1007/978-3-319-94631-3_2⟩. ⟨hal-01905638⟩

Share

Metrics

Record views

162