Demonstrace skákajících automatů

This paper is concerned with demonstration of newly investigated jumping finite automata. Unlike conventional finite automata that read input words continuously these automatas make a jump over some symbols and from there it can read a symbol. In this paper we will be mostly focused on finding a practical algorithm for solving the membership problem. As will be shown the membership problem for jumping finite automata can be reduced to finding a non-negative integral solution to a Quantifier-Free Presburger arithmetics formula. From such formula we are able to determine whole infinite language of jumping finite automata. We will show that some subset of jumping finite automata can be solved in polynomial time. We note that formula in Presburger arithmetics can be transformed to the corresponding concurent finite automata. Unfortunately for general jumping automata finding non-negative solution is not sufficent but it can reduce search space. Other heuristics will be presented that increase the effectivity for the general jumping finite automata acceptance process.

jumping finite automata, general jumping finite automata, membership problem, integer linear programming, constraint integer programming, backtrack, heuristics