Unifying Software and Product Con guration: A Research Roadmap

Abstract

For more than 30 years, knowledge-based product con guration systems have been successfully applied in many industrial domains. Correspondingly, a large number of advanced techniques and algorithms have been developed in academia and industry to support di erent aspects of con guration reasoning. While traditional research in the eld focused on the con guration of physical artefacts, recognition of the business value of customizable software products led to the emergence of software product line engineering. Despite the signi cant overlap in research interests, the two elds mainly evolved in isolation. Only limited attempts were made at combining the approaches developed in the di erent elds. In this paper, we rst aim to give an overview of commonalities and di erences between software product line engineering and product con guration. We then identify opportunities for cross-fertilization between these elds and nally develop a research agenda to combine their respective techniques. Ultimately, this should lead to a uni ed con guration approach.

-

Customizable products are an integral part of most B2B and B2C markets. Mass-customization strategies have been applied to tangible products (e.g., cars and mobile phones) as well as intangible products like software (e.g., operating systems and ERPs) and services (e.g., insurance). To this end, companies use software con gurators that provide automated support to tailor products to the requirements of speci c customers or market segments.

Compared to the long history of computer-supported con guration of products, research on the con guration of parametrizable software is rather new. Product con guration (PC) is the umbrella activity of assembling and customizing physical artefacts (e.g. technical equipment, cars or muesli) or services. Historically, PC has been a sub eld of arti cial intelligence (AI), focusing on knowledge representation and reasoning techniques to support con guration. Mostly independent of PC, the eld of software product line engineering (SPLE) emerged in the software engineering community. SPLE deals with the design and implementation of software components that can be adapted and parametrized according to customer requirements and business or technical constraints [ 47 ]. As in PC approaches, the goal is to save costs by assembling individualized systems from reusable components [ 41 ]. Typical application domains for SPLE include embedded systems, device drivers, and operating systems.

Interestingly, research in these two elds has been carried out so far mostly independently. Except in rare cases (e.g. [ 28, 5 ]), researchers in both elds are often unaware of approaches that have been developed in the other community. Further, even though a lot of PC work has focused on con guring technical equipment, such equipment increasingly contains software. At the same time, SPLE increasingly targets software-intensive systems that also include computing and other types of equipment. Based on these observations, our hypothesis is that both the PC and SPLE communities have produced results that are applicable in the other domain.

The remainder of this paper explores further the opportunity for cross-fertilization (Section 2) and proposes a research roadmap (Section 3) to systematically compare the two domains and foster e orts towards unifying both elds. In particular, we hope to nd innovative approaches to questions that are largely open in one or the other community such as the recon guration of deployed systems, better interactive con guration support (e.g., in case of unsatis able requirements), methods for full lifecycle support and the evolution of models and knowledge bases. For this last question, we will also explore how techniques from software con guration management (CM) can be integrated. 2

Motivation

Questions of knowledge acquisition, knowledge representation as well as di erent types of reasoning support have been investigated for many years in PC and SPLE. We highlight some key results in both elds to show their commonalities and di erences. These preliminary observations motivate our endeavour to study, compare, and eventually unify research on con guration. We split the introduction of our motivations along ve dimensions. For each dimension, we also formulate the research questions whose answers should expose opportunities for cross-fertilization. 2.1

Knowledge acquisition and modelling

Research on PC has used a wide range of knowledge modeling approaches (based, e.g., on UML [ 22 ] or description logic [ 40 ]), involving di erent types of logics and constraints. While a few SPLE approaches also used UML to capture aspects of con guration knowledge (e.g. [ 60, 25 ]), most results build upon the seminal work on feature-oriented domain analysis (FODA) initiated in 1990 by Kang et al. [ 37 ], which today is converging with decision models [ 17 ]. The cornerstone of FODA are feature models (FMs), a graphical notation to capture and express the commonalities and variabilities of a product family. FMs are menu-like hierarchies of mandatory, optional, and alternative features, with cross-hierarchy relationships to express dependencies and incompatibilities. This initial FM notation has been gradually extended to support, for example, multiple instances [ 18, 44 ] or the con guration process [ 29 ].

