Outline analysis of complexity

The complexity of the work arises from four major sources: 1) model space construction, 2) label propagation in the ATMS, 3) model space to aDCSP translation, and 4) aDPCSP solution.

$\CALL{generateModelSpace}{\langle O,R\rangle}$ essentially performs a fixed sequence of instructions and produces a small set of nodes and inferences for each match of a model fragment. Therefore, its time and space complexity are linear with respect to the number of possible matches of model fragments. $\CALL{createaDCSP}{\mbox{}}$ extracts certain information from the model space and rewrites it in a different formalism without further manipulations. Therefore, its time and space complexity are linear with respect to the size of the model space.

The label propagation algorithm of an ATMS is known to have an exponential time complexity. However, because the model space is built up incrementally (by $\CALL{generateModelSpace}{\langle O,R\rangle}$) from the root nodes of the ATMS network (i.e. those that correspond to facts and have no antecedents) to the leaf nodes (i.e. those that have have no consequents, other than the nogood node) and because the inconsistencies are added at the end, this complexity only increases exponentially with the depth of the network and the number of participants and relations in individual model fragments, rather than with the size of the model space. This fact significantly limits the complexity impact of label propagation. Firstly, the depth of the ATMS network is restricted by the domain. In many conventional compositional modellers, where model fragments are direct translations from scenario components to scenario model equations, this depth would be only one. Empirically, constructing the model space for sophisticated eco-systems, the depth of a model space never exceeded 8. Secondly, the size of the individual model fragments does not change significantly with the size of the knowledge base.

The fourth and final source of complexity is driven by the fact that the constraint satisfaction algorithm must determine a consistent combination of assumptions in the model space. The space of attribute value assignments increases exponentially with the size of the number of assumptions and hence, with the model space. Thus, the overall complexity of the present approach is largely dominated by the constraint satisfaction algorithm employed.

If the user does not specify any preference, the CSP is an aDCSP. Recently, a number of efficient methods have been devised for solving aDCSPs as presented by Minton et al. [30]; Mittal and Falkenhainer [31]; and Verfaillie and Schiex [42]. This helps minimise the overhead incurred for compositional modelling.

With preferences, the CSP becomes an aDPCSP. As argued in section 2, this presents a new problem that has not yet been studied in detail. In this work, an A* algorithm has been proposed to implement the CSP solution method. This approach is known to be the most efficient in terms of the proportion of the search space the algorithm needs to explore before finding an optimal solution, when compared to other search methods that are based on the same heuristic [13]. A disadvantage is that it incurs an exponential space complexity. As explained by Miguel and Shen [28,29]; and Tsang [41], a wide range of alternative solution techniques exist for ordinary CSPs and many of these could also be extended to solve aDPCSPs. A detailed examination of these techniques is a topic of future research.