![]() Recently, there has been a considerable advance in techniques for dealing with these problems. Both mentioned operations over NFA are PSPACE-complete problems. Complementation is easy for deterministic FA (DFA)-just swapping accepting and non-accepting states-but a hard problem for nondeterministic FA (NFA), which need to be determinized first (this may lead to an exponential explosion in the number of the states of the automaton). The classical (so called textbook) approach is based on complementation of the language of an FA. Many of the mentioned applications need to perform certain expensive operations on FA, such as checking universality of an FA (i.e., checking whether it accepts any word over a given alphabet), or checking language inclusion of a pair of FA (i.e., testing whether the language of one FA is a subset of the language of the second FA). In formal verification alone are its uses abundant, e.g., in model checking of safety temporal properties, abstract regular model checking, static analysis, or decision procedures of some logics, such as Presburger arithmetic or weak monadic second-order theory of one successor (WS1S). Keywords: finite automata, formal verification, language inclusion, bisimulation up to congruence, antichains, simulation 1 INTRODUCTION A finite automaton (FA) is a computation model with applications in different branches of computer science, e.g., compiler design, formal verification or the design of digital circuits. The main goal of this paper is to describe these techniques which are being implemented as the new extension for the VATA library. ![]() Recently, several new techniques for this problem that avoid explicit determinization (using the so-called antichains or bisimulation up to congruence) have been proposed. However, this advantage may be lost if a naïve approach to some operations, in particular checking language inclusion, which performs explicit determinization of the NFA, is taken. Their advantages over deterministic finite automata (DFA) is that they may be exponentially conciser. ![]() EFFICIENT ALGORITHMS FOR FINITE AUTOMATA Martin Hruška Bachelor Degree Programme (3), FIT BUT E-mail: Supervised by: Ondˇrej Lengál E-mail: Abstract: Nondeterministic finite automata (NFA) are used in many areas of computer science, including, but not limited to, formal verification, or the design of digital circuits.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |