Hierarchical Multiset Theories of Cardinality-Based Feature Diagrams

Feature modeling is the most common approach to specify software product lines. The main part of a feature model is a special tree of features called a feature diagram. Cardinality-based feature diagrams provide the most expressive tool among the current feature diagram languages. The most common characterization of the semantics of a cardinality-based diagram is the set of flat multisets over features satisfying the constraints. However, this semantics provides a poor abstract view of the diagram. We address this problem by proposing another multiset theory for the diagram, called the hierarchical theory. We show that the theory captures all information of the diagram so that one can retrieve the diagram from its theory. This provides us with a theoretical framework for addressing some challenging issues in feature modeling, e.g., feature model management and reverse engineering of feature models.