The complexities of the satisfiability checking problems of feature diagram sublanguages.

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. [ABSTRACT FROM AUTHOR]