Generalized Label Reduction for Merge-and-Shrink Heuristics


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



abstraction heuristics, merge-and-shrink, label reduction


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-and-shrink 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 non-linear merge strategy based on the original work on merge-and-shrink heuristics in model checking by Dräger et al.




How to Cite

Sievers, S., Wehrle, M., & Helmert, M. (2014). Generalized Label Reduction for Merge-and-Shrink Heuristics. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).