Tseitin or not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses
| dc.contributor.author | Kuiter, Elias | |
| dc.contributor.author | Krieter, Sebastian | |
| dc.contributor.author | Sundermann, Chico | |
| dc.contributor.author | Thüm, Thomas | |
| dc.contributor.author | Saake, Gunter | |
| dc.contributor.editor | Engels, Gregor | |
| dc.contributor.editor | Hebig, Regina | |
| dc.contributor.editor | Tichy, Matthias | |
| dc.date.accessioned | 2023-01-18T13:38:45Z | |
| dc.date.available | 2023-01-18T13:38:45Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | This work was published at the 37th IEEE/ACM International Conference on Automated Software Engineering (ASE) 2022 [Ku22]. Feature modeling is widely used to systematically model features of variant-rich software systems and their dependencies. By translating feature models into propositional formulas and analyzing them with solvers, a wide range of automated analyses across all phases of the software development process become possible. Most solvers only accept formulas in conjunctive normal form (CNF), so an additional transformation of feature models is often necessary. However, it is unclear whether this transformation has a noticeable impact on analyses. We compare three transformations for bringing feature-model formulas into CNF. We analyze which transformation can be used to correctly perform feature-model analyses and evaluate three CNF transformation tools on a corpus of 22 real-world feature models. Our empirical evaluation illustrates that some CNF transformations do not scale to complex feature models or even lead to wrong results for model-counting analyses. Further, the choice of the CNF transformation can substantially influence the performance of subsequent analyses. | en |
| dc.identifier.isbn | 978-3-88579-726-5 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40094 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | Software Engineering 2023 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-332 | |
| dc.subject | Feature Modeling | |
| dc.subject | Automated Reasoning | |
| dc.subject | Conjunctive Normal Form | |
| dc.title | Tseitin or not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 84 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 83 | |
| gi.conference.date | 20.–24. Februar 2023 | |
| gi.conference.location | Paderborn | |
| gi.conference.sessiontitle | Wissenschaftliches Hauptprogramm |
Dateien
Originalbündel
1 - 1 von 1