Elimination of Constraints from Feature Trees

We present an algorithm which eliminates constraints from a feature model whose feature diagram is a tree and whose constraints are "requires" or "excludes " constraints. The algorithm constructs a feature tree which has the same semantics as the original feature model. The computational complexity of the algorithm is exponential in the number of constraints, but linear in the number of features. The algorithm allows to efficiently compute properties of product lines whose feature model consists of a feature tree and a small number of "requires " and "excludes" constraints. An executable specification of the algorithm is given in the functional programming language Miranda