Erschienen:
Association for the Advancement of Artificial Intelligence (AAAI), 2015
Erschienen in:Proceedings of the International Conference on Automated Planning and Scheduling
Sprache:
Nicht zu entscheiden
DOI:
10.1609/icaps.v25i1.13732
ISSN:
2334-0835;
2334-0843
Entstehung:
Anmerkungen:
Beschreibung:
<jats: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.
</jats:p>