A theoretical framework for cardinality-based feature models: The semantics and computational aspects

Feature modeling is the most common approach for modeling software product line configurations. We propose a formal language-based formalization for the hierarchical semantics of cardinality-based feature models. We provide a transformation mapping, which allows us to transform a cardinality-based feature diagram to an appropriate regular expression. We propose a formal framework for expressing crosscutting constraints over cardinality-based feature diagrams. We then provide two kinds of semantics for constraints: the flat and the language semantics. We show how to integrate the semantics of diagrams and constraints over them. We also characterize some analysis operations over feature models in terms of operations on languages and discuss the corresponding decidability and computational complexity problems.