Feature diagrams and logics: There and back again

Feature modeling is a notation and an approach for modeling commonality and variability in product fami-lies. In their basic form, feature models contain manda-tory/optional features, feature groups, and implies and ex-cludes relationships. It is known that such feature models can be translated into propositional formulas, which en-ables the analysis and configuration using existing logic-based tools. In this paper, we consider the opposite transla-tion problem, that is, the extraction of feature models from propositional formulas. We give an automatic and efficient procedure for computing a feature model from a formula. As a side effect we characterize a class of logical formulas equivalent to feature models and identify logical structures corresponding to their syntactic elements. While many different feature models can be extracted from a single formula, the computed model strives to ex-pose graphically the maximum of the original logical struc-ture while minimizing redundancies in the representation. The presented work furthers our understanding of the se-mantics of feature modeling and its relation to logics, open-ing avenues for new applications in reverse engineering and refactoring of feature models.