{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:27:46Z","timestamp":1790749666143,"version":"4.1.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T00:00:00Z","timestamp":1665446400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T00:00:00Z","timestamp":1665446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Softw Syst Model"],"published-print":{"date-parts":[[2023,8]]},"DOI":"10.1007\/s10270-022-01048-3","type":"journal-article","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T07:03:03Z","timestamp":1665471783000},"page":"1113-1129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The complexities of the satisfiability checking problems of feature diagram sublanguages"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5234-6028","authenticated-orcid":false,"given":"Oliver","family":"Kautz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"1048_CR1","first-page":"629","volume-title":"Advanced Information Systems Engineering","author":"M Acher","year":"2012","unstructured":"Acher, M., Heymans, P., Collet, P., Quinton, C., Lahire, P., Merle, P.: Feature Model Differences. In: Ralyt\u00e9, J., Franch, X., Brinkkemper, S., Wrycza, S. (eds.) Advanced Information Systems Engineering, pp. 629\u2013645. Springer, Berlin (2012)"},{"issue":"5","key":"1048_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.5381\/jot.2009.8.5.c5","volume":"8","author":"S Apel","year":"2009","unstructured":"Apel, S., K\u00e4stner, C.: An overview of feature-oriented software development. J. Obj. Technol. 8(5), 49\u201384 (2009)","journal-title":"J. Obj. Technol."},{"key":"1048_CR3","doi-asserted-by":"crossref","unstructured":"Artale, A., Calvanese, D., Ib\u00e1\u00f1ez-Garc\u00eda, Y. A.: Full satisfiability of UML class diagrams. In: 29th International Conference on Conceptual Modeling Conceptual Modeling\u2014ER 2010, pp. 317\u2013331. Springer (2010)","DOI":"10.1007\/978-3-642-16373-9_23"},{"issue":"3","key":"1048_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"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)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1048_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/2491509.2491518","volume":"22","author":"M Balaban","year":"2013","unstructured":"Balaban, M., Maraee, A.: Finite satisfiability of UML class diagrams with constrained class hierarchy. ACM Trans. Softw. Eng. Methodol. 22(3), 66 (2013)","journal-title":"ACM Trans. Softw. Eng. Methodol."},{"key":"1048_CR6","doi-asserted-by":"crossref","unstructured":"Batory, D.: Feature models, grammars, and propositional formulas. In: 9th International Conference Software Product Lines, pp. 7\u201320. Springer (2005)","DOI":"10.1007\/11554844_3"},{"issue":"6","key":"1048_CR7","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/j.is.2010.01.001","volume":"35","author":"D Benavides","year":"2010","unstructured":"Benavides, D., Segura, S., Ruiz-Cort\u00e9s, A.: Automated analysis of feature models 20 years later: a literature review. Inf. Syst. 35(6), 615\u2013636 (2010)","journal-title":"Inf. Syst."},{"key":"1048_CR8","unstructured":"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)"},{"key":"1048_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013154. IEEE (2017)","DOI":"10.1109\/ICSA.2017.34"},{"key":"1048_CR10","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.jss.2018.12.016","volume":"149","author":"A Butting","year":"2019","unstructured":"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\u2013461 (2019)","journal-title":"J. Syst. Softw."},{"key":"1048_CR11","doi-asserted-by":"crossref","unstructured":"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\u2013213. IEEE (1994)","DOI":"10.1109\/ICDE.1994.283032"},{"key":"1048_CR12","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1613\/jair.548","volume":"11","author":"D Calvanese","year":"1999","unstructured":"Calvanese, D., Lenzerini, M., Nardi, D.: Unifying class-based representation formalisms. J. Artif. Intell. Res. 11, 199\u2013240 (1999)","journal-title":"J. Artif. Intell. Res."},{"key":"1048_CR13","unstructured":"Clements, P., Northrop, L.: Software Product Lines: Practices and Patterns. Addison-Wesley (2007)"},{"key":"1048_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"key":"1048_CR15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd Ed. MIT Press (2001)"},{"key":"1048_CR16","doi-asserted-by":"crossref","unstructured":"Czarnecki, K., W\u0105sowski, A.: Feature diagrams and logics: there and back again. In: 11th International Conference on Software Product Lines, pp. 23\u201334. IEEE (2007)","DOI":"10.1109\/SPLINE.2007.24"},{"issue":"3","key":"1048_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"WF Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Program. 1(3), 267\u2013284 (1984)","journal-title":"J. Logic Program."},{"key":"1048_CR18","doi-asserted-by":"crossref","unstructured":"Drave, I., Eikermann, R., Kautz, O., Rumpe, B.: Semantic differencing of statecharts for object-oriented systems. In: Hammoudi, S., Pires, L.F., Seli\u0107, B. (Eds.) Proceedings of the 7th International Conference on Model-Driven Engineering and Software Development, pp. 272\u2013280. SciTePress (2019)","DOI":"10.5220\/0007351902740282"},{"key":"1048_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013255. ACM (2019)","DOI":"10.1145\/3336294.3336300"},{"issue":"4","key":"1048_CR20","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.1007\/s10270-015-0503-z","volume":"16","author":"A Dur\u00e1n","year":"2017","unstructured":"Dur\u00e1n, A., Benavides, D., Segura, S., Trinidad, P., Cort\u00e9s, 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\u20131082 (2017)","journal-title":"Softw. Syst. Model."},{"key":"1048_CR21","doi-asserted-by":"crossref","unstructured":"France, R.B., Rumpe, B.: Model-driven development of complex software: a research roadmap. In: Future of Software Engineering (FOSE \u201907), pp. 37\u201354. IEEE (2007)","DOI":"10.1109\/FOSE.2007.14"},{"key":"1048_CR22","doi-asserted-by":"crossref","unstructured":"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\u201378. Association for Computing Machinery (2016)","DOI":"10.1145\/2934466.2934478"},{"issue":"3","key":"1048_CR23","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1049\/iet-sen:20070055","volume":"2","author":"P Heymans","year":"2008","unstructured":"Heymans, P., Schobbens, P., Trigaux, J., Bontemps, Y., Matulevi\u010dius, R., Classen, A.: Evaluating formal properties of feature diagram languages. IET Softw. 2(3), 281\u2013302 (2008)","journal-title":"IET Softw."},{"key":"1048_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013652. Springer (2011)","DOI":"10.1007\/978-3-642-24485-8_47"},{"key":"1048_CR25","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.21236\/ADA235785"},{"key":"1048_CR26","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1048_CR27","unstructured":"Kautz, O.: Model Analyses Based on Semantic Differencing and Automatic Model Repair. Aachener Informatik-Berichte, Software Engineering, Band 46. Shaker Verlag (2021)"},{"key":"1048_CR28","unstructured":"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)"},{"key":"1048_CR29","unstructured":"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)"},{"key":"1048_CR30","volume-title":"Decision Procedures: An Algorithmic Point of View","author":"D Kroening","year":"2008","unstructured":"Kroening, D., Strichman, O.: Decision Procedures: An Algorithmic Point of View. Springer, Berlin (2008)"},{"key":"1048_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013100. ACM (2015)","DOI":"10.1145\/2791060.2791070"},{"key":"1048_CR32","doi-asserted-by":"crossref","unstructured":"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\u201333. IEEE (2015)","DOI":"10.1109\/MODELS.2015.7338232"},{"key":"1048_CR33","doi-asserted-by":"crossref","unstructured":"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\u2013189. ACM (2011)","DOI":"10.1145\/2025113.2025140"},{"key":"1048_CR34","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-642-22655-7_12","volume-title":"ECOOP 2011\u2014Object-Oriented Programming","author":"S Maoz","year":"2011","unstructured":"Maoz, S., Ringert, J.O., Rumpe, B.: CDDiff: semantic differencing for class diagrams. In: Mezini, M. (ed.) ECOOP 2011\u2014Object-Oriented Programming, pp. 230\u2013254. Springer, Berlin (2011)"},{"key":"1048_CR35","unstructured":"Mendonca, M., W\u0105sowski, A., Czarnecki, K.: SAT-based analysis of feature models is easy. In: Proceedings of the 13th International Software Product Line Conference, pp. 231\u2013240. Carnegie Mellon University (2009)"},{"key":"1048_CR36","unstructured":"Mendon\u00e7a, M.: Efficient Reasoning Techniques for Large Scale Feature Models. PhD thesis, School of Computer Science, University of Waterloo (2009)"},{"key":"1048_CR37","doi-asserted-by":"crossref","unstructured":"Pohl, K., B\u00f6ckle, G., van der Linden, F.: Software Product Line Engineering: Foundations. Springer, Principles and Techniques (2005)","DOI":"10.1007\/3-540-28901-1"},{"key":"1048_CR38","doi-asserted-by":"crossref","unstructured":"Rumpe, B.: Modeling with UML: Language, Concepts, Methods. Springer (2016)","DOI":"10.1007\/978-3-319-33933-7"},{"key":"1048_CR39","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"1048_CR40","doi-asserted-by":"crossref","unstructured":"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\u201906), pp. 139\u2013148. IEEE (2006)","DOI":"10.1109\/RE.2006.23"},{"issue":"2","key":"1048_CR41","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.comnet.2006.08.008","volume":"51","author":"P-Y Schobbens","year":"2007","unstructured":"Schobbens, P.-Y., Heymans, P., Trigaux, J.-C., Bontemps, Y.: Generic semantics of feature diagrams. Comput. Netw. 51(2), 456\u2013479 (2007)","journal-title":"Comput. Netw."},{"key":"1048_CR42","doi-asserted-by":"crossref","unstructured":"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\u2013631. IEEE (2017)","DOI":"10.1109\/ICSE.2017.63"}],"container-title":["Software and Systems Modeling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10270-022-01048-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10270-022-01048-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10270-022-01048-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T15:02:54Z","timestamp":1728140574000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10270-022-01048-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,11]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["1048"],"URL":"https:\/\/doi.org\/10.1007\/s10270-022-01048-3","relation":{},"ISSN":["1619-1366","1619-1374"],"issn-type":[{"value":"1619-1366","type":"print"},{"value":"1619-1374","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,11]]},"assertion":[{"value":"17 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}