Top

Software and Systems Modeling

Published in:

11-10-2022 | Regular Paper

The complexities of the satisfiability checking problems of feature diagram sublanguages

Author: Oliver Kautz

Published in: Software and Systems Modeling | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It is well-known that the satisfiability problem of feature diagrams (FDs) is computationally hard. This paper examines the complexities of the satisfiability problems of sixteen FD sublanguages, i.e., languages that only permit a subset of the syntactic modeling elements of general FDs. Previous work neglected a detailed examination of the complexities of the satisfiability problems of FD sublanguages, although results in this area could lead to the development of efficient satisfiability checking procedures for the FDs of specific sublanguages. This paper contributes to fill this gap by analyzing the complexities of the satisfiability problems of sixteen FD sublanguages that differ in whether they allow or-groups, xor-groups, excludes constraints, and requires constraints. The results of this paper show that the satisfiability problem is NP-complete for eight of these sublanguages, is solvable in linear time for two of these sublanguages, and is trivial for the remaining six sublanguages in the sense that every FD of these sublanguages is satisfiable. The results are extended to feature model sublanguages with complex cross-tree constraints by extending FD sublanguages that have satisfiability problems, which are solvable in polynomial time. The feature model sublanguages also have satisfiability problems that are solvable in polynomial time.

previous article On the use of domain knowledge for process model repair

next article Real-time collaborative multi-level modeling by conflict-free replicated data types

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Acher, M., Heymans, P., Collet, P., Quinton, C., Lahire, P., Merle, P.: Feature Model Differences. In: Ralyté, J., Franch, X., Brinkkemper, S., Wrycza, S. (eds.) Advanced Information Systems Engineering, pp. 629–645. Springer, Berlin (2012)

Apel, S., Kästner, C.: An overview of feature-oriented software development. J. Obj. Technol. 8(5), 49–84 (2009)CrossRef

Artale, A., Calvanese, D., Ibáñez-García, Y. A.: Full satisfiability of UML class diagrams. In: 29th International Conference on Conceptual Modeling Conceptual Modeling—ER 2010, pp. 317–331. Springer (2010)

Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 66 (1979)MathSciNetCrossRefMATH

Balaban, M., Maraee, A.: Finite satisfiability of UML class diagrams with constrained class hierarchy. ACM Trans. Softw. Eng. Methodol. 22(3), 66 (2013)CrossRef

Batory, D.: Feature models, grammars, and propositional formulas. In: 9th International Conference Software Product Lines, pp. 7–20. Springer (2005)

Benavides, D., Segura, S., Ruiz-Cortés, A.: Automated analysis of feature models 20 years later: a literature review. Inf. Syst. 35(6), 615–636 (2010)CrossRef

Bontemps, Y., Heymans, P., Schobbens, P., Trigaux, J.: Generic semantics of feature diagrams variants. In: Proceedings of 8th International Conference on Feature Interactions in Telecommunications and Software Systems (ICFI). IOS Press (2005)

Butting, A., Kautz, O., Rumpe, B., Wortmann, A.: Semantic differencing for message-driven component & connector architectures. In: IEEE International Conference on Software Architecture (ICSA), pp. 145–154. IEEE (2017)

10.

Butting, A., Kautz, O., Rumpe, B., Wortmann, A.: Continuously analyzing finite, message-driven, time-synchronous component & connector systems during architecture evolution. J. Syst. Softw. 149, 437–461 (2019)CrossRef

11.

Calvanese, D., Lenzerini, M.: On the interaction between ISA and cardinality constraints. In: Proceedings of 1994 IEEE 10th International Conference on Data Engineering, pp. 204–213. IEEE (1994)

12.

Calvanese, D., Lenzerini, M., Nardi, D.: Unifying class-based representation formalisms. J. Artif. Intell. Res. 11, 199–240 (1999)MathSciNetCrossRefMATH

13.

Clements, P., Northrop, L.: Software Product Lines: Practices and Patterns. Addison-Wesley (2007)

14.

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM (1971)

15.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd Ed. MIT Press (2001)

16.

Czarnecki, K., Wąsowski, A.: Feature diagrams and logics: there and back again. In: 11th International Conference on Software Product Lines, pp. 23–34. IEEE (2007)

17.

Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Program. 1(3), 267–284 (1984)MathSciNetCrossRefMATH

18.

Drave, I., Eikermann, R., Kautz, O., Rumpe, B.: Semantic differencing of statecharts for object-oriented systems. In: Hammoudi, S., Pires, L.F., Selić, B. (Eds.) Proceedings of the 7th International Conference on Model-Driven Engineering and Software Development, pp. 272–280. SciTePress (2019)

19.

Drave, I., Kautz, O., Michael, J., Rumpe, B.: Semantic evolution analysis of feature models. In: Proceedings of the 23rd International Systems and Software Product Line Conference, pp. 245–255. ACM (2019)

20.

Durán, A., Benavides, D., Segura, S., Trinidad, P., Cortés, A.R.: FLAME: a formal framework for the automated analysis of software product lines validated by automated specification testing. Softw. Syst. Model. 16(4), 1049–1082 (2017)CrossRef

21.

France, R.B., Rumpe, B.: Model-driven development of complex software: a research roadmap. In: Future of Software Engineering (FOSE ’07), pp. 37–54. IEEE (2007)

22.

