Elimination of Constraints from Feature Trees

P.M. van den Broek; I. Galvao; J.A.R. Noppen

Elimination of Constraints from Feature Trees

P.M. van den Broek, I. Galvao, J.A.R. Noppen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

84 Downloads (Pure)

Abstract

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.

Original language	Undefined
Title of host publication	Proceedings of the 12th International Software Product Line Conference
Place of Publication	Limerick, Ireland
Publisher	Lero International Science Centre, University of Limerick, Ireland
Pages	227-232
Number of pages	6
ISBN (Print)	978-1-905952-06-9
Publication status	Published - 2008
Event	12th International Software Product Line Conference, SPLC 2008 - Limerick, Ireland Duration: 8 Sept 2008 → 12 Sept 2008 Conference number: 12

Publication series

Name
Publisher	Lero International Science Centre, University of Limerick, Ireland
Number	Supplement

Workshop

Workshop	12th International Software Product Line Conference, SPLC 2008
Abbreviated title	SPLC
Country/Territory	Ireland
City	Limerick
Period	8/09/08 → 12/09/08

Keywords

EWI-13457
IR-64986
METIS-251190
SE-Q: Quality Modelling and Verification

Access to Document

http://www.isa.us.es/aspl08/?download=W5_P07_VanDenBroek_Elimination_of_Constraints_from_Feature_Trees.pdf

Cite this

van den Broek, P. M., Galvao, I., & Noppen, J. A. R. (2008). Elimination of Constraints from Feature Trees. In Proceedings of the 12th International Software Product Line Conference (pp. 227-232). Lero International Science Centre, University of Limerick, Ireland. http://www.isa.us.es/aspl08/?download=W5_P07_VanDenBroek_Elimination_of_Constraints_from_Feature_Trees.pdf

@inproceedings{719640b7a2734636b6d094a221e25ef6,

title = "Elimination of Constraints from Feature Trees",

abstract = "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.",

keywords = "EWI-13457, IR-64986, METIS-251190, SE-Q: Quality Modelling and Verification",

author = "{van den Broek}, P.M. and I. Galvao and J.A.R. Noppen",

year = "2008",

language = "Undefined",

isbn = "978-1-905952-06-9",

publisher = "Lero International Science Centre, University of Limerick, Ireland",

number = "Supplement",

pages = "227--232",

booktitle = "Proceedings of the 12th International Software Product Line Conference",

note = "12th International Software Product Line Conference, SPLC 2008 ; Conference date: 08-09-2008 Through 12-09-2008",

}

van den Broek, PM, Galvao, I & Noppen, JAR 2008, Elimination of Constraints from Feature Trees. in Proceedings of the 12th International Software Product Line Conference. Lero International Science Centre, University of Limerick, Ireland, Limerick, Ireland, pp. 227-232, 12th International Software Product Line Conference, SPLC 2008, Limerick, Ireland, 8/09/08. <http://www.isa.us.es/aspl08/?download=W5_P07_VanDenBroek_Elimination_of_Constraints_from_Feature_Trees.pdf>

Elimination of Constraints from Feature Trees. / van den Broek, P.M.; Galvao, I.; Noppen, J.A.R.
Proceedings of the 12th International Software Product Line Conference. Limerick, Ireland: Lero International Science Centre, University of Limerick, Ireland, 2008. p. 227-232.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Elimination of Constraints from Feature Trees

AU - van den Broek, P.M.

AU - Galvao, I.

AU - Noppen, J.A.R.

N1 - Conference code: 12

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - EWI-13457

KW - IR-64986

KW - METIS-251190

KW - SE-Q: Quality Modelling and Verification

M3 - Conference contribution

SN - 978-1-905952-06-9

SP - 227

EP - 232

BT - Proceedings of the 12th International Software Product Line Conference

PB - Lero International Science Centre, University of Limerick, Ireland

CY - Limerick, Ireland

T2 - 12th International Software Product Line Conference, SPLC 2008

Y2 - 8 September 2008 through 12 September 2008

ER -