On Two Characterizations of Feature Models

Software-intensive systems can have thousands of interdependent configuration options across different subsystems. Feature models allow designers to organize the configuration space by describing configuration options using interdependent features: a feature is a name representing some functionality and each software variant is identified by a set of features. Different representations of feature models have been proposed in the literature. In this paper we focus on the propositional representation (which works well in practice) and the extensional representation (which has been recently shown well suited for theoretical investigations). We provide an algebraic and a propositional characterization of feature model operations and relations, and we formalize the connection between the two characterizations as monomorphisms from lattices of propositional feature models to lattices of extensional features models. This formalization sheds new light on the correspondence between the extensional and the propositional representations of feature models. It aims to foster the development of a formal framework for supporting practical exploitation of future theoretical developments on feature models and software product lines.