Galindo, J.A., Acher, M., Tirado, J.M., Vidal, C., Baudry, B., Benavides, D.: Exploiting the enumeration of all feature model configurations: a new perspective with distributed computing. In: Proceedings of the 20th International Systems and Software Product Line Conference, pp. 74–78. Association for Computing Machinery (2016)

23.

Heymans, P., Schobbens, P., Trigaux, J., Bontemps, Y., Matulevičius, R., Classen, A.: Evaluating formal properties of feature diagram languages. IET Softw. 2(3), 281–302 (2008)CrossRef

24.

Johansen, M.F., Haugen, O., Fleurey, F.: Properties of realistic feature models make combinatorial testing of product lines feasible. In: Proceedings of the 14th International Conference on Model Driven Engineering Languages and Systems, pp. 638–652. Springer (2011)

25.

Kang, K.C., Cohen, S.G., Hess, J.A., Novak, W.E., Peterson, A.S.: Feature-Oriented Domain Analysis (FODA) Feasibility Study. Technical Report CMU/SEI-90-TR-021, Software Engineering Institute, Carnegie Mellon University (1990)

26.

Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

27.

Kautz, O.: Model Analyses Based on Semantic Differencing and Automatic Model Repair. Aachener Informatik-Berichte, Software Engineering, Band 46. Shaker Verlag (2021)

28.

Kautz, O., Maoz, S., Ringert, J.O., Rumpe, B.: CD2Alloy: A Translation of Class Diagrams to Alloy. Technical Report AIB-2017-06, RWTH Aachen University (2017)

29.

Kautz, O., Rumpe, B.: Semantic differencing of activity diagrams by a translation into finite automata. In: Hebig, R., Berger, T. (Eds.), Proceedings of MODELS 2018 Workshops: ModComp, MRT, OCL, FlexMDE, EXE, COMMitMDE, MDETools, GEMOC, MORSE, MDE4IoT, MDEbug, MoDeVVa, ME, MULTI, HuFaMo, AMMoRe, PAINS co-located with ACM/IEEE 21st International Conference on Model Driven Engineering Languages and Systems (MODELS 2018). CEUR (2018)

30.

Kroening, D., Strichman, O.: Decision Procedures: An Algorithmic Point of View. Springer, Berlin (2008)MATH

31.

Liang, J.H., Ganesh, V., Czarnecki, K., Raman, V.: SAT-based analysis of large real-world feature models is easy. In: Proceedings of the 19th International Conference on Software Product Line, pp. 91–100. ACM (2015)

32.

Maoz, S., Ringert, J.O.: A framework for relating syntactic and semantic model differences. In: ACM/IEEE 18th International Conference on Model Driven Engineering Languages and Systems (MODELS), pp. 24–33. IEEE (2015)

33.

Maoz, S., Ringert, J.O., Rumpe, B.: ADDiff: semantic differencing for activity diagrams. In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, pp. 179–189. ACM (2011)

34.

Maoz, S., Ringert, J.O., Rumpe, B.: CDDiff: semantic differencing for class diagrams. In: Mezini, M. (ed.) ECOOP 2011—Object-Oriented Programming, pp. 230–254. Springer, Berlin (2011)CrossRef

35.

Mendonca, M., Wąsowski, A., Czarnecki, K.: SAT-based analysis of feature models is easy. In: Proceedings of the 13th International Software Product Line Conference, pp. 231–240. Carnegie Mellon University (2009)

36.

Mendonça, M.: Efficient Reasoning Techniques for Large Scale Feature Models. PhD thesis, School of Computer Science, University of Waterloo (2009)

37.

Pohl, K., Böckle, G., van der Linden, F.: Software Product Line Engineering: Foundations. Springer, Principles and Techniques (2005)

38.

Rumpe, B.: Modeling with UML: Language, Concepts, Methods. Springer (2016)

39.

Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216–226. ACM (1978)

40.

Schobbens, P.Y., Heymans, P., Trigaux, J.-C., Bontemps, Y.: Feature diagrams: a survey and a formal semantics. In: Glinz, M., Lutz, R. (Eds.) 14th IEEE International Requirements Engineering Conference (RE’06), pp. 139–148. IEEE (2006)

41.

Schobbens, P.-Y., Heymans, P., Trigaux, J.-C., Bontemps, Y.: Generic semantics of feature diagrams. Comput. Netw. 51(2), 456–479 (2007)CrossRefMATH

42.

Tzoref-Brill, R., Maoz, S.: Syntactic and semantic differencing for combinatorial models of test designs. In: 2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE), pp. 621–631. IEEE (2017)

Title: The complexities of the satisfiability checking problems of feature diagram sublanguages
Author: Oliver Kautz
Publication date: 11-10-2022
Publisher: Springer Berlin Heidelberg
Published in: Software and Systems Modeling / Issue 4/2023
Print ISSN: 1619-1366
Electronic ISSN: 1619-1374
DOI: https://doi.org/10.1007/s10270-022-01048-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2023

On the use of domain knowledge for process model repair

From low-level programming to full-fledged industrial model-based development: the story of the Rubus Component Model

Visual query languages to design complex queries: a systematic literature review

Real-time collaborative multi-level modeling by conflict-free replicated data types

CalcGraph: taming the high costs of deep learning using models

A generic framework for representing and analyzing model concurrency

Premium Partner