Thesis Details
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
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Novák Michal, doc. RNDr., Ph.D. (DMAT FEEC BUT), člen
Strnadel Josef, Ing., Ph.D. (DCSY FIT BUT), člen
Szőke Igor, Ing., Ph.D. (DCGM FIT BUT), člen
@bachelorsthesis{FITBT19890, author = "Ladislav R\r{u}\v{z}i\v{c}ka", type = "Bachelor's thesis", title = "Demonstrace sk\'{a}kaj\'{i}c\'{i}ch automat\r{u}", school = "Brno University of Technology, Faculty of Information Technology", year = 2017, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/19890/" }