Compared to con guration modelling ontologies used in PC (e.g., [ 22 ] or [ 53 ]), the expressiveness of FMs (even extended ones) appears too limited compared to more complex PC ontologies. Examples of advanced PC problems include connecting components via ports (i.e., inferring complex topologies), nding optimal or at least good con gurations, integrating iteratively new components, and distributing knowledge over di erent agents or business entities [ 32 ]. Some work exists in SPLE on component connection and integration (e.g. [ 5 ]) and optimization (e.g. [ 58 ]). This motivated the creation of more expressive languages (e.g., [ 8 ]). PC appears to o er a richer body of work in this area, though.

Opportunities for cross-fertilization: Some authors have already acknowledged the bond between con guration in PC and in SPLE through feature-based con guration. Gunter et al. [ 27 ] recognize concept hierarchies (similar to FMs) as a fundamental concept in their survey of knowledge-based con guration methods. According to Junker's classi cation of known con guration problems [ 34 ], feature-based con guration falls in the option selection or shopping list problems. To systematically identify such synergies, our research agenda should answer the following questions:

RQ1 What classes of con guration problems exist? RQ2 How are these problems modelled?

2.2

Automated reasoning

Generally, with respect to modeling and knowledge representation, the AI-rooted PC community is usually interested in \executable" models that can be directly translated into a representation processable by a reasoning engine. The formal basis of most knowledge modelling languages lays the foundation for advanced con guration reasoning techniques (e.g., checking for consistency of con gurations, completing partial con gurations, or supporting interactive con guration processes). In contrast, the SPLE community only started recently to develop a formal foundation of FMs (e.g. [ 9, 49 ]) and their analyses (e.g. [ 5, 43, 33, 59 ]). Based on precise formal problem characterizations, additional automations for SPLE become feasible. An example is the automated analysis of FMs; see [ 10 ] for an overview. Furthermore, Benavides et al. [ 11 ] propose to translate FMs into a Constraint Satisfaction Problem (CSP) and apply Reiter's model-based diagnosis (MBD) approach to detect problems in the models. Xiong et al. [ 59 ] combine MBD and Satis ability Modulo Theory (SMT) solvers to generate range xes in software con guration. Mendonca et al. [ 43 ] report on experiments with a SATencoding of FMs. Finally, Bagheri et al. [ 7 ], support hard and soft requirements in the con guration process.

The SPLE community sometimes reinvents techniques which have been developed previously in PC. Encoding con guration problems in some logic or as CSPs has a long history in the AI community [ 34 ]. The PC community was also the rst to apply SAT solvers to con guration problems [ 51 ]. New CSP representations such as Dynamic, Composite or Generative CSPs [ 45, 48, 54, 32 ] as well as logics [ 26, 4 ] were partially inspired by the challenges observed in PC. This latter pool of techniques addresses the problem of conditionally including multiple instances of a certain component type. The PC community was also rst to use MBD for con guration, e.g., for detecting problems in con guration knowledge bases [ 23 ]. Regarding soft constraints and preferences, there is abundant literature in constraint programming (e.g. [ 36, 46 ]). Finally, binary decision diagrams (BDDs) have also been used for building fast interactive con gurators (trading time vs space from a complexity point of view) [ 3 ]. That latter approach has been explored in SPLE as well (e.g. [ 42 ]), but it turned intractable on large FMs.

Opportunities for cross-fertilization: In contrast to physical components, software components are represented completely as computer artifacts. While physical components need to be speci ed explicitly in the computer to check crosscomponent compatibility, software con guration can analyze variability models and the actual con gurable artifacts at the same time. This opens up new possibilities for con guration, where the compatibility of components can be checked on the y during con guration without going back to the design phase and modifying con guration knowledge. To identify overlaps and di erences between SPLE and PC, we include the questions: RQ3 What automated tasks are supported (e.g., completion, repair, and optimization of con gurations)? RQ4 How are these automated tasks implemented? 2.3

Complexity

