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

80 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	English
Title of host publication	Proceedings of the 12th International Software Product Line Conference, SPLC 2008
Subtitle of host publication	Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008
Editors	Steffen Thiel, Klaus Pohl
Place of Publication	Limerick, Ireland
Publisher	Lero International Science Centre, University of Limerick, Ireland
Pages	227-232
Number of pages	6
Volume	2: Workshops
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

SE-Q: Quality Modelling and Verification

Access to Document

ArticleFinal published version, 239 KB

Cite this

van den Broek, P. M., Galvao, I., & Noppen, J. A. R. (2008). Elimination of Constraints from Feature Trees. In S. Thiel, & K. Pohl (Eds.), Proceedings of the 12th International Software Product Line Conference, SPLC 2008: Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008 (Vol. 2: Workshops, pp. 227-232). Lero International Science Centre, University of Limerick, Ireland.

van den Broek, P.M. ; Galvao, I. ; Noppen, J.A.R. / Elimination of Constraints from Feature Trees. Proceedings of the 12th International Software Product Line Conference, SPLC 2008: Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008. editor / Steffen Thiel ; Klaus Pohl. Vol. 2: Workshops Limerick, Ireland : Lero International Science Centre, University of Limerick, Ireland, 2008. pp. 227-232

@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 = "SE-Q: Quality Modelling and Verification",

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

year = "2008",

language = "English",

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

volume = "2: Workshops",

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

number = "Supplement",

pages = "227--232",

editor = "Steffen Thiel and Klaus Pohl",

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

note = "12th International Software Product Line Conference, SPLC 2008, SPLC ; 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 S Thiel & K Pohl (eds), Proceedings of the 12th International Software Product Line Conference, SPLC 2008: Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008. vol. 2: Workshops, 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.

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, SPLC 2008: Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008. ed. / Steffen Thiel; Klaus Pohl. Vol. 2: Workshops 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 - SE-Q: Quality Modelling and Verification

M3 - Conference contribution

SN - 978-1-905952-06-9

VL - 2: Workshops

SP - 227

EP - 232

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

A2 - Thiel, Steffen

A2 - Pohl, Klaus

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 -

van den Broek PM, Galvao I, Noppen JAR. Elimination of Constraints from Feature Trees. In Thiel S, Pohl K, editors, Proceedings of the 12th International Software Product Line Conference, SPLC 2008: Lero Int. Science Centre, University of Limerick, Limerick, Ireland, September 8-12, 2008. Vol. 2: Workshops. Limerick, Ireland: Lero International Science Centre, University of Limerick, Ireland. 2008. p. 227-232

Elimination of Constraints from Feature Trees

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this