Generalized Label Reduction for Merge-and-Shrink Heuristics

Label reduction is a technique for simplifying families of labeled transition systems by dropping distinctions between certain transition labels. While label reduction is critical to the efficient computation of merge-and-shrink heuristics, current theory only permits reducing labels in a limited number of cases. We generalize this theory so that labels can be reduced in every intermediate abstraction of a merge-andshrink tree. This is particularly important for efficiently computing merge-and-shrink abstractions based on non-linear merge strategies. As a case study, we implement a nonlinear merge strategy based on the original work on mergeand-shrink heuristics in model checking by Dräger et al.

Authors

• Silvan Sievers
• Martin Wehrle
• Malte Helmert University of Basel

Keywords

No keywords are indexed for this paper.