A Fast Counting-Free Algorithm for Computing Atomic Sets in Feature Models
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913659920318464 |
|---|---|
| author | Heß, Tobias Molt, Aaron |
| author_facet | Heß, Tobias Molt, Aaron |
| contents | In the context of product-line engineering and feature models, atomic sets are sets of features that must always be selected together in order for a configuration to be valid. For many analyses and applications, these features may be condensed into one feature, without affecting, for instance, satisfiability, model counting, sampling, or knowledge compilation. However, the performance of current approaches tends to be insufficient in practice. This is especially true but not limited to approaches based on model counting. In this work, we present a counting-free algorithm for computing atomic sets that only relies on SAT solving. Our evaluation shows that it scales with ease to hard real-world systems and even succeeds for a contemporary version of the Linux kernel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12490 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fast Counting-Free Algorithm for Computing Atomic Sets in Feature Models Heß, Tobias Molt, Aaron Data Structures and Algorithms In the context of product-line engineering and feature models, atomic sets are sets of features that must always be selected together in order for a configuration to be valid. For many analyses and applications, these features may be condensed into one feature, without affecting, for instance, satisfiability, model counting, sampling, or knowledge compilation. However, the performance of current approaches tends to be insufficient in practice. This is especially true but not limited to approaches based on model counting. In this work, we present a counting-free algorithm for computing atomic sets that only relies on SAT solving. Our evaluation shows that it scales with ease to hard real-world systems and even succeeds for a contemporary version of the Linux kernel. |
| title | A Fast Counting-Free Algorithm for Computing Atomic Sets in Feature Models |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.12490 |