@article{Helmert_Röger_Sievers_2015, title={On the Expressive Power of Non-Linear Merge-and-Shrink Representations}, volume={25}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/13732}, DOI={10.1609/icaps.v25i1.13732}, abstractNote={ <p> 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. </p> }, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Helmert, Malte and Röger, Gabriele and Sievers, Silvan}, year={2015}, month={Apr.}, pages={106-114} }