Journal article

Publication year: 2020

Pages: 805-825

Journal: International Journal of Foundations of Computer Science

Volume number: 31

Issue number: 6

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054120410063

Publisher: World Scientific Publishing

Abstract: 
We continue our investigation [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. In Proc. 20th DCFS, LNCS, 2018] on (right) one-way jumping finite automata (ROWJFAs), a variant of jumping automata, which is an automaton model for discontinuous information processing. Here we focus on decision problems for ROWJFAs. It turns out that most problems such as, e.g., emptiness, finiteness, universality, the word problem and variants thereof, closure under permutation, etc., are decidable. Moreover, we show that the containment of a language within the strict hierarchy of ROWJFA permutation closed languages induced by the number of accepting states as well as whether permutation closed regular or jumping finite automata languages can be accepted by ROWJFAs is decidable, too. On the other hand, we prove that for (linear) context-free languages the corresponding ROWJFA acceptance problem becomes undecidable. Moreover, we discuss also some complexity results for the considered decision problems.

Harvard Citation style: Beier, S. and Holzer, M. (2020) Decidability of Right One-Way Jumping Finite Automata, International Journal of Foundations of Computer Science, 31(6), pp. 805-825. https://doi.org/10.1142/S0129054120410063

APA Citation style: Beier, S., & Holzer, M. (2020). Decidability of Right One-Way Jumping Finite Automata. International Journal of Foundations of Computer Science. 31(6), 805-825. https://doi.org/10.1142/S0129054120410063