The computational complexity is an indicator of the amount of resources needed to solve a given problem. In PC, reasoning is usually achieved by encoding the problem in formalisms such as CSP, SAT, answer set programming or description logics, all of which are being supported by mature reasoners. Both SAT and CSP are well-known to be NP complete [ 15, 38 ]. Some extensions of CSPs (dynamic, composite) polynomially reduce to classical CSP [ 56 ] whereas the decidability of Generative CSP has yet to be established. Ground answer set programs are NP complete ( 2p complete in the case of optimization); if programs contain uninstantiated variables we obtain NEXPTIME completeness [ 50, 19 ]. Description logics are typically decidable fragments of rst order logic [ 6 ]; the DLs used in PC range from polynomial over PSPACE complete to undecidable [ 35, 40, 12 ]. Let us emphasize that the aforementioned complexity results are only upper bounds: Precise complexity results for classes of con guration problems are still too rare (e.g., [ 52 ]).

The same symptom can be observed in SPLE where only a tiny fraction of the papers study complexity aspects (e.g. [ 49 ]). While some experimental results exist, e.g., [ 43 ], theoretical results are largely missing.

Opportunities for cross-fertilization. Although to a di erent extent, both PC and SPLE do not fully cover questions related to the complexity of the automated tasks they support for di erent classes of con guration problems. To follow up on RQ1 and RQ3, we propose these new questions that study their complexities: RQ5 What is the complexity of automated tasks for relevant classes of con guration problems? RQ6 What reasoning frameworks can be used to build scalable tools for each class of con guration problems? 2.4

Life cycle coverage

SPLE su ers from a certain lack of homogeneity across the modelling artefacts used throughout the engineering life cycle. From requirements engineering down to code generation, a myriad of alternative techniques exist which are used and combined di erently depending on the application domain and project context. Therefore, there is no standard view on how they should be integrated. As for PC, con guration tasks can range from bill-of-material con guration over cement factory design to t-shirt customization. These tasks call for very di erent methods and techniques whose applications have been insu ciently studied. Additionally, the creation of feedback loops from productive use back to variability design decisions is rather explored in the more business- or management-centric literature without transfer to PC.

Con gurator engineering is a more mature discipline in PC than in SPLE, aiming at the co-design of the con gurator and the con gurable artefact. According to Hvam et al. [ 30 ], the creation, implementation and operation of a con gurator is a seven-phase procedure. The rst phase identi es the product speci cation process, used for analyzing customer needs, creating a customized product, and prescribing other related activities, such as purchasing, delivery, servicing, and recycling. The speci cation process also de nes the con guration system that supports the activities composing it. The second phase deals with the de nition of the product portfolio. Phases three to six deal with the modelling and implementation of the con guration system. The seventh phase focuses on maintenance.

Finally, the commercial side of con guration is also important. PC has to deal typically with sales, consumer goods, and engineers, wheras SPLE is more geared towards software engineers and other technical experts. Although stakeholder pro les vary from one case to the other, some con guration tasks overlap and techniques could be shared.

Opportunities for cross-fertilization. To better pinpoint overlaps, we split the problem into three questions:

RQ7 What are the con guration tasks? RQ8 How is a con gurable product engineered? RQ9 How is a con gurator engineered?

2.5

Knowledge evolution

The main concern of the software con guration management (CM) discipline is controlling and tracking the evolution of products in response to changes. To do so, it introduces the concept of versions that represent instances of products and its parts over time. In CM, there are two main types of versions [ 14 ]: revisions and variants. Revisions are versions that supersede other versions due to bug xes or addition of new functionalities. Variants are versions intended to coexist through time to satisfy di erent user or platform needs. Variants are well known in the PC and SPLE elds. However, the management of revisions and the interaction of both is still a weakness of PC and SPLE, especially when the product and its parts evolve frequently. The need to deploy change management techniques in SPLE is recognized [ 13, 47 ], and some researchers have started working in this direction (e.g. [ 2, 57 ]). Although promising, these results are still incomplete, and need to be extended and consolidated.

Problems related to the evolution of the con guration knowledge and system (e.g. knowledge base, database, and product instances) are also known in PC [ 21 ]. PC research has addressed some of these evolution-related aspects in the context of recon guration problems (e.g. [ 55, 24 ]), which consist in changing an already existing or deployed con guration to accommodate new or changed customer requirements or constraints in the knowledge base. Mannisto et al. [ 39 ] discuss the issue of the evolution of con guration knowledge and instances, proposing a framework to address it. The key idea is to accept the independence of these evolutions, capture the evolution in the models, and then do recon guration. Problems similar to recon guration have been addressed in the software domain: given a component-based software installation (e.g. Linux, Eclipse), the component dependencies and an (un-)install request, compute a best new installation [ 1 ].

