Journalartikel

Jahr der Veröffentlichung: 2020

Seiten: 805-825

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 31

Heftnummer: 6

ISSN: 0129-0541

eISSN: 1793-6373

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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