Efficient reduction of nondeterministic automata with application to language inclusion testing
2019
We present efficient algorithms to reduce the size of nondeterministic
B\"uchi word automata (NBA) and nondeterministic finite word automata (NFA),
while retaining their languages. Additionally, we describe methods to solve
PSPACE-complete automata problems like language universality, equivalence, and
inclusion for much larger instances than was previously possible ($\ge 1000$
states instead of 10-100). This can be used to scale up applications of
automata in formal verification tools and decision procedures for logical
theories. The algorithms are based on new techniques for removing transitions
(pruning) and adding transitions (saturation), as well as extensions of classic
quotienting of the state space. These techniques use criteria based on
combinations of backward and forward trace inclusions and simulation relations.
Since trace inclusion relations are themselves PSPACE-complete, we introduce
lookahead simulations as good polynomial time computable approximations
thereof. Extensive experiments show that the average-case time complexity of
our algorithms scales slightly above quadratically. (The space complexity is
worst-case quadratic.) The size reduction of the automata depends very much on
the class of instances, but our algorithm consistently reduces the size far
more than all previous techniques. We tested our algorithms on NBA derived from
LTL-formulae, NBA derived from mutual exclusion protocols and many classes of
random NBA and NFA, and compared their performance to the well-known automata
tool GOAL.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI