On the expressive power of non-linear Merge-and-Shrink representations

Helmert, Malte and Röger, Gabriele and Sievers, Silvan. (2015) On the expressive power of non-linear Merge-and-Shrink representations. In: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015). Palo Alto, California, pp. 106-114.

PDF - Published Version

Official URL: http://edoc.unibas.ch/43153/

Downloads: Statistics Overview


We prove that general merge-and-shrink representations are
strictly more powerful than linear ones by showing that there exist problem families that can be represented compactly with general merge-and-shrink representations but not with linear ones. We also give a precise bound that quantifies the necessary blowup incurred by conversions from general merge-and-shrink representations to linear representations or BDDs/ADDs. Our theoretical results suggest an untapped potential for non-linear merging strategies and for the use of non-linear merge-and-shrink-like representations within symbolic search.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Röger, Gabriele and Helmert, Malte and Sievers, Silvan
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 16:46
Deposited On:11 Oct 2017 07:50

Repository Staff Only: item control page