Another practical challenge both in PC and SPLE is the constantly growing number of components that can be part of a con guration, be they semi-conductors, switches, or software plug-ins. The corresponding knowledge bases soon become hard to manage because they describe how older components have to be replaced by newer ones or which component versions are compatible.

In CM, some have tried to provide a uni ed model for software CM and product data management (e.g. [ 20, 16 ]). Those models stop at the conceptual level without providing operational solutions, however.

Opportunities for cross-fertilization. Since the 1970s, research in CM focused on change management. Mature solutions are now available and could be applicable to PC. Furthermore, researchers in SPLE and PC could join forces to develop scalable techniques to address the explosion of the number of components and their evolution. Those results could then be contributed back to CM. The resulting questions are: RQ10 How can CM techniques be applied to PC and SPLE? RQ11 How to scale up with growing revision knowledge?

Conclusion 3

Research Roadmap

The rst step of our project was the composition of an heterogeneous panel of experts from the di erent communities and the creation of a knowledge exchange portal. Once populated with our initial results, our intention is to open this shared portal to a wider community and invite collaborations. Our research roadmap has ve phases. 1. Literature survey. The rst phase focuses on a literature survey that should answer RQ1-9. The part of the survey related to RQ1-4 is already underway. The body of knowledge gathered during this initial phase will be the foundation upon which the panel will start its uni cation endeavour. 2. Domain understanding and classi cation. The second phase paves the road toward a uni ed theory of con guration. Its objective is to analyze the material collected in the rst phase, to classify the application domains, study their di erences and commonalities, and to identify the possible bridges between these domains. 3. Uni ed theory de nition. The foundation for this theory will be a mathematical model of the classes of conguration problems and their properties. These classes of con guration problems will be characterized by the expressiveness needed to solve the problems. Analogous to the classi cation of description logics [ 6 ], this will enable the study of the theoretical complexity of the associated computational problems. Problem frames [ 31 ] could be used as the macro-structure for this classi cation. 4. Uni ed theory operationalization. Upon this de nition, we will build two layers: modelling languages and reasoning techniques. In the modelling layer, we will rst sort existing languages according to the con guration problems they address. We will then work toward their uni cation, possibly by mapping into a common core language. The reasoning layer will gather the con guration tasks (e.g., consistency check, repair, and completion) identi ed in the previous phases. For each task and a class of con guration problems captured by a language, we will study alternative reasoning techniques and assess their applicability (see next phase). Finally, we will investigate how version management techniques from CM can be adapted to support con guration evolution. Based on these elements, we will answer RQ6, 10 and 11. 5. Uni ed theory validation. Con guration can be applied in a myriad of application domains to support many di erent usage scenarios. Each situation will need its own benchmarks and analyses. The objective of the panel will be to validate the results of the theory operationalization on a few industry-size models. In particular, it will seek to better understand the respective merits and limitations of the various reasoning techniques. Benchmarks will be needed to assess their applicability and tractability on various classes of problems. This pilot validation will be a rst step in setting up a framework in which parallel e orts of the community could commence.

This roadmap is not intended to be executed in a waterfall fashion: we expect several iterations through phases 2-5. Con guration, both of software and other types of products, continues to be a timely business strategy as customers consistently strive for a ordable tailor-made products. Yet, research in product and software con guration progresses on di erent and rarely intersecting paths. This paper (1) motivated the need for bridging the current gap between these two domains, and (2) presented a roadmap to build such a bridge and set cross-fertilization in motion.

Our initial observations show that the contribution of the research in product con guration to software product con guration is rather glaring. The inverse is, however, less obvious. As possible contributions, we see methodological aspects as well as modelling techniques. Once laid upon more formal foundations, some of these models could further improve product con guration.

Finally, the evolution problem is still under-explored in both software and product con guration. They both have a lot to gain from the techniques promoted in con guration management. Conversely, the formal treatment of con guration problems and automated reasoning could enhance existing work in con guration management.

References

[1] P. Abate , R. Di Cosmo , R. Treinen , and S. Zacchiroli , ` Dependency solving: a separate concern in component evolution management' , Systems and Software , ( 2012 ). To appear.

[2] M. Anastasopoulos , D. Muthig , T. H. B. de Oliveira , E. S. Almeida , and S. R. de Lemos Meira, ` Evolving a software product line reuse infrastructure: A con guration management solution' , in Proc. VaMoS'09 , Sevilla , ( 2009 ).

[3] H. R. Andersen , T. Hadzic , and D. Pisinger , ` Interactive cost con guration over decision diagrams' , Arti cial Intelligence Research (JAIR) , 37 , 99{ 139 , ( 2010 ).

[4] M. Aschinger , C. Drescher , and H. Vollmer , ` LoCo - A Logic for Con guration Problems' , in Proceedings of the 20th European Conference on Arti cial Intelligence (ECAI) , Montpellier, France, ( 2012 ).

[5] T. Asikainen , T. Soininen , and T. Mannisto, ` A Koala-based approach for modelling and deploying con gurable software product families' , in Porc PLE'03 , Springer LNCS 3014, pp. 225 { 249 , ( 2003 ).

[6] The Description Logic Handbook: Theory , Implementation, and Applications, eds., F. Baader , D. Calvanese , D. L. McGuinness , D. Nardi , and P. F. Patel-Schneider , Cambridge University Press, 2003 .

[7] E. Bagheri , T. Di Noia , A. Ragone , and D. Gasevic , ` Conguring software product line feature models based on stakeholders' soft and hard requirements' , in SPLC'10 , pp. 16 { 31 , ( 2010 ).

[8] K. Bak , K. Czarnecki , and Andrzej W., ` Feature and metamodels in clafer: Mixed, specialized , and coupled', in Proc. SLE'10 , pp. 102 { 122 , Eindhoven , The Netherlands, ( 2010 ). Springer-Verlag.

[9] D. Batory , ` Feature models, grammars, and propositional formulas' , in SPLC'05 , pp. 7 { 20 , Rennes , France, ( 2005 ).

[10] D. Benavides , S. Segura , and A. Ruiz-Cortes , ` Automated analysis of feature models 20 years later: a literature review' , Information Systems , 35 ( 6 ), 615 { 636 , ( 2010 ).

[11] D. Benavides , P. Trinidad , and Ruiz-Cortez A ., `Automated reasoning on feature models' , in Proc. CAiSE'05 , pp. 491 { 503 , Porto , Portugal, ( 2005 ). Springer.

[12] M. Buchheit , R. Klein , and W. Nutt, ` Constructive Problem Solving: A Model Construction Approach towards Con guration' , Technical Report TM-95-01 , DFKI, ( 1995 ).

[13] P. Clements and L. Northrop , Software Product Lines: Practices and Patterns , Addison-Wesley , 2001 .

[14] R. Conradi and B. Westfechtel , ` Version models for software con guration management' , ACM Computing Surveys , 30 , 232{ 282 , ( June 1998 ).

[15] S. A. Cook , ` The complexity of theorem-proving procedures' , in Proceedings of the 3rd Annual ACM Symposium on Theory of Computing , ( 1971 ).

[16] I. Crnkovic , U. Asklund , and A. P. Dahlqvist , Implementing and integrating product data management and software conguration management , Artech House Publishers, 2003 .

[17] K. Czarnecki , P. Grunbacher , R. Rabiser , K. Schmid , and A. Wasowski , ` Cool features and tough decisions: Two decades of variability modeling' , in Proc. VaMoS'12 , Leipzig, Germany, ( 2012 ). ACM Press.

[18] K. Czarnecki , S. Helsen , and U. W. Eisenecker, ` Staged conguration through specialization and multi-level con guration of feature models' , Software Process: Improvement and Practice , 10 ( 2 ), 143 { 169 , ( 2005 ).

[19] E. Dantsin , T. Eiter , G. Gottlob, and A. Voronkov , ` Complexity and expressive power of logic programming' , ACM Computing Surveys , 33 ( 3 ), 374 { 425 , ( 2001 ).

[20] J. Estublier , J.-M. Favre , and P. Morat , `Toward scm / pdm integration?', in Proc. SCM'98 , pp. 75 { 94 , London, UK, UK , ( 1998 ). Springer-Verlag.

[21] A. Falkner and A. Haselb ock, `Challenges of knowledge evolution in practice' , in ECAI 2010 IKBET Wks , pp. 1 { 5 , ( 2010 ).

[22] A. Felfernig , G. Friedrich, and D. Jannach , ` UML as domain speci c language for the construction of knowledge-based conguration systems' , in Proc. SEKE 99 , pp. 337 { 345 , Kaiserslautern , Germany, ( 1999 ).

[23] A. Felfernig , G. Friedrich , D. Jannach , and M. Stumptner , ` Consistency-based diagnosis of con guration knowledge bases' , Arti cial Intelligence , 152 , 213{ 234 , ( 2004 ).

[24] G. Friedrich , A. Ryabokon , A. Falkner , A . Haselbock, G. Schenner, and H. Schreiner , ` (Re)con guration based on model generation' , in Proc. LoCoCo Workshop , EPTCS, pp. 26 { 35 , ( 2011 ).

[25] H. Gomaa and M. Eonsuk Shin , ` Multiple-view modelling and meta-modelling of software product lines' , IET Software , 2 ( 2 ), 94 { 122 , ( 2008 ).

[26] G. Gottlob , G. Greco, and T. Mancini, ` Conditional Constraint Satisfaction: Logical Foundations and Complexity' , in Proceedings of the 20th International Joint Conference on Arti cial Intelligence (IJCAI) , Hyderabad, India, ( 2007 ).

[27] A. Gu nter and C. Kuhn, `Knowledge-based con guration: Survey and future directions' , in Proc. XPS'99 , pp. 47 { 66 , London, ( 1999 ).

[28] L. Hotz , K. Wolter , and T. Krebs , Con guration in Industrial Product Families: The ConIPF Methodology , IOS Press, Inc., 2006 .

[29] A. Hubaux , A. Classen , and P. Heymans , ` Formal modelling of feature con guration work ow' , in Proc. SPLC'09 , pp. 221 { 230 , San Francisco , ( 2009 ).

[30] L. Hvam , N. Henrik Mortensen , and J. Riis , Product Customization, Springer-Verlag Berlin Heidelberg, 2008 .

[31] M. Jackson , Problem frames: analyzing and structuring software development problems , Addison-Wesley, 2001 .

[32] D. Jannach and M. Zanker , ` Modeling and solving distributed con guration problems: A CSP-based approach' , IEEE TKDE, http://doi.ieeecomputersociety. org/10 .1109/TKDE. 2011 . 236 .

[33] M. Janota , ` Do SAT solvers make good con gurators?' , in Proc. ASPL'08 , pp. 191 { 195 , Limerick , Ireland, ( 2008 ).

[34] U. Junker , Handbook of Constraint Programming, chapter Con guration , 837 { 873 , Elsevier , 2006 .

[35] U. Junker and D. Mailharro , ` The logic of ILOG (J)Con gurator: Combining constraint programming with a description logic' , in Proc. IJCAI-03 Con guration Workshop , ( 2003 ).

[36] U. Junker and D. Mailharro , ` Preference programming: Advanced problem solving for con guration' , AIEDAM , 17 ( 1 ), 13 { 29 , ( 2003 ).

[37] K. Kang , S. G. Cohen , J. A. Hess , W. E. Novak , and A. S. Peterson , ` Feature-Oriented Domain Analysis (FODA) Feasibility Study' , Technical report, SEI , CMU , ( 1990 ).

[38] A. K. Mackworth , ` Consistency in networks of relations' , Arti cial Intelligence , 8 , 99{ 118 , ( 1977 ).

[39] T. Ma nnisto, A Conceptual Modelling Approach to Product Families and Their Evolution , Ph.D. dissertation , Helsinki University of Technology, Finland, 2000 .

[40] D. L. McGuinness and J. R. Wright , ` Conceptual modelling for con guration: A description logic-based approach' , Artif. Intell. Eng. Des. Anal. Manuf ., 12 ( 4 ), 333 { 344 , ( 1998 ).

[41] M. D. McIlroy , ` Mass produced software components' , in Proc. Software Engineering Concepts and Techniques , pp. 138 { 150 . NATO Science Committee, ( 1968 ).

[42] M. Mendonca , E cient Reasoning Techniques for Large Scale Feature Models , Ph.D. dissertation , U Waterloo, 2009 .

[43] M. Mendonca , A. Wasowski , and K. Czarnecki , ` SAT-based analysis of feature models is easy' , in Proc. SPLC'09 , pp. 231 { 240 , San Francisco , ( 2009 ). Carnegie Mellon University.

[44] R. Michel , A. Classen , A. Hubaux , and Q. Boucher , ` A formal semantics for feature cardinalities in feature diagrams' , in Proc. Wks . VaMoS'11 , pp. 82 { 89 , Namur , BE , ( 2011 ).

[45] S. Mittal and B. Falkenhainer , ` Dynamic constraint satisfaction problems' , in AAAI'90 , pp. 25 { 32 , Boston, ( 1990 ).

[46] M. Pasanen , Warnings and Pre-selection Packages in a Weight Constraint Rule Based Con gurator , Master's thesis , Helsinki University of Technology, Department of Computer Science and Engineering, Finland, 2003 .

[47] K. Pohl , G. Bockle, and F. J. van der Linden , Software Product Line Engineering: Foundations, Principles and Techniques, Springer, 2005 .

[48] D. Sabin and E. C. Freuder , ` Con guration as Composite Constraint Satisfaction' , in Proceedings of the Arti cial Intelligence and Manufacturing Research Planning Workshop (AIMRP) , Albuquerque, New Mexico, ( 1996 ).

[49] P-Y. Schobbens , P. Heymans , J-C. Trigaux , and Yves Bontemps, ` Generic semantics of feature diagrams', Comput . Netw., 51 ( 2 ), 456 { 479 , ( 2007 ).

[50] P. Simons , I. Niemela, and T . Soininen, ` Extending and implementing the stable model semantics' , Arti cial Intelligence , 138 ( 1 {2), 181 { 234 , ( 2002 ).

[51] C. Sinz , A. Kaiser , and W. Kuchlin, ` SAT-based consistency checking of automotive electronic product data' , in ECAI Workshop , ( 2000 ).

[52] T. Soininen , An Approach to Knowledge Representation and Reasoning for Product Con guration Tasks , Ph.D. dissertation , 2000 .

[53] T. Soininen , J. Tiihonen , T. Mannisto, and R. Sulonen , ` Towards a general ontology of con guration' , AIEDAM , 12 , 357{ 372 , ( 1998 ).

[54] M. Stumptner , A . Haselbock, and G. Friedrich, ` Generative Constraint-based Con guration of Large Technical Systems' , AI EDAM , 12 ( 4 ), 307 { 320 , ( 1998 ).

[55] M. Stumptner and F. Wotawa , ` Model-based recon guration' , in Proc. AID'98 , pp. 45 { 64 , ( 1998 ).

[56] E. Thorstensen , `Capturing Con guration', in Doctoral Program at the 16th International Conference on Principles and Practice of Constraint Programming (CP) , St . Andrews, Scotland, ( 2010 ).

[57] T. Thum , D. Batory , and C. Kastner , ` Reasoning about edits to feature models' , in Proc. ICSE'09 , pp. 254 { 264 , Washington, DC, USA, ( 2009 ). IEEE Computer Society.

[58] T. T. Tun , Q. Boucher , A. Classen , A. Hubaux , and P. Heymans , ` Relating requirements and feature con gurations: A systematic approach' , in Proc. SPLC'09 , pp. 201 { 210 , San Francisco, CA, USA, ( 2009 ). ACM Press.

[59] Y. Xiong , A. Hubaux , and K. Czarnecki , ` Generating range xes for software con guration' , in Proc. ICSE'12 , Zurich , Switzerland, ( 2012 ). IEEE Computer Society.

[60] T. Ziadi , L. Helouet , and J. -M. Jezequel , ` Towards a UML pro le for software product lines' , in Software Product-Family Engineering , Springer LNCS 3014, 129 { 139 , ( 2004 ).