Journalartikel

Jahr der Veröffentlichung: 2019

Seiten: 5-27

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 30

Heftnummer: 1

ISSN: 0129-0541

eISSN: 1793-6373

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

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