Sans Constraints? Feature Diagrams vs. Feature Models

摘要

In this paper we study constraints—inter-dependencies between basic features in a feature model which are not captured by diagrams. We offer a method for the removal of these constraints and explain why their removal require an (inevitable) exponential increase to the tree size. We show that the elimination of constraints makes it possible to provide an efficient solution for the feature editing problem, recently raised by Thiim, Batory and Kastner. We tie feature models with computer science fields which may appear very foreign to our domain, including circuit complexity, graph algorithms and algebraic complexity. The objective of this tie is double folded: drawing the attention of the foreign community to the problems we address in our field, and to suggest the use of current results in these fields for better understanding of the mathematics behind the modeling of software product lines.