|
|
Repetitive Substructures for Efficient Representation of Automata
Šedý, Michal ; Češka, Milan (oponent) ; Holík, Lukáš (vedoucí práce)
Nondeterministic finite automata (NFAs) are widely used across almost every field of computer science, such as for the representation of regular expressions, monitoring high-speed networks, in abstract regular model checking, program verification, in decision procedures of WS1S and WS2S logics, linear integer arithmetic, temporal logics, or even in bioinformatics for searching sequences of nucleotides in DNA. Automata with a large number of states can lead to an exponential increase in the state space in many algorithms. To address this issue, minimization techniques, such as state merging and transition pruning, are used. Despite the strong minimization potential of these methods, the resulting automata can still contain duplicate substructures with equivalent transition sequences. There are even types of automata that cannot be minimized by these standard methods at all. This work presents a novel automata minimization approach based on a transformation of an NFA into a nondeterministic pushdown automaton (NPDA). The transformation identifies multiple similar substructures and replaces them with one common structure (called a procedure). By doing so, we were able to further reduce automata by up to 67.3%. The principle of transforming NFA into NPDA can be understood as a transformation of a purely sequential program into a program with functions and a call stack.
|
host ::
RSS.