The Semantics of Cardinality-Based Feature Models via Formal Languages

Cardinality-based feature models provide the most expressive language among the existing feature modeling languages. We provide a reduction process, which allows us to transform a cardinality-based feature diagram to an appropriate regular expression. As for crosscutting constraints, we propose a formal language interpretation of them. In this way, we provide a formal language-based semantics for cardinality-based feature models. Accordingly, we describe a computational hierarchy of feature models, which guides us in how feature models can be constructively analyzed. We also characterize some existing analysis operations over feature models in terms of languages and discuss the corresponding decidability problems.