Journal article

Publication year: 2019

Pages: 5-27

Journal: International Journal of Foundations of Computer Science

Volume number: 30

Issue number: 1

ISSN: 0129-0541

eISSN: 1793-6373

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

Publisher: World Scientific Publishing

Abstract: 
We consider jumping finite automata and their operational state complexity and decidability status. Roughly speaking, a jumping automaton is a finite automaton with a non-continuous input. This device has nice relations to semilinear sets and thus to Parikh images of regular sets, which will be exhaustively used in our proofs. In particular, we prove upper bounds on the intersection and complementation. The latter result on the complementation upper bound answers an open problem from [G. J. Lavado, G. Pighizzini, S. Seki: Operational State Complexity of Parikh Equivalence, 2014]. Moreover, we correct an erroneous result on the inverse homomorphism closure. Finally, we also consider the decidability status of standard problems as regularity, disjointness, universality, inclusion, etc. for jumping finite automata.

Harvard Citation style: Beier, S., Holzer, M. and Kutrib, M. (2019) Operational State Complexity and Decidability of Jumping Finite Automata, International Journal of Foundations of Computer Science, 30(1), pp. 5-27. https://doi.org/10.1142/S012905411940001X

APA Citation style: Beier, S., Holzer, M., & Kutrib, M. (2019). Operational State Complexity and Decidability of Jumping Finite Automata. International Journal of Foundations of Computer Science. 30(1), 5-27. https://doi.org/10.1142/S012905411940001X