# DynamicHS:
Streamlining Reiter’s Hitting-Set Tree for Sequential Diagnosis††thanks:
Earlier and significantly shorter versions (?, ?, ?) of this paper were
accepted and presented at the _31st International Workshop on Principles of
Diagnosis (DX’20)_ , the _Symposium on Combinatorial Search (SoCS’20)_ , as
well as at the _24th European Conference on Artificial Intelligence
(ECAI’20)_. The present version extends these earlier versions in various
regards, providing i.a. a more detailed discussion of the proposed algorithm,
a correctness proof, additional examples, a more comprehensive treatment of
related works, and a substantially augmented evaluation section.

Patrick Rodler<EMAIL_ADDRESS>
Universitätsstr. 65-67, 9020 Klagenfurt, Austria

###### Abstract

Given a system that does not work as expected, Sequential Diagnosis (SD) aims
at suggesting a series of system measurements to isolate the true explanation
for the system’s misbehavior from a potentially exponential set of possible
explanations. To reason about the best next measurement, SD methods usually
require a sample of possible fault explanations at each step of the iterative
diagnostic process. The computation of this sample can be accomplished by
various diagnostic search algorithms. Among those, Reiter’s HS-Tree is one of
the most popular due its desirable properties and general applicability.
Usually, HS-Tree is used in a stateless fashion throughout the SD process to
(re)compute a sample of possible fault explanations in each iteration, each
time given the latest (updated) system knowledge including all so-far
collected measurements. At this, the built search tree is discarded between
two iterations, although often large parts of the tree have to be rebuilt in
the next iteration, involving redundant operations and calls to costly
reasoning services.

As a remedy to this, we propose DynamicHS, a variant of HS-Tree that maintains
state throughout the diagnostic session and additionally embraces special
strategies to minimize the number of expensive reasoner invocations. DynamicHS
provides an answer to a longstanding question posed by Raymond Reiter in his
seminal paper from 1987, where he wondered whether there is a reasonable
strategy to reuse an existing search tree to compute fault explanations after
new system information is obtained.

We conducted extensive evaluations on real-world diagnosis problems from the
domain of knowledge-based systems—a field where the usage of HS-Tree is state-
of-the-art—under various diagnosis scenarios in terms of the number of fault
explanations computed and the heuristic for measurement selection used. The
results prove the reasonability of the novel approach and testify its clear
superiority to HS-Tree wrt. computation time. More specifically: _(1)_
DynamicHS required less time than HS-Tree in 96 % of the executed sequential
diagnosis sessions. _(2)_ DynamicHS exhibited substantial and statistically
significant time savings over HS-Tree in most scenarios, with median and
maximal savings of 52 % and 75 %, respectively. _(3)_ The relative amount of
saved time appears to neither depend on the number of computed fault
explanations nor on the used measurement selection heuristic. _(4)_ In the
hardest (most time-intensive) cases per diagnosis scenario, DynamicHS achieved
even higher savings than on average, and could avoid median and maximal time
overheads of over 175 % and 800 %, respectively, as opposed to a usage of HS-
Tree.

Remarkably, DynamicHS achieves these performance improvements while preserving
all desirable properties as well as the general applicability of HS-Tree.

##  1 Introduction

_Model-based diagnosis_ (?, ?) is a popular, well-understood, domain-
independent and principled paradigm that has over the last decades found
widespread adoption for troubleshooting systems as different as programs,
circuits, physical devices, knowledge bases, spreadsheets, production plans,
robots, vehicles, or aircrafts (?, ?, ?, ?, ?, ?, ?, ?, ?, ?). The theory of
model-based diagnosis (?) assumes a _system_ that is composed of a set of
_components_ , and a formal _system description_. The latter is given as a
logical knowledge base and can be used to derive the expected behavior of the
system by means of automated deduction systems. If the predicted system
behavior, under the assumption that all components are functioning normally,
is not in line with _observations_ made about the system, the goal is to
locate the abnormal system components that are responsible for this
discrepancy. Given a _diagnosis problem instance (DPI)_ —consisting of the
system description, the system components, and the observations—a _diagnosis_
is a set of components that, when assumed abnormal, leads to consistency
between system description (predicted behavior) and observations (real
behavior). In many cases, there is a substantial number of different diagnoses
given the initial system observations. However, only one of the diagnoses
(which we refer to as the _actual diagnosis_) pinpoints the actually faulty
components. To isolate the actual diagnosis, _sequential diagnosis_ (?)
methods collect additional system observations (called _measurements_) to
gradually refine the set of diagnoses.

The basic idea behind measurements is to exploit the fact that different
diagnoses predict different system behaviors or properties (e.g., intermediate
values or outputs). Observing a system aspect for which the predictions of
diagnoses disagree then leads to the invalidation of those diagnoses whose
predictions are inconsistent with the observation. Since  _(i)_ the amount of
useful information gained differs significantly for different possible
measurements,  _(ii)_ performing a measurement is usually costly (as, e.g., a
human operator needs to take action), and  _(iii)_ determining (nearly)
optimal measurement points is beyond the reach of humans for sufficiently
complex systems,  it is important to have a diagnosis system provide
appropriate measurement suggestions automatically. To this end, several
(efficiently computable) _heuristics_ (?, ?, ?, ?, ?, ?, ?, ?), that define
the goodness of measurements based on various information-theoretic
considerations, have been proposed to deal with the problem that optimal
measurement proposal is NP-hard (?). These heuristics, in principle, assess
the impact of measurements by comparing a-priori (before measurement is taken)
and expected a-posteriori (after measurement outcome is known) situations
regarding the (known) diagnoses and their properties (e.g., probabilities).
That is, the evaluation of the expected utility of measurements requires the
knowledge of a sample of diagnoses. This sample is often termed the _leading
diagnoses_ and usually defined as the best diagnoses according to some
preference criterion such as minimal cardinality (where a minimal _number_ of
components is assumed abnormal) or maximal probability. Beside such criteria,
for computational and pragmatic reasons, a least requirement is usually that
only minimal diagnoses are computed (cf. the “principle of parsimony” (?)). A
_minimal diagnosis_ is one that does not strictly contain (in the sense of
set-inclusion) any diagnosis.

A generic _sequential diagnosis process_ (see Fig. 1) can thus be thought of
as a recurring execution of  _(i)_ the computation of a set of leading minimal
diagnoses,  _(ii)_ the selection of the most informative measurement based on
these,  _(iii)_ the conduction of measurement actions (by some oracle or
user), and  _(iv)_ the exploitation of the measurement outcome to refine the
system knowledge.  This iterative process continues until sufficient
diagnostic certainty is obtained (e.g., one diagnosis has overwhelming
probability).

Decisive factors for successful and practicable sequential diagnosis are a low
number of measurements and a low cost per measurement (effort for human
operator), as well as reasonable system computation times (waiting time of
human operator). While the first two factors depend on a suitable measurement
selection, the latter depends largely on the efficiency of the algorithm for
(leading) diagnoses computation (?, ?, ?).

One of the most popular and widely used such algorithms is Reiter’s HS-Tree
(?), which is adopted in various domains such as for the debugging of software
(?, ?) or ontologies and knowledge bases (?, ?, ?, ?, ?), or for the diagnosis
of hardware (?, ?) or of recommender and configuration systems (?, ?). The
main reasons for the widespread adoption of HS-Tree are that  _(i)_ _it is
broadly applicable_ , because all it assumes is a system description in some
(monotonic111 _Monotonicity_ means that the entailment relation $\models$ of
the logical language satisfies
$\alpha\models\beta\implies\alpha\cup\gamma\models\beta$ for all sets of
sentences $\alpha,\beta,\gamma$ over this language. That is, adding additional
sentences $\gamma$ to a knowledge base $\alpha$ does not invalidate any
conclusions that could be drawn from $\alpha$ beforehand.) knowledge
representation language for which a sound and complete inference method
exists,  _(ii)_ _it is sound and complete_ , as it computes only and
all222Given a non-empty set of minimal diagnoses for a DPI, the problem of
deciding whether there is a minimal diagnosis for this DPI which is not in the
given set is NP-hard (?). Hence, the completeness of HS-Tree (or any other
algorithm that computes minimal diagnoses) guarantees the computation of all
minimal diagnoses for an arbitrary DPI (only) if unlimited time and memory are
assumed. Note that in practical diagnosis applications the computation of
(even multiple) minimal diagnoses is often accomplishable in reasonable time.
minimal diagnoses, and  _(iii)_ _it computes diagnoses in best-first order_
according to a given preference criterion.

Figure 1: Overview of a generic sequential diagnosis process. Note that the
diagnosis problem instance (DPI) changes between phases 4 and 1 in each
iteration, i.e., $\mathit{Prob}_{i+1}$ is the reault of adding the new
measurement obtained from phase 3 to $\mathit{Prob}_{i}$.

However, HS-Tree per-se does not encompass any specific provisions for being
used in an iterative way. In other words, the DPI to be solved is assumed
constant throughout the execution of HS-Tree. As a consequence of that, the
question we address in this work is whether HS-Tree can be optimized for
adoption _in a sequential diagnosis scenario_ , where the DPI to be solved is
subject to successive change (information acquisition through measurements).
Already Raymond Reiter, in his seminal paper (?) from 1987, asked:

> _When new diagnoses do arise as a result of system measurements, can we
> determine these new diagnoses in a reasonable way from the (…) HS-Tree
> already computed in determining the old diagnoses?_

To the best of our knowledge, no study or algorithm has yet been proposed that
sheds light on this very question.

As a result, sequential approaches which draw on HS-Tree for diagnosis
computation have to handle the varying DPI to be solved by re-invoking HS-Tree
each time a new piece of system knowledge (measurement outcome) is obtained.
This amounts to a _discard-and-rebuild_ usage of HS-Tree, where the data
structure (search tree) produced in one iteration is dropped prior to the next
iteration, where a new one is built from scratch. As the new tree obtained
after incorporating the information about one measurement outcome usually
quite closely resembles the existing tree, this approach generally requires
substantial redundant computations. What even exacerbates this fact is that
these computations often involve a significant number of expensive reasoner
calls. For instance, when debugging knowledge bases written in highly
expressive logics such as OWL 2 DL, a single consistency check performed by an
inference service is already 2NEXPTIME-complete (?).

Motivated by that, the contribution of this work is the development of
DynamicHS, a novel _stateful_ variant of HS-Tree that pursues a _reuse-and-
adapt_ strategy and is able to manage the dynamicity of the DPI throughout
sequential diagnosis while avoiding the mentioned redundancy issues. The main
objective of this new algorithm is to allow for more efficient computations
than HS-Tree while maintaining all the aforementioned advantages (generality,
soundness, completeness, best-first property) of the latter. For that purpose,
DynamicHS implements sophisticated techniques such as a time-efficient lazy
update strategy or procedures to minimize expensive reasoning by trading it
for cheaper (reasoning or set) operations.

In extensive evaluations we put DynamicHS to the test, using a benchmark of 20
real-world diagnosis problems from the domain of knowledge-based systems,
which is one prominent field where HS-Tree is the prevalent tool for
(sequential) diagnosis computation (?, ?, ?, ?, ?, ?, ?, ?, ?). One major
cause for the attractivity of HS-Tree in this domain are its mild assumptions
made about the system description language and its resulting independence from
the particular used language and reasoning engine, combined with the fact that
a multitude of different logical languages are adopted in knowledge-based
systems (with the goal to optimally trade off expressivity with reasoning
efficiency). For each diagnosis problem in our dataset, we experimented with
DynamicHS and HS-Tree under various _diagnosis scenarios_ wrt. the number of
diagnoses computed per sequential diagnosis iteration and the employed
measurement selection heuristic. The main insights from our evaluations are:

  * •

DynamicHS is superior to HS-Tree in terms of computation time in 99.4 % of the
investigated diagnosis scenarios, and in 96 % of all single sequential
diagnosis sessions run. Roughly, these savings are achieved by trading less
time (fewer redundant operations and reasoner calls) for more space
(statefulness), where the additional memory required by DynamicHS was
reasonable in the vast majority of the scenarios; and, whenever HS-Tree was
applicable in our experiments in terms of memory requirements, DynamicHS was
so as well.

  * •

The runtime savings over HS-Tree achieved by DynamicHS are substantial and
statistically significant in most scenarios, and reach median and maximal
values of 52 % and 75 %. That is, HS-Tree requires up to an _average_ of four
times the computation time of DynamicHS in the tested diagnosis scenarios. In
_single_ diagnosis sessions, we observed that it took HS-Tree up to more than
nine times as much time as DynamicHS—notably, while both algorithms always
compute _the same_ solutions.

  * •

The median runtime savings of DynamicHS per scenario appear to be neither
dependent on the number of diagnoses computed nor on the measurement selection
heuristic used.

  * •

Considering the hardest cases per diagnosis scenario, which were up to one
order of magnitude harder than the average cases, the time savings obtained by
means of DynamicHS are even more substantial than on average, and reach median
and maximal values of 64 % and 89 %, respectively.

The organization of this work is as follows: Preliminaries on (sequential)
model-based diagnosis are given in Sec. 2. The novel algorithm DynamicHS is
discussed in detail in Sec. 3, where we follow a didactical approach by
“deriving” DynamicHS from Reiter’s well-known HS-Tree algorithm. Moreover, we
prove the algorithm’s correctness and detail some advanced techniques used by
DynamicHS regarding tree management, reasoning operations and node storage.
Related works are reviewed in Sec. 4. In Sec. 5, we describe our experimental
settings, the used test dataset, and thoroughly discuss the obtained results.
More specifically, we first study the performance of DynamicHS, and then
provide explanations for the outcomes through additional analyses. Finally,
Sec. 6 concludes this work.

##  2 Preliminaries

We briefly characterize the basic technical concepts used throughout this
work, based on the framework of (?, ?) which is (slightly) more general (?)
than Reiter’s theory of diagnosis (?). In other words, any model-based
diagnosis problem that can be formulated by means of Reiter’s theory, can be
equivalently stated by the following framework. The main reason for using this
more general framework is its ability to handle negative measurements (things
that must _not_ be true for the diagnosed system) which are helpful, e.g., for
diagnosing knowledge bases (?, ?, ?).

###  2.1 Diagnosis Problem Instance (DPI)

We assume that the diagnosed system, consisting of a set of components
$\left\\{c_{1},\dots,c_{k}\right\\}$, is described by a finite set of logical
sentences $\mathcal{K}\cup\mathcal{B}$, where $\mathcal{K}$ (possibly faulty
sentences) includes knowledge about the behavior of the system components, and
$\mathcal{B}$ (correct background knowledge) comprises any additional
available system knowledge and system observations. More precisely, there is a
one-to-one relationship between sentences $\mathit{ax}_{i}\in\mathcal{K}$ and
components $c_{i}$, where $\mathit{ax}_{i}$ describes the nominal behavior of
$c_{i}$ (_weak fault model_ 333 _Weak fault models_ , in constrast to _strong
fault models_ , define _only the normal behavior_ of the system components,
and do not specify any behavior in case components are at fault (?). The weak
fault model is also referred to as “Ignorance of Abnormal Behavior” property
(?).). For instance, if $c_{i}$ is an AND-gate in a circuit, then
$\mathit{ax}_{i}:=out(c_{i})=and(in1(c_{i}),in2(c_{i}))$; $\mathcal{B}$ in
this example might encompass sentences stating, e.g., which components (gates)
are connected by wires, or observed outputs of the circuit. The inclusion of a
sentence $\mathit{ax}_{i}$ in $\mathcal{K}$ corresponds to the (implicit)
assumption that $c_{i}$ is healthy. Evidence about the system behavior is
captured by sets of positive ($\mathit{P}$) and negative ($\mathit{N}$)
measurements (?, ?, ?). Each measurement is a logical sentence; positive ones,
$\mathit{p}\in\mathit{P}$, must be true, and negative ones,
$\mathit{n}\in\mathit{N}$, must not be true. The former can be, depending on
the context, e.g., observations about the system, probes or required system
properties. The latter model properties that must not hold for the system. For
example, if the diagnosed system is a logical description of a university
domain, a negative test case could be $\forall
X\,(\mathit{researcher(X)}\rightarrow\mathit{professor(X)})$, i.e., that it
must not be true that each researcher is a professor. We call
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ a
_diagnosis problem instance (DPI)_.

Example 1 Tab. 1 depicts an example of a DPI, formulated in propositional
logic. The “system” (which is the knowledge base itself in this case)
comprises five “components” $c_{1},\dots,c_{5}$, and the “nominal behavior” of
$c_{i}$ is given by the respective axiom $\mathit{ax}_{i}\in\mathcal{K}$.
There is neither any background knowledge ($\mathcal{B}=\emptyset$) nor any
positive test cases ($\mathit{P}=\emptyset$) available from the start. But,
there is one negative test case (i.e., $\mathit{N}=\left\\{\lnot A\right\\}$),
which postulates that $\lnot A$ must _not_ be an entailment of the correct
system (knowledge base). Note, however, that $\mathcal{K}$ (i.e., the
assumption that all “components” work nominally) in this case does entail
$\lnot A$ (e.g., due to the axioms $\mathit{ax}_{1},\mathit{ax}_{2}$) and
therefore some axiom in $\mathcal{K}$ must be faulty (i.e., some “component”
is not healthy).∎

Table 1: Example DPI stated in propositional logic. $\mathcal{K}\;=$ |  $\\{\mathit{ax}_{1}:A\to\lnot B$ $\mathit{ax}_{2}:A\to B$ $\mathit{ax}_{3}:A\to\lnot C$
---|---
$\phantom{\\{}\mathit{ax}_{4}:B\to C$ $\mathit{ax}_{5}:A\to B\lor
C\qquad\qquad\,\quad\;\\}$
$\mathcal{B}=\emptyset\quad\qquad\qquad\qquad\mathit{P}=\emptyset\quad\qquad\qquad\qquad\mathit{N}=\left\\{\lnot
A\right\\}$

###  2.2 Diagnoses

Given that the system description along with the positive measurements (under
the assumption $\mathcal{K}$ that all components are healthy) is inconsistent,
i.e., $\mathcal{K}\cup\mathcal{B}\cup\mathit{P}\models\bot$, or some negative
measurement is entailed, i.e.,
$\mathcal{K}\cup\mathcal{B}\cup\mathit{P}\models\mathit{n}$ for some
$\mathit{n}\in\mathit{N}$, some assumption(s) about the healthiness of
components, i.e., some sentences in $\mathcal{K}$, must be retracted. We call
such a set of sentences $\mathcal{D}\subseteq\mathcal{K}$ a _diagnosis_ for
the DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ iff
$(\mathcal{K}\setminus\mathcal{D})\cup\mathcal{B}\cup\mathit{P}\not\models x$
for all $x\in\mathit{N}\cup\left\\{\bot\right\\}$. We say that $\mathcal{D}$
is a _minimal diagnosis_ for a DPI $\mathit{dpi}$ iff there is no diagnosis
$\mathcal{D}^{\prime}\subset\mathcal{D}$ for $\mathit{dpi}$. The set of
minimal diagnoses is representative for all diagnoses (under the weak fault
model (?)), i.e., the set of all diagnoses is exactly given by the set of all
supersets of all minimal diagnoses. Therefore, diagnosis approaches often
restrict their focus to only minimal diagnoses. In the following, we denote
the set of all minimal diagnoses for a DPI $\mathit{dpi}$ by
$\mathbf{diag}(\mathit{dpi})$. We furthermore denote by $\mathcal{D}^{*}$ the
(unknown) _actual diagnosis_ which pinpoints the actually faulty axioms, i.e.,
all elements of $\mathcal{D}^{*}$ are in fact faulty and all elements of
$\mathcal{K}\setminus\mathcal{D}^{*}$ are in fact correct.

Example 2 For our DPI $\mathit{dpi}$ in Tab. 1 we have four minimal diagnoses,
given by $\mathcal{D}_{1}:=[\mathit{ax}_{1},\mathit{ax}_{3}]$,
$\mathcal{D}_{2}:=[\mathit{ax}_{1},\mathit{ax}_{4}]$,
$\mathcal{D}_{3}:=[\mathit{ax}_{2},\mathit{ax}_{3}]$, and
$\mathcal{D}_{4}:=[\mathit{ax}_{2},\mathit{ax}_{5}]$, i.e.,
$\mathbf{diag}(\mathit{dpi})=\left\\{\mathcal{D}_{1},\dots,\mathcal{D}_{4}\right\\}$.444In
this work, we denote diagnoses by square brackets. For instance,
$\mathcal{D}_{1}$ is a minimal diagnosis as
$(\mathcal{K}\setminus\mathcal{D}_{1})\cup\mathcal{B}\cup\mathit{P}=\left\\{\mathit{ax}_{2},\mathit{ax}_{4},\mathit{ax}_{5}\right\\}$
is both consistent and does not entail the given negative test case $\lnot
A$.∎

###  2.3 Conflicts

Useful for the computation of diagnoses is the concept of a conflict (?, ?). A
conflict is a set of healthiness assumptions for components $c_{i}$ that
cannot all hold given the current knowledge about the system. More formally,
$\mathcal{C}\subseteq\mathcal{K}$ is a _conflict_ for the DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ iff
$\mathcal{C}\cup\mathcal{B}\cup\mathit{P}\models x$ for some
$x\in\mathit{N}\cup\left\\{\bot\right\\}$. We call $\mathcal{C}$ a _minimal
conflict_ for a DPI $\mathit{dpi}$ iff there is no conflict
$\mathcal{C}^{\prime}\subset\mathcal{C}$ for $\mathit{dpi}$. In the following,
we denote the set of all minimal conflicts for a DPI $\mathit{dpi}$ by
$\mathbf{conf}(\mathit{dpi})$. A (minimal) diagnosis for $\mathit{dpi}$ is
then a (minimal) hitting set of all minimal conflicts for $\mathit{dpi}$ (?),
where $X$ is a _hitting set_ of a collection of sets $\mathbf{S}$ iff
$X\subseteq\bigcup_{S_{i}\in\mathbf{S}}S_{i}$ and $X\cap S_{i}\neq\emptyset$
for all $S_{i}\in S$.

Example 3 For our running example, $\mathit{dpi}$, in Tab. 1, there are four
minimal conflicts, given by
$\mathcal{C}_{1}:=\langle\mathit{ax}_{1},\mathit{ax}_{2}\rangle$,
$\mathcal{C}_{2}:=\langle\mathit{ax}_{2},\mathit{ax}_{3},\mathit{ax}_{4}\rangle$,
$\mathcal{C}_{3}:=\langle\mathit{ax}_{1},\mathit{ax}_{3},\mathit{ax}_{5}\rangle$,
and
$\mathcal{C}_{4}:=\langle\mathit{ax}_{3},\mathit{ax}_{4},\mathit{ax}_{5}\rangle$,
i.e.,
$\mathbf{conf}(\mathit{dpi})=\left\\{\mathcal{C}_{1},\dots,\mathcal{C}_{4}\right\\}$.555In
this work, we denote conflicts by angle brackets. For instance,
$\mathcal{C}_{4}$, in CNF equal to $(\lnot A\lor\lnot C)\land(\lnot B\lor
C)\land(\lnot A\lor B\lor C)$, is a conflict because, adding the unit clause
$(A)$ to this CNF yields a contradiction, which is why the negative test case
$\lnot A$ is an entailment of $\mathcal{C}_{4}$. The minimality of the
conflict $\mathcal{C}_{4}$ can be verified by rotationally removing from
$\mathcal{C}_{4}$ a single axiom at the time and controlling for each so
obtained subset that this subset is consistent and does not entail $\lnot A$.

For example, the minimal diagnosis $\mathcal{D}_{1}$ (see Example 2.2) is a
hitting set of all minimal conflict sets because each conflict in
$\mathbf{conf}(\mathit{dpi})$ contains $\mathit{ax}_{1}$ or $\mathit{ax}_{3}$.
It is moreover a _minimal_ hitting set since the elimination of
$\mathit{ax}_{1}$ implies an empty intersection with, e.g., $\mathcal{C}_{1}$,
and the elimination of $\mathit{ax}_{3}$ means that, e.g., $\mathcal{C}_{4}$
is no longer hit.∎

Literature offers a variety of algorithms for conflict computation, e.g., (?,
?, ?). Given a DPI
$\mathit{dpi}=\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$
as input, one call to such an algorithm returns one minimal conflict for
$\mathit{dpi}$, if existent, and ’no conflict’ otherwise. All algorithms
require an appropriate theorem prover that is used as an oracle to perform
consistency checks over the logic by which the DPI is expressed. In the worst
case, none of the available algorithms requires fewer than $O(|\mathcal{K}|)$
theorem prover calls per conflict computation (?). The performance of
diagnosis computation methods depends largely on the complexity of consistency
checking for the used logic and on the number of consistency checks executed
(cf., e.g., (?)). Since consistency checking is often NP-complete or beyond
for practical problems (?, ?, ?, ?, ?), and diagnostic algorithms have no
influence on the used system description language, it is pivotal to keep the
number of conflict computations at a minimum.

###  2.4 Sequential Diagnosis (SD) Problem

We now define the sequential diagnosis (SD) problem, which calls for a set of
measurements for a given DPI, such that adding these measurements to the DPI
implies diagnostic certainty, i.e., a single remaining minimal diagnosis for
the new DPI. In the optimization version (OptSD), the goal is to find such a
measurement set of minimal cost.

######  Problem 1 ((Opt)SD).

Given: A DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$.
Find: A (minimal-cost) set of measurements
$\mathit{P}^{\prime}\cup\mathit{N}^{\prime}$ such that
$|\mathbf{diag}(\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\right\rangle)|=1$.666There
are different characterizations of the SD Problem in literature. E.g., it is
sometimes formulated as the problem of finding a policy that suggests the next
measurement given any possible situation that might be encountered starting
from a given DPI. For the purpose of this paper, we basically stick to the
conceptualization of (?), where measurements are sets of logical sentences.

A minimal-cost set of measurements
$\mathit{P}^{\prime}\cup\mathit{N}^{\prime}$ minimizes
$\sum_{m\in\mathit{P}^{\prime}\cup\mathit{N}^{\prime}}\mathsf{cost}(m)$, where
$\mathsf{cost}(m)$ is the cost value assigned to measurement $m$. Possible
cost functions range from simple unit cost assumptions for measurements
($\mathsf{cost}(m)=1$ for all $m$) to sophisticated measurement time, effort,
or complexity evaluations (?, ?, ?).

Example 4 Let
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ be
the example DPI described in Tab. 1, and assume that
$\mathcal{D}^{*}=\mathcal{D}_{2}$, i.e., $[\mathit{ax}_{1},\mathit{ax}_{4}]$
is the actual diagnosis. Then, one solution to Problem 1 is
$\mathit{P}^{\prime}=\\{A\land B\\}$ and $\mathit{N}^{\prime}=\\{C\\}$. In
other words,
$\mathbf{diag}(\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\right\rangle)=\\{\mathcal{D}_{2}\\}$.
An alternative solution would be $\mathit{P}^{\prime}=\\{A\to\lnot C\\}$ and
$\mathit{N}^{\prime}=\\{A\to C,A\to\lnot B\\}$. If the solution cost is
quantified by the number of measurements, then the first solution has a cost
of 2, whereas the second has a cost of 3. We would thus prefer the first
solution. If we alternatively adopt a more fine-grained cost analysis,
considering also the estimated complexity of the measurements, e.g., that
negation and implication are harder (to understand for an interacting domain
expert who labels sentences as positive or negative measurements) than
conjunction, then the first solution would be even more preferred to the
second than under the assumption of uniform measurement costs. ∎

###  2.5 Computational Issues in Sequential Diagnosis

In principle, the OptSD problem can be tackled by appropriate _measurement
point 777 In the scope of this work, the relation between measurement and
measurement point is as follows. A _measurement_ is a logical sentence that
describes the outcome of a _measuring action_ at some predefined _measurement
point_. For instance, when diagnosing a circuit, the measurement action could
be the application of a voltmeter, and the measurement point a particular
terminal of a gate in a circuit. The outcome would then be whether the
measured wire $w$ is high (1) or low (0), yielding one of the (positive)
measurements $w=1$ or $w=0$, respectively. selection888What we call
_measurement point selection_ in this work is often simply referred to as
_measurement selection_ in literature, e.g., (?, ?). Moreover, the measurement
point selection might also include a prior _measurement point computation_ ,
for (e.g., knowledge-based) systems for which the possible measurement points
are not explicitly given (?, ?)._ (?) approaches. However, due to the NP-
hardness of OptSD (?), sequential diagnosis systems, in general, can merely
attempt to approximate its optimal solution. This is usually accomplished by
means of a one-step-lookahead approach (?) which evaluates (the gain of)
possible measurement points based on the a-posteriori situations encountered
for its different outcomes, weighted by their respective (estimated)
probabilities. To make these estimations, a sample of (minimal) diagnoses, the
_leading diagnoses_ , is usually taken as a basis (?, ?, ?, ?). In the context
of one-step-lookahead analysis, a range of measurement point evaluation
_heuristics_ have been suggested in literature, such as the measurement
point’s information gain (?), its ability to guarantee a maximal worst-case
diagnoses invalidation rate (?, ?), a dynamic combination thereof (?), or the
measurement point’s goodness wrt. various active learning criteria (?, ?, ?).
Besides these more sophisticated assessment criteria, a common minimal
requirement to a rational measurement point selection strategy is that it
suggests only _discriminating measurement points_ , i.e., for each measurement
outcome there must be at least one leading diagnosis that is inconsistent with
this outcome. In other words, proposing a discriminating measurement point
guarantees the invalidation of some spurious fault hypothesis (or: the gain of
some useful information) already a-priori, irrespective of the measurement
outcome.

While appropriate measurement point selection is one important factor
determining the overall efficiency of the diagnostic process, not only the
cost associated with the _measurement conduction_ is of relevance from the
viewpoint of a user interacting with a sequential diagnosis engine. In fact,
there is another crucial factor which is left implicit in Problem 1, namely
the question how efficiently the _measurement point computation_ is
accomplished by the diagnosis system. Because, the _overall_ (user) time to
diagnose a system is given by the overall measurement conduction time _plus_
the overall system computation time for the proposal of the measurement
points. The following problem makes this explicit:

######  Problem 2 (Efficient (Opt)SD).

Given: A DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$.
Find: A solution to (Opt)SD in minimal time.

Approaching a solution to Problem 2 involves the minimization of what we call
the system _reaction time_ , i.e., the computation time required by the system
after being informed about the outcome of one measuring action until the
provision of the next measurement point. The reaction time is composed of the
time required for _(i)_ the _system knowledge update_ (based on the
information acquired through a new measurement), _(ii)_ the (leading)
_diagnosis computation_ , as well as for _(iii)_ the _measurement point
selection_. These main factors affecting the sequential diagnosis time are
summarized in Fig. 2.

Whereas the efficiency-optimization of measurement point selection
algorithms999Measurement selection algorithms (?) are given a set of leading
diagnoses, the current system knowledge (DPI), as well as the available
probabilistic information and a selection heuristic, and should output “the
best” next measurement according to the given heuristic. can be largely or
even fully decoupled from diagnosis computation and knowledge update
algorithms, the latter two might need to be studied in common, depending on
whether the diagnosis computation is stateless (?, ?) or stateful (?, ?, ?).
More specifically, the elaborateness of the knowledge update process might
range from almost trivial (addition of a new measurement to the DPI; update of
probabilities) in the stateless case, to very sophisticated in the stateful
case, where, e.g., the state of a persistent data structure used throughout
sequential diagnosis must be additionally updated.

We present in this work DynamicHS, a stateful diagnosis computation algorithm
that addresses Problem 2 by _focusing on the efficiency of the diagnosis
computation and knowledge update processes_ (cf. Fig. 2). In fact, we will
provide empirical evidence (in Sec. 5) that the novel algorithm is more time-
efficient for sequential diagnosis than Reiter’s HS-Tree, which is a state-of-
the-art diagnosis computation approach, e.g., in the knowledge base and
ontology debugging domains (?, ?, ?, ?, ?, ?, ?, ?, ?). In particular,
DynamicHS aims at achieving an efficiency gain over HS-Tree while _computing
the same solution_ to Problem 1 as HS-Tree, while _preserving all the
(desirable) properties_ of HS-Tree, and while _maintaining full compatibility
with other approaches_ that tackle Problem 2 from the perspective of making
the measurement point selection more efficient (such as (?)), or that attack
Problem 1 to achieve a reduction of measurement conduction time (such as (?,
?, ?)).

Figure 2: Categorization of the factors that influence the overall sequential
diagnosis time. The blue / red frame refers to the OptSD / Efficient OptSD
problem. The factors shaded green are those addressed by the DynamicHS
algorithm suggested in this work. For the figure to reflect a more general
viewpoint (including also resources other than time), one may replace each
occurrence of “time” in the figure by “cost”.

##  3 DynamicHS Algorithm

###  3.1 Outline of DynamicHS

####  3.1.1 Motivation and Principle

Starting from Reiter’s HS-Tree, the main observation that builds the ground
for the development of DynamicHS is that, throughout a sequential diagnosis
session, the initially given DPI is subject to gradual change. That is, new
measurements are successively added to it, and usually significant portions of
a built hitting set tree remain unaffected after the transition from one DPI
to the next. Thus, discarding the existing tree and (re)constructing a similar
tree in the next iteration potentially involves a significant number of
redundant (and expensive) operations. With DynamicHS, we account for that by
proposing to replace a discard-and-rebuild paradigm by an adapt-and-reuse
one—that is, the built hitting set tree is persistently maintained and
accordingly adapted each time a new measurement comes in. These tree updates,
which mainly include tree pruning and node relabeling steps, are required to
guarantee the correctness of the diagnosis computation in the next iteration,
i.e., for the _newest_ DPI. The underlying rationale of DynamicHS is to avoid
unnecessary repeated actions and to cleverly leverage the reused search data
structure to trade expensive reasoning against cheaper operations, such as set
comparisons or less expensive (but equally informative) reasoning.

####  3.1.2 Inputs and Outputs

DynamicHS (depicted by Alg. 3 on page 3) is a procedure that computes a set of
minimal diagnoses for a DPI
$\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$
in best-first order (as per some given goodness criterion, which we assume to
be a probability measure $\mathit{pr}$ in this work). DynamicHS accepts the
following arguments: _(1)_ an initial DPI
$\mathit{dpi}_{0}=\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$,
_(2)_ the already accumulated positive and negative measurements
$\mathit{P}^{\prime}$ and $\mathit{N}^{\prime}$, respectively, _(3)_ a
probability measure $\mathit{pr}$ which is exploited to compute diagnoses in
descending order based on their probabilities, _(4)_ a stipulated number
$\mathit{ld}\geq 2$ of diagnoses to be returned,101010The reason why at least
two diagnoses should be computed is that _(i)_ two or more minimal diagnoses
are needed for the computation of a discriminating measurement point (?) (cf.
Sec. 2.5), and _(ii)_ this way the stop criterion “only a single minimal
diagnosis remaining” (cf. Alg. 1) guarantees that the sequential diagnosis
process ends only if diagnostic certainty has been achieved (correct diagnosis
among _all_ minimal diagnoses found). _(5)_ the set of those diagnoses
returned by the previous run of DynamicHS that are consistent
($\mathbf{D}_{\checkmark}$) and those that are inconsistent
($\mathbf{D}_{\times}$) with the last added measurement, and _(6)_ a tuple of
variables $\mathsf{state}$, which altogether describe DynamicHS’s current
state.

Algorithm 1 Sequential Diagnosis

1:DPI
$\mathit{dpi}_{0}:=\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$,
probability measure $\mathit{pr}$ (to compute diagnoses probabilities), number
$\mathit{ld}$ ($\geq 2$) of minimal diagnoses to be computed per iteration,
heuristic $\mathsf{heur}$ for measurement selection, boolean
$\mathit{dynamic}$ that governs which diagnosis computation algorithm is used
(DynamicHS if true, HS-Tree otherwise)

2:$\left\\{\mathcal{D}\right\\}$ where $\mathcal{D}$ is the final diagnosis
after solving SD (Problem 1)

3:$\mathit{P}^{\prime}\leftarrow\emptyset,\mathit{N}^{\prime}\leftarrow\emptyset$
$\triangleright$ performed measurements

4:$\mathbf{D}_{\checkmark}\leftarrow\emptyset,\mathbf{D}_{\times}\leftarrow\emptyset$
$\triangleright$ variables describing state…

5:$\mathsf{state}\leftarrow\left\langle[\,[]\,],[\,],\emptyset,\emptyset\right\rangle$
$\triangleright$ …of DynamicHS tree

6:while $\mathit{true}$ do

7: if $\mathit{dynamic}$ then

8:
$\left\langle\mathbf{D},\mathsf{state}\right\rangle\leftarrow\textsc{DynamicHS}(\mathit{dpi}_{0},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld},\mathbf{D}_{\checkmark},\mathbf{D}_{\times},\mathsf{state})$

9: else

10: $\mathbf{D}\leftarrow\textsc{HS-
Tree}(\mathit{dpi}_{0},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld})$

11: if $|\mathbf{D}|=1$ then return $\mathbf{D}$

12:
$mp\leftarrow\textsc{computeBestMeasPoint}(\mathbf{D},\mathit{dpi}_{0},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathsf{heur})$

13: $\mathit{outcome}\leftarrow\textsc{performMeas}(mp)$ $\triangleright$
oracle inquiry (user interaction)

14:
$\left\langle\mathit{P}^{\prime},\mathit{N}^{\prime}\right\rangle\leftarrow\textsc{addMeas}(mp,outcome,\mathit{P}^{\prime},\mathit{N}^{\prime})$

15: if $\mathit{dynamic}$ then

16:
$\left\langle\mathbf{D}_{\checkmark},\mathbf{D}_{\times}\right\rangle\leftarrow\textsc{assignDiagsOkNok}(\mathbf{D},\mathit{dpi}_{0},\mathit{P}^{\prime},\mathit{N}^{\prime})$

####  3.1.3 Embedding in Sequential Diagnosis Process

Alg. 1 sketches a generic sequential diagnosis algorithm and shows how it
accommodates DynamicHS (line 8) or, alternatively, Reiter’s HS-Tree (line 10),
as methods for iterative diagnosis computation. The algorithm reiterates a
while-loop (line 6) until the solution space of minimal diagnoses includes
only a single element.111111Of course, less rigorous stopping criteria are
possible, e.g., one might appoint a probability threshold and stop once the
probability of one computed diagnosis exceeds this threshold (?). Since both
DynamicHS and HS-Tree are complete (see later) and always attempt to compute
at least two diagnoses ($\mathit{ld}\geq 2$), this stop criterion is met iff a
diagnoses set $\mathbf{D}$ with $|\mathbf{D}|=1$ is output (line 11). On the
other hand, as long as $|\mathbf{D}|>1$, the algorithm seeks to acquire
additional information to rule out further elements in $\mathbf{D}$. To this
end, the best next measurement point $mp$ is computed (computeBestMeasPoint,
line 12), using the current system information—$\mathit{dpi}_{0}$,
$\mathbf{D}$, and acquired measurements $\mathit{P}^{\prime}$,
$\mathit{N}^{\prime}$—as well as the given probabilistic information
$\mathit{pr}$ and some selection heuristic $\mathsf{heur}$ (which defines what
“best” means, cf. (?)). The conduction of the measurement at $mp$
(performMeas, line 13) is usually accomplished by a qualified user (_oracle_)
that interacts with the sequential diagnosis system, e.g., an electrical
engineer for a defective circuit, or a domain expert in case of a faulty
knowledge base. The measurement point $mp$ along with its result
$\mathit{outcome}$ are used to formulate a logical sentence $m$ that is either
added to $\mathit{P}^{\prime}$ if $m$ constitutes a positive measurement, and
to $\mathit{N}^{\prime}$ otherwise (addMeas, line 14).121212Depending on the
diagnosed system, the notion of a “measurement point” might be quite
differently interpreted. For instance, in case of a physical system (?), it
might be literally a point $mp$ in the system where to make a measurement with
some physical measurement instrument (e.g., a voltmeter). In case of a
knowledge-based system (?), on the other hand, it might be, e.g., a question
$mp$ in the form of a logical sentence asked to an expert about the domain
described by a problematic knowledge base; e.g., one could ask $mp:=\forall
X\,(\mathit{bird(X)}\rightarrow\mathit{canFly(X)})$ (“can all birds fly?”).
Likewise, the “outcome” of a measurement might be the measured value $v$ at
the measurement point $mp$ in the former case, and a truth value answering the
asked question $mp$ in the latter. The new “measurement” (logical sentence),
formulated from the measurement point and the respective outcome, could be
$m_{phys}:=mp=v$ in the former, and $m_{\mathit{KB}}:=mp$ in the latter case.
At this, $m_{phys}$ would be added to the positive measurements
$\mathit{P}^{\prime}$ (since $m_{phys}$ is now a fact), whereas
$m_{\mathit{KB}}$ would be added to the positive (negative) measurements
$\mathit{P}^{\prime}$ ($\mathit{N}^{\prime}$) if the answer to the asked
question was positive (negative), i.e., $m_{\mathit{KB}}$ must (not) be true
in the correct knowledge base (cf. (?)). Finally, if DynamicHS is adopted, the
set of diagnoses $\mathbf{D}$ is partitioned into those consistent
($\mathbf{D}_{\checkmark}$) and those inconsistent ($\mathbf{D}_{\times}$)
with the newly added measurement $m$ (assignDiagsOkNok, line 16).

####  3.1.4 Properties

DynamicHS is _stateful_ in that one and the same tree data structure is used
throughout the entire sequential diagnostic process. Apart from that, it
preserves all (desirable) properties of Reiter’s HS-Tree, i.e., the
_soundness_ (only minimal diagnoses for the current DPI are found) and
_completeness_ (all minimal diagnoses for the current DPI can be found) of the
diagnosis search in each iteration, as well as the generality (_logics- and
reasoner-independence_) and the feature to _calculate diagnoses in most-
preferred-first order_.

####  3.1.5 Specialized Incorporated Techniques

To keep the extent—and thus the impact on the computational complexity—of the
regularly performed tree update actions at a minimum, DynamicHS incorporates a
specialized _lazy update policy_ , where only such updates are executed whose
omission would (in general) compromise the soundness or completeness of the
diagnosis search. Second, as regards the tree pruning, DynamicHS features an
_efficient two-tiered redundancy testing technique_ for evaluating tree
branches with regard to whether they are necessary (still needed) or redundant
(ready to be discarded). The principle behind this technique is to first
execute a more performant sound but incomplete test, and second, only if
necessary, a sound and complete test. Moreover, preliminarily unneeded
_“duplicate” tree branches are stored in a space-saving manner_ and only used
on demand to reconstruct a proper replacement branch if the “original”
associated with the duplicate has become redundant. Finally, DynamicHS
embraces various _strategies to avoid the overall amount of logical reasoning_
involved in its computations, since the calls of a logical inference engine
normally account for most of the computation time of a diagnosis system (cf.,
e.g., (?)).

###  3.2 Description of DynamicHS

In this section we describe the DynamicHS algorithm, given by Alg. 3, in more
detail. It inherits many of its aspects from Reiter’s HS-Tree, depicted by
Alg. 2. Hence, we first recapitulate HS-Tree and then focus on the differences
to and idiosyncrasies of DynamicHS.

####  3.2.1 Reiter’s HS-Tree

We briefly repeat the functioning of Reiter’s HS-Tree (Alg. 2), which computes
minimal diagnoses for a DPI
$\mathit{dpi}=\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\right\rangle$
in a sound, complete131313Unlike Reiter (?), we assume that only _minimal_
conflicts are used as node labels. Thus, the issue pointed out by (?) does not
arise. and best-first way.

Starting from a priority queue of unlabeled nodes ${\mathbf{Q}}$, initially
comprising only an unlabeled root node, $\emptyset$, the algorithm continues
to remove and label the first ranked node from ${\mathbf{Q}}$ (getAndDele-
teFirst) until all nodes are labeled (${\mathbf{Q}}=[\,]$) or $\mathit{ld}$
minimal diagnoses have been computed. The possible node labels are minimal
conflicts (for internal tree nodes) and $\mathit{valid}$ as well as
$\mathit{closed}$ (for leaf nodes). All minimal conflicts that have already
been computed and used as node labels are stored in the (initially empty) set
$\mathbf{C}_{calc}$. Each edge in the constructed tree has a label. For ease
of notation (in Alg. 2), the set of edge labels along the branch from the root
node of the tree to a node $\mathsf{nd}$ is associated with $\mathsf{nd}$,
i.e., $\mathsf{nd}$ stores this set of labels. E.g., the node at location
$\tiny12⃝$ in iteration 1 of Fig. 4 on page 4 is referred to as
$\left\\{1,2,5\right\\}$. Once the tree has been completed
(${\mathbf{Q}}=[\,]$), i.e., all nodes are labeled, the minimal diagnoses for
$\mathit{dpi}$ are given exactly by the set of all nodes labeled
$\mathit{valid}$; formally:
$\mathbf{diag}(\mathit{dpi})=\left\\{\mathsf{nd}\mid\mathsf{nd}\text{ is
labeled }\mathit{valid}\right\\}$.

Algorithm 2 HS-Tree

1:tuple
$\left\langle\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld}\right\rangle$
comprising

  * •

a DPI
$\mathit{dpi}=\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$

  * •

the acquired sets of positive ($\mathit{P}^{\prime}$) and negative
($\mathit{N}^{\prime}$) measurements so far

  * •

a function $\mathit{pr}$ assigning a fault probability to each element in
$\mathcal{K}$

  * •

the number $\mathit{ld}$ of leading minimal diagnoses to be computed

2:$\mathbf{D}$, the set of the $\mathit{ld}$ (if existent) most probable (as
per $\mathit{pr}$) minimal diagnoses wrt.
$\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$

3:procedure
hsTree($\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld}$)

4: $\mathbf{D}_{calc},\mathbf{C}_{calc}\leftarrow\emptyset$

5: ${\mathbf{Q}}\leftarrow[\emptyset]$

6: while
${\mathbf{Q}}\neq[\,]\land\left(\;|\mathbf{D}_{calc}|<\mathit{ld}\;\right)$ do

7: $\mathsf{node}\leftarrow\textsc{getAndDeleteFirst}({\mathbf{Q}})$

8: $\left\langle
L,\mathbf{C}\right\rangle\leftarrow\textsc{label}(\mathit{dpi},\mathsf{node},\mathbf{C}_{calc},\mathbf{D}_{calc},{\mathbf{Q}})$

9: $\mathbf{C}_{calc}\leftarrow\mathbf{C}$

10: if $L=\mathit{valid}$ then

11:
$\mathbf{D}_{calc}\leftarrow\mathbf{D}_{calc}\cup\left\\{\mathsf{node}\right\\}$

12: else if $L=\mathit{closed}$ then $\triangleright$ do nothing $\to\;$
$\mathsf{node}$ discarded

13: else$\triangleright$ $L$ must be a minimal conflict set

14: for $e\in L$ do

15:
${\mathbf{Q}}\leftarrow\textsc{insertSorted}(\mathsf{node}\cup\left\\{e\right\\},{\mathbf{Q}},\mathit{pr})$

16: return $\mathbf{D}_{calc}$

17:procedure
label($\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle,\mathsf{node},\mathbf{C}_{calc},\mathbf{D}_{calc},{\mathbf{Q}}$)

18: for $\mathsf{nd}\in\mathbf{D}_{calc}$ do $\triangleright$ (L1)

19: if $\mathsf{node}\supseteq\mathsf{nd}$ then $\triangleright$ non-
minimality

20: return $\left\langle\mathit{closed},\mathbf{C}_{calc}\right\rangle$

21: for $\mathsf{nd}\in{\mathbf{Q}}$ do $\triangleright$ (L2)

22: if $\mathsf{node}=\mathsf{nd}$ then $\triangleright$ remove duplicates

23: return $\left\langle\mathit{closed},\mathbf{C}_{calc}\right\rangle$

24: for $\mathcal{C}\in\mathbf{C}_{calc}$ do $\triangleright$ (L3)

25: if $\mathcal{C}\cap\mathsf{node}=\emptyset$ then $\triangleright$ reuse
conflict $\mathcal{C}$

26: return $\left\langle\mathcal{C},\mathbf{C}_{calc}\right\rangle$

27:
$L\leftarrow\textsc{findMinConflict}(\langle\mathcal{K}\setminus\mathsf{node},\mathcal{B},\mathit{P},\mathit{N}\rangle_{\mathit{R}})$
$\triangleright$ (L4)

28: if $L$ = ’no conflict’ then $\triangleright$ $\mathsf{node}$ is a
diagnosis

29: return $\left\langle\mathit{valid},\mathbf{C}_{calc}\right\rangle$

30: else$\triangleright$ $L$ is _new_ minimal conflict set
($\notin\mathbf{C}_{calc}$)

31: $\mathbf{C}_{calc}\leftarrow\mathbf{C}_{calc}\cup\left\\{L\right\\}$

32: return $\left\langle L,\mathbf{C}_{calc}\right\rangle$

To label a node $\mathsf{nd}$, the algorithm calls a labeling function (label)
which executes the following tests in the given order and returns as soon as a
label for $\mathsf{nd}$ has been determined:

  1. (L1)

_(non-minimality):_ Check if $\mathsf{nd}$ is non-minimal (i.e., whether there
is a node $\mathsf{n}$ with label $\mathit{valid}$ where
$\mathsf{nd}\supseteq\mathsf{n}$). If so, $\mathsf{nd}$ is labeled by
$\mathit{closed}$.

  2. (L2)

_(duplicate):_ Check if $\mathsf{nd}$ is duplicate (i.e., whether
$\mathsf{nd}=\mathsf{n}$ for some other $\mathsf{n}$ in ${\mathbf{Q}}$). If
so, $\mathsf{nd}$ is labeled by $\mathit{closed}$.

  3. (L3)

_(reuse label):_ Scan $\mathbf{C}_{calc}$ for some $\mathcal{C}$ such that
$\mathsf{nd}\cap\mathcal{C}=\emptyset$. If so, $\mathsf{nd}$ is labeled by
$\mathcal{C}$.

  4. (L4)

_(compute label):_ Invoke findMinConflict, a _(sound and complete) minimal
conflicts searcher_ , e.g., QuickXPlain (?, ?), to get a minimal conflict for
$\langle\mathcal{K}\setminus\mathsf{nd},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$.
If a minimal conflict $\mathcal{C}$ is output, $\mathsf{nd}$ is labeled by
$\mathcal{C}$. Otherwise, if ’no conflict’ is returned, then $\mathsf{nd}$ is
labeled $\mathit{valid}$.

All nodes labeled by $\mathit{closed}$ or $\mathit{valid}$ have no successors
and are leaf nodes. For each node $\mathsf{nd}$ labeled by a minimal conflict
$L$, one outgoing edge is constructed for each element $e\in L$, where this
edge is labeled by $e$ and pointing to a newly created unlabeled node
$\mathsf{nd}\cup\left\\{e\right\\}$. Each new node is added to ${\mathbf{Q}}$
such that ${\mathbf{Q}}$’s sorting is preserved (insertSorted). ${\mathbf{Q}}$
might be, e.g., _(i)_ a FIFO queue, entailing that HS-Tree computes diagnoses
in minimum-cardinality-first order (_breadth-first search_), or _(ii)_ sorted
in descending order by $\mathit{pr}$, where most probable diagnoses are
generated first (_uniform-cost search_ ; for details see (?, Sec. 4.6)).

Importantly, $\mathit{pr}$ must in any case be specified in a way the
probability for each system component (element of $\mathcal{K}$) is below
$0.5$.141414This condition (?) is fairly benign as it can be established from
any probability model $\mathit{pr}$ by simply choosing an arbitrary fixed
$c\in(0,0.5)$ and by setting
$\mathit{pr}_{\mathit{adj}}(\mathit{ax}):=c\cdot\mathit{pr}(\mathit{ax})$ for
all $\mathit{ax}\in\mathcal{K}$. Observe that this adjustment does not affect
the relative probabilities or the fault probability order of components in
that
$\mathit{pr}_{\mathit{adj}}(\mathit{ax})/\mathit{pr}_{\mathit{adj}}(\mathit{ax}^{\prime})=k$
whenever $\mathit{pr}(\mathit{ax})/\mathit{pr}(\mathit{ax}^{\prime})=k$. In
other words, each system component must be more likely to be nominal than to
be faulty. This additional assumption is necessary for the soundness of HS-
Tree, i.e., to guarantee that _only_ minimal diagnoses are returned. The
crucial point is that, for a queue ${\mathbf{Q}}$ ordered by $\mathit{pr}$,
this requirement guarantees that node $\mathsf{n}\in{\mathbf{Q}}$ will be
processed prior to node $\mathsf{n}^{\prime}\in{\mathbf{Q}}$ whenever
$\mathsf{n}\subset\mathsf{n}^{\prime}$. For more information consider (?, p.
73 et seq.).

Finally, note the _statelessness_ of Reiter’s HS-Tree, reflected by
${\mathbf{Q}}$ initially including _only an unlabeled root node_ , and
$\mathbf{C}_{calc}$ being initially _empty_. That is, an HS-Tree is built from
scratch in each iteration, every time for different measurement sets
$\mathit{P}^{\prime},\mathit{N}^{\prime}$.

####  3.2.2 Dynamicity of DPI in Sequential Diagnosis

In the course of the sequential diagnosis process (Alg. 1), where additional
system knowledge is gathered in terms of measurements, the DPI is subject to
gradual change—it is dynamic. At this, each addition of a new discriminating
measurement151515A _discriminating measurement_ is a measurement at a
discriminating measurement point (cf. Sec. 2). That is, adding such a
measurement to (the positive or negative measurements of) the DPI causes the
invalidation of at least one diagnosis. to the DPI also effectuates a
transition of the sets of (minimal) diagnoses and (minimal) conflicts. Whereas
this fact is of no concern to a stateless diagnosis computation strategy, it
has to be carefully taken into account when engineering a stateful approach.

####  3.2.3 Towards Stateful Hitting Set Computation

To understand the necessary design decisions to devise a sound and complete
stateful hitting set algorithm in the light of the said DPI dynamicity, we
next discuss a few more specifics of the conflicts and diagnoses evolution
throughout sequential diagnosis:161616A more formal treatment and proofs for
all statements can be found in (?, Sec. 12.4).

######  Property 1.

Let
$\mathit{dpi}_{j}=\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$
be a DPI and let $T$ be Reiter’s HS-Tree for $\mathit{dpi}_{j}$ (executed
until) producing the leading diagnoses $\mathbf{D}$ where $|\mathbf{D}|\geq
2$. Further, let the measurement $m$ describe the outcome of measuring at a
discriminating measurement point computed from $\mathbf{D}$, and let
$\mathit{dpi}_{j+1}$ be the DPI resulting from $\mathit{dpi}_{j}$ through the
addition of $m$ to either $\mathit{P}$ or $\mathit{N}$. Then:

  1. 1.

$T$ is not a correct HS-Tree for $\mathit{dpi}_{j+1}$, i.e., (at least) some
node labeled by $\mathit{valid}$ in $T$ is incorrectly labeled.
_That is, to reuse $T$ for $\mathit{dpi}_{j+1}$, $T$ must be appropriately
updated._

  2. 2.

Each $\mathcal{D}\in\mathbf{diag}(\mathit{dpi}_{j+1})$ is either equal to or a
superset of some $\mathcal{D}^{\prime}\in\mathbf{diag}(\mathit{dpi}_{j})$.
_That is, minimal diagnoses can grow or remain unchanged, but cannot shrink.
Consequently, to reuse $T$ for sound and complete minimal diagnosis
computation for $\mathit{dpi}_{j+1}$, existing nodes must never be
reduced—either a node is left as is, deleted as a whole, or (prepared to be)
extended._

  3. 3.

For all $\mathcal{C}\in\mathbf{conf}(\mathit{dpi}_{j})$ there is a
$\mathcal{C}^{\prime}\in\mathbf{conf}(\mathit{dpi}_{j+1})$ such that
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$.
_That is, existing minimal conflicts can only shrink or remain unaffected, but
cannot grow. Hence, priorly computed minimal conflicts (for an old DPI) might
not be minimal for the current DPI. In other words, conflict node labels of
$T$ can, but do not need to, be correct for $\mathit{dpi}_{j+1}$._

  4. 4.

(a) There is some $\mathcal{C}\in\mathbf{conf}(\mathit{dpi}_{j})$ for which
there is some $\mathcal{C}^{\prime}\in\mathbf{conf}(\mathit{dpi}_{j+1})$ with
$\mathcal{C}^{\prime}\subset\mathcal{C}$, and/or
(b) there is some
$\mathcal{C}_{\mathit{new}}\in\mathbf{conf}(\mathit{dpi}_{j+1})$ where
$\mathcal{C}_{\mathit{new}}\not\subseteq\mathcal{C}^{\prime\prime}$ and
$\mathcal{C}_{\mathit{new}}\not\supseteq\mathcal{C}^{\prime\prime}$ for all
$\mathcal{C}^{\prime\prime}\in\mathbf{conf}(\mathit{dpi}_{j})$.
_That is, at least one minimal conflict is reduced in size, and/or at least
one entirely new minimal conflict (which is not in any subset-relationship
with existing ones) arises. Some existing node in $T$ which represents a
minimal diagnosis for $\mathit{dpi}_{j}$ _(a)_ can be deleted since it would
not be present when using $\mathcal{C}^{\prime}$ as node label in $T$ wherever
$\mathcal{C}$ is used, or _(b)_ must be extended to constitute a diagnosis for
$\mathit{dpi}_{j+1}$, since it does not hit (has an empty intersection with)
the conflict $\mathcal{C}_{\mathit{new}}$._

####  3.2.4 Major Modifications to Reiter’s HS-Tree

Based on Property 1, the following principal amendments to Reiter’s HS-Tree
are necessary to make it a properly-working stateful diagnosis computation
method. We exemplify these modifications by referring to Figs. 3 and 4 (on
pages 3 and 4), which are discussed in detail in Example 4 and which describe
sequential diagnosis executions (as per Alg. 1) of DynamicHS and HS-Tree,
respectively, for our example DPI given in Tab. 1.

  1. (Mod1)

A tree update is executed at the beginning of each DynamicHS execution, where
the hitting set tree produced for a previously relevant DPI is adapted to a
tree that allows to compute minimal diagnoses for the current DPI in a sound,
complete and best-first manner.
_Justification:_ The necessity of this update is attested by Property 1.1. The
actions taken in the course of the update are motivated by the remaining
bullet points of Property 1.
_Example:_ Between iterations 1 and 2 in Fig. 3, DynamicHS runs a tree update,
which adapts the tree constructed in iteration 1 for $\mathit{dpi}_{0}$ to one
that can be reused to tackle $\mathit{dpi}_{1}$ in iteration 2. This update
effectively involves the removal of the redundant nodes (minimal diagnoses for
$\mathit{dpi}_{0}$, indicated by a $\checkmark$) numbered $\scriptsize6⃝$ and
$\scriptsize8⃝$, the reduction of the conflicts numbered $\scriptsize2⃝$ and
$\scriptsize3⃝$ to their proper subsets $\left\langle 2,4\right\rangle$ and
$\left\langle 1,5\right\rangle$ which are now (for $\mathit{dpi}_{1}$) minimal
conflicts, and the reinsertion of node $\tiny10⃝$ into the queue
${\mathbf{Q}}$ (because, after the deletion of the two mentioned redundant
nodes, there is no longer a “witness” diagnosis testifying the non-minimality
of node $\tiny10⃝$).

  2. (Mod2)

Non-minimal diagnoses (test (L1) in HS-Tree) and duplicate nodes (test (L2))
are stored in collections $\mathbf{D}_{\supset}$ and ${\mathbf{Q}}_{dup}$,
respectively, instead of being closed and discarded.
_Justification:_ Property 1.2 suggests to store non-minimal diagnoses, as they
might constitute (sub-branches of) minimal diagnoses in the next iteration.
Property 1.4(a) suggests to record all duplicates for completeness of the
diagnosis search. Because, some active node $\mathsf{nd}$ representing this
duplicate in the current tree could become obsolete due to the shrinkage of
some conflict, and the duplicate might be non-obsolete and eligible to turn
active and replace $\mathsf{nd}$ in the tree.
_Example:_ Node $\scriptsize4⃝$ in iteration 1 of Fig. 3 is added to
${\mathbf{Q}}_{dup}$ (DynamicHS), whereas the corresponding node
$\scriptsize7⃝$ in iteration 1 of Fig. 4 is not further considered (HS-Tree).
Similarly, node $\tiny10⃝$ is stored in $\mathbf{D}_{\supset}$ in case of
DynamicHS (Fig. 3), whereas the same node is simply closed and eliminated in
HS-Tree (Fig. 4).

  3. (Mod3)

Each node $\mathsf{nd}$ is no longer identified as the _set_ of edge labels
from the root to $\mathsf{nd}$, but as an _ordered list_ of these edge labels.
In addition, an ordered list of the conflicts used to label internal nodes
along the branch from the root to $\mathsf{nd}$ is stored in terms of
$\mathsf{nd.cs}$.
_Justification:_ This modification is required due to Property 1.4. The
necessity of storing both the edge labels and the internal node labels as
lists has its reason in the replacement of obsolete tree branches by stored
duplicates. In fact, any duplicate used to replace a node must correspond to
the same _set_ of edge labels as the replaced node. However, in the branch of
the obsolete node, some node-labeling conflict has been reduced to make the
node redundant, whereas for a suitable duplicate replacing the node, no
redundancy-causing changes to conflicts along its branch have occurred. By
storing only sets of edge labels, we could not differentiate between the
redundant and the non-redundant nodes.
_Example:_ For the node $\mathsf{nd}$ at location $\scriptsize9⃝$ in iteration
1 of Fig. 3, we have $\mathsf{nd}=[2,5]$ and $\mathsf{nd.cs}=[\left\langle
1,2\right\rangle,\left\langle 1,3,5\right\rangle]$.

  4. (Mod4)

Before reusing a conflict $\mathcal{C}$ to label a node (labeling test (L3) in
HS-Tree), a minimality check for $\mathcal{C}$ is performed. If a proper
subset $X$ of $\mathcal{C}$ is identified as a conflict for the current DPI in
the course of this check, $X$ is used to prune obsolete tree branches, to
replace node-labeling conflicts that are supersets of $X$ by $X$, and to
update $\mathbf{C}_{calc}$ in that $X$ is added and all of its supersets are
deleted.
_Justification:_ By Property 1.3, stored conflicts in $\mathbf{C}_{calc}$ and
those appearing as labels in the existing tree (elements of the lists
$\mathsf{nd.cs}$ for the different nodes $\mathsf{nd}$) might not be minimal
for the current DPI (since they might have been computed for a prior DPI).
This minimality check helps both to prune the tree (reduction of the number of
nodes) and to make sure that any extension to the tree uses only minimal
conflicts wrt. the current DPI as internal node labels (avoidance of the
introduction of unnecessary new edges).
_Example:_ Let us assume that a new node should be labeled in iteration 2 of
DynamicHS (Fig. 3) and $\mathcal{C}:=\left\langle 3,4,5\right\rangle$ is a
conflict that satisfies the reuse-test (L3). Then the performed minimality
check would return $X:=\left\langle 4,5\right\rangle$ as a subset of
$\mathcal{C}$ (since $\mathcal{C}$ is a minimal conflict for
$\mathit{dpi}_{0}$, but a non-minimal one for $\mathit{dpi}_{1}$, cf. Tab. 2).

  5. (Mod5)

The current state of DynamicHS (in terms of the so-far produced hitting set
tree) is stored over all its iterations executed throughout the sequential
diagnosis process (Alg. 1) by means of the tuple $\mathsf{state}$.
_Justification:_ Statefulness of DynamicHS.
_Example:_ Consider iteration 2 for both HS-Tree (Fig. 4) and DynamicHS (Fig.
3). In the latter case, for the new DPI $\mathit{dpi}_{1}$, the tree built in
iteration 1 is reused, whereas in the former a new one is built. One
implication of this is, e.g., that DynamicHS does not need to (fully)
recompute the conflicts $\left\langle 1,2\right\rangle$, $\left\langle
2,4\right\rangle$ and $\left\langle 1,5\right\rangle$.

Algorithm 3 DynamicHS

1:. tuple
$\left\langle\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld},\mathbf{D}_{\checkmark},\mathbf{D}_{\times},\mathsf{state}\right\rangle$
comprising

  * •

a DPI
$\mathit{dpi}=\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$

  * •

the acquired sets of positive ($\mathit{P}^{\prime}$) and negative
($\mathit{N}^{\prime}$) measurements so far

  * •

a function $\mathit{pr}$ assigning a fault probability to each element in
$\mathcal{K}$

  * •

the number $\mathit{ld}$ of leading minimal diagnoses to be computed

  * •

the set $\mathbf{D}_{\checkmark}$ of all elements of the set
$\mathbf{D}_{calc}$ (returned by the previous dynamicHS run) which are minimal
diagnoses wrt.
$\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$

  * •

the set $\mathbf{D}_{\times}$ of all elements of the set $\mathbf{D}_{calc}$
(returned by the previous dynamicHS run) which are no diagnoses wrt.
$\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$

  * •

$\mathsf{state}=\left\langle{\mathbf{Q}},{\mathbf{Q}}_{dup},\mathbf{D}_{\supset},\mathbf{C}_{\mathit{calc}}\right\rangle$
where

    * –

${\mathbf{Q}}$ is the current queue of unlabeled nodes,

    * –

${\mathbf{Q}}_{dup}$ is the current queue of duplicate nodes,

    * –

$\mathbf{D}_{\supset}$ is the current set of computed non-minimal diagnoses,

    * –

$\mathbf{C}_{calc}$ is the current set of computed minimal conflict sets.

2:tuple $\left\langle\mathbf{D},\mathsf{state}\right\rangle$ where

  * •

$\mathbf{D}$ is the set of the $\mathit{ld}$ (if existent) most probable (as
per $\mathit{pr}$) minimal diagnoses wrt.
$\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle$

  * •

$\mathsf{state}$ is as described above

3:procedure
dynamicHS($\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathit{ld},\mathbf{D}_{\checkmark},\mathbf{D}_{\times},\mathsf{state}$)

4: $\mathbf{D}_{calc}\leftarrow\emptyset$

5:
$\mathsf{state}\leftarrow\textsc{updateTree}(\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathbf{D}_{\checkmark},\mathbf{D}_{\times},\mathsf{state})$

6: while
${\mathbf{Q}}\neq[\,]\land\left(\;|\mathbf{D}_{calc}|<\mathit{ld}\;\right)$ do

7: $\mathsf{node}\leftarrow\textsc{getAndDeleteFirst}({\mathbf{Q}})$
$\triangleright$ $\mathsf{node}$ is processed

8: if $\mathsf{node}\in\mathbf{D}_{\checkmark}$ then $\triangleright$
$\mathbf{D}_{\checkmark}$ includes only min…

9: $L\leftarrow\mathit{valid}$ $\triangleright$ …diags wrt. current DPI

10: else

11: $\left\langle
L,\mathsf{state}\right\rangle\leftarrow\textsc{dLabel}(\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathsf{node},\mathbf{D}_{calc},\mathsf{state})$

12: if $L=\mathit{valid}$ then

13:
$\mathbf{D}_{calc}\leftarrow\mathbf{D}_{calc}\cup\left\\{\mathsf{node}\right\\}$
$\triangleright$ $\mathsf{node}$ is a min diag wrt. current DPI

14: else if $L=\mathit{nonmin}$ then

15:
$\mathbf{D}_{\supset}\leftarrow\mathbf{D}_{\supset}\cup\left\\{\mathsf{node}\right\\}$
$\triangleright$ $\mathsf{node}$ is a non-min diag wrt. current DPI

16: else

17: for $e\in L$ do $\triangleright$ $L$ is a min conflict wrt. current DPI

18: $\mathsf{node}_{e}\leftarrow\textsc{append}(\mathsf{node},e)$
$\triangleright$ $\mathsf{node}_{e}$ is generated

19:
$\mathsf{node}_{e}.\mathsf{cs}\leftarrow\textsc{append}(\mathsf{node.cs},L)$

20: if
$\mathsf{node}_{e}\in{\mathbf{Q}}\lor\mathsf{node}_{e}\in\mathbf{D}_{\supset}$
then $\triangleright$ $\mathsf{node}_{e}$ is (_set-equal_) duplicate of some
node in ${\mathbf{Q}}$ or $\mathbf{D}_{\supset}$

21:
${\mathbf{Q}}_{dup}\leftarrow\textsc{insertSorted}(\mathsf{node}_{e},{\mathbf{Q}}_{dup},\mathit{card},<)$

22: else

23:
${\mathbf{Q}}\leftarrow\textsc{insertSorted}(\mathsf{node}_{e},{\mathbf{Q}},\mathit{pr},>)$

24: return $\left\langle\mathbf{D}_{calc},\mathsf{state}\right\rangle$

25:procedure
dLabel($\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle,\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathsf{node},\mathbf{D}_{calc},\mathsf{state}$)

26: for $\mathsf{nd}\in\mathbf{D}_{calc}$ do

27: if $\mathsf{node}\supset\mathsf{nd}$ then $\triangleright$ $\mathsf{node}$
is a non-min diag

28: return $\left\langle\mathit{nonmin},\mathsf{state}\right\rangle$

29: for $\mathcal{C}\in\mathbf{C}_{calc}$ do $\triangleright$
$\mathbf{C}_{calc}$ includes conflicts wrt. current DPI

30: if $\mathcal{C}\cap\mathsf{node}=\emptyset$ then $\triangleright$ reuse (a
subset of) $\mathcal{C}$ to label $\mathsf{node}$

31:
$X\leftarrow\textsc{findMinConflict}(\langle\mathcal{C},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle)$

32: if $X=\mathcal{C}$ then

33: return $\left\langle\mathcal{C},\mathsf{state}\right\rangle$

34: else$\triangleright$ $X\subset\mathcal{C}$

35:
$\left\langle\mathsf{state},\mathbf{D}_{calc}\right\rangle\leftarrow\textsc{prune}(X,\\{\mathsf{state},\mathbf{D}_{calc}\\})$

36: return $\left\langle X,\mathsf{state}\right\rangle$

37:
$L\leftarrow\textsc{findMinConflict}(\langle\mathcal{K}\setminus\mathsf{node},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle)$

38: if $L$ = ’no conflict’ then $\triangleright$ $\mathsf{node}$ is a diag

39: return $\left\langle\mathit{valid},\mathsf{state}\right\rangle$

40: else$\triangleright$ $L$ is a _new_ min conflict
($\notin\mathbf{C}_{calc}$)

41: $\mathbf{C}_{calc}\leftarrow\mathbf{C}_{calc}\cup\left\\{L\right\\}$

42: return $\left\langle L,\mathsf{state}\right\rangle$

Algorithm 3 DynamicHS (continued)

43:procedure
updateTree($\mathit{dpi},\mathit{P}^{\prime},\mathit{N}^{\prime},\mathit{pr},\mathbf{D}_{\checkmark},\mathbf{D}_{\times},\mathsf{state}$)

44: for $\mathsf{nd}\in\mathbf{D}_{\times}$ do $\triangleright$ search for
redundant nodes among invalidated diags

45: if $\textsc{redundant}(\mathsf{nd},\mathit{dpi})$ then

46:
$\left\langle\mathsf{state},\mathbf{D}_{\checkmark},\mathbf{D}_{\times}\right\rangle\leftarrow\textsc{prune}(X,\\{\mathsf{state},\mathbf{D}_{\checkmark},\mathbf{D}_{\times}\\})$

47: for $\mathsf{nd}\in\mathbf{D}_{\times}$ do $\triangleright$ add all (non-
pruned) nodes in $\mathbf{D}_{\times}$ to ${\mathbf{Q}}$

48:
${\mathbf{Q}}\leftarrow\textsc{insertSorted}(\mathsf{nd},{\mathbf{Q}},\mathit{pr},>)$

49:
$\mathbf{D}_{\times}\leftarrow\mathbf{D}_{\times}\setminus\left\\{\mathsf{nd}\right\\}$

50: for $\mathsf{nd}\in\mathbf{D}_{\supset}$ do $\triangleright$ add all (non-
pruned) nodes in $\mathbf{D}_{\supset}$ to ${\mathbf{Q}}$, which…

51: $\mathit{nonmin}\leftarrow\mathit{false}$ $\triangleright$ …are no longer
supersets of any diag in $\mathbf{D}_{\checkmark}$

52: for $\mathsf{nd}^{\prime}\in\mathbf{D}_{\checkmark}$ do

53: if $\mathsf{nd}\supset\mathsf{nd}^{\prime}$ then

54: $\mathit{nonmin}\leftarrow\mathit{true}$

55: break

56: if $\mathit{nonmin}=\mathit{false}$ then

57:
${\mathbf{Q}}\leftarrow\textsc{insertSorted}(\mathsf{nd},{\mathbf{Q}},\mathit{pr},>)$

58:
$\mathbf{D}_{\supset}\leftarrow\mathbf{D}_{\supset}\setminus\left\\{\mathsf{nd}\right\\}$

59: for $\mathcal{D}\in\mathbf{D}_{\checkmark}$ do $\triangleright$ add known
min diags in $\mathbf{D}_{\checkmark}$ to ${\mathbf{Q}}$ to find diags…

60:
${\mathbf{Q}}\leftarrow\textsc{insertSorted}(\mathcal{D},{\mathbf{Q}},\mathit{pr},>)$
$\triangleright$ …in best-first order (as per $\mathit{pr}$)

61: return $\mathsf{state}$

####  3.2.5 DynamicHS: Algorithm Walkthrough

We now explicate the workings of DynamicHS, depicted by Alg. 3.

Like HS-Tree, DynamicHS is basically processing a priority queue
${\mathbf{Q}}$ of nodes (while-loop; lines 6 and 7). That is, in each
iteration of the while-loop, the top-ranked node $\mathsf{node}$ is removed
from ${\mathbf{Q}}$ to be labeled (getAndDeleteFirst). Before calling the
labeling function (dLabel), however, the algorithm checks if $\mathsf{node}$
is among the already computed minimal diagnoses $\mathbf{D}_{\checkmark}$ from
the previous iteration which are consistent with all measurements in
$\mathit{P}^{\prime}\cup\mathit{N}^{\prime}$ (line 8). If so, the node is
directly labeled $\mathit{valid}$ (line 9). Otherwise the dLabel function is
invoked to compute a label for $\mathsf{node}$ (line 11).

dLabel: First, the non-minimality check is performed, just as done in HS-Tree,
see (L1) above (lines 26–28). If the check is negative, a conflict-reuse check
is carried out next (lines 29–36). Note that the duplicate check (L2), which
is done at this stage in HS-Tree, is obsolete since no duplicate nodes can
ever be elements of ${\mathbf{Q}}$. This is evaded by directly making the
duplicate check after new nodes have been constructed and are to be added to
${\mathbf{Q}}$ (see lines 20 and 21). The conflict-reuse check starts equally
as in HS-Tree. However, if a suitable conflict $\mathcal{C}$ for reuse is
found in the set of so-far computed conflicts $\mathbf{C}_{calc}$ (line 30),
then findMinConflict (cf. (L4) above) is employed to check the minimality of
the conflict wrt. the _current_ DPI (line 31). If a proper subset $X$ of
$\mathcal{C}$ is found which is a conflict wrt. the current DPI (line 34),
then $X$ is used to prune the current hitting set tree (line 35) using the
prune function (see below). Finally, depending on the minimality check, either
the conflict $\mathcal{C}$ from $\mathbf{C}_{calc}$, if minimal, or the
computed subset $X$ of $\mathcal{C}$ is used to label $\mathsf{node}$ (lines
33 and 36). In case no conflict is eligible for being reused, findMinConflict
is called (line 37) to test if a minimal conflict (wrt. the current DPI) to
label $\mathsf{node}$ exists at all, or if $\mathsf{node}$ already corresponds
to a (minimal) diagnosis wrt. the current DPI (again, this part, i.e., lines
37–42, is equal to HS-Tree, cf. (L4) above). As a last point, note that dLabel
gets and returns the tuple $\mathsf{state}$ as an argument. This tuple
includes collections of nodes storing the current state of the hitting set
tree maintained by DynamicHS. The reason for passing $\mathsf{state}$ to
dLabel is that the pruning actions potentially performed in the course of the
reuse-check might modify $\mathsf{state}$ (while all other actions executed
during dLabel can never alter $\mathsf{state}$).

The output of dLabel is then processed by DynamicHS (lines 12–24) in order to
assign $\mathsf{node}$ to its appropriate node collection (note that the
labels of processed nodes are implicitly stored by assigning the nodes to
corresponding collections). More specifically, $\mathsf{node}$ is assigned to
$\mathbf{D}_{calc}$ if the returned label is $\mathit{valid}$ (line 13), and
to $\mathbf{D}_{\supset}$ if the label is $\mathit{nonmin}$ (line 15). If, on
the other hand, the label is a minimal conflict $L$, then a child node
$\mathsf{node}_{e}$ is created for each element $e\in L$ and assigned to
either ${\mathbf{Q}}_{dup}$ (line 21) if there is a node in ${\mathbf{Q}}$ or
in $\mathbf{D}_{\supset}$ that is _set_ -equal to $\mathsf{node}_{e}$, or to
${\mathbf{Q}}$ otherwise (line 23). At this, $\mathsf{node}_{e}$ is
constructed from $\mathsf{node}$ via the append function (lines 18 and 19),
which appends the element $e$ to the list $\mathsf{node}$, and the conflict
$L$ to the list $\mathsf{node.cs}$ (cf. (Mod3) above). Note that both
${\mathbf{Q}}$ and ${\mathbf{Q}}_{dup}$ are priority queues. ${\mathbf{Q}}$ is
ordered by descending node probability as per the given measure $\mathit{pr}$,
and ${\mathbf{Q}}_{dup}$ by ascending node cardinality, i.e., nodes with fewer
edge labels along their branch from the root node are prioritized. The reason
for this will become fully evident when we discuss the prune function (see
below).

The described processing of nodes from ${\mathbf{Q}}$ is successively
continued until one of the stop criteria applies (while-loop, line 6). That
is, the algorithm returns the set of computed minimal diagnoses
$\mathbf{D}_{calc}$ along with the current tree state $\mathsf{state}$ when
either all nodes have been processed (${\mathbf{Q}}=[\,]$), i.e., the tree has
been built to its entirety, or when the stipulated number $\mathit{ld}$ of
leading diagnoses have been found ($|\mathbf{D}_{calc}|=\mathit{ld}$).

updateTree: The idea here is to adapt the current tree in a way it constitutes
a basis for finding all and only minimal diagnoses in highest-probability-
first order for the _current_ DPI. As discussed above, the minimal diagnoses
can only remain the same or be augmented in size (Property 1.2), whereas for
existing conflicts it is the case that they can only remain the same or shrink
in size (Property 1.3), or new conflicts can arise (Property 1.4). The
principle followed by updateTree is to search for non-minimal conflicts to be
updated, and tree branches to be pruned, among the nodes that corresponded to
minimal diagnoses for the previous DPI, but have been invalidated by the
latest added measurement (the elements of $\mathbf{D}_{\times}$, cf. line 16
in Alg. 1).

Regarding the pruning of tree branches, we call a node $\mathsf{nd}$
_redundant_ (wrt. a DPI $\mathit{dpi}$) iff there is some index $j$ and a
minimal conflict $X$ wrt. $\mathit{dpi}$ such that the conflict
$\mathsf{nd.cs}[j]\supset X$ and the element
$\mathsf{nd}[j]\in\mathsf{nd.cs}[j]\setminus X$.171717 By $\mathsf{nd}[j]$ and
$\mathsf{nd.cs}[j]$, respectively, we refer to the $j$-th element of the
ordered lists $\mathsf{nd}$ and $\mathsf{nd.cs}$ (cf. (Mod3) above), i.e., to
the $j$-th edge label and to the $j$-th conflict along node $\mathsf{nd}$’s
branch starting from the root. Moreover, we call $X$ a _witness of redundancy
for $\mathsf{nd}$_ (wrt. $\mathit{dpi}$). In simple words, $\mathsf{nd}$ is
redundant iff the branch from the root node to $\mathsf{nd}$ would not exist
given that the (current) minimal conflict $X$ had been used instead of the
(old, formerly minimal, but by now) non-minimal conflict $\mathsf{nd.cs}[j]$.

If such a redundant node is detected among the elements of
$\mathbf{D}_{\times}$ (function redundant, drawing on call(s) to
findMinConflict; explained in detail later), then the prune function (see
later) is called given the witness of redundancy of the redundant node as an
argument (lines 44–46). After each node in $\mathbf{D}_{\times}$ has been
processed,181818Note that $\mathbf{D}_{\times}$ itself might change during the
execution of the tree pruning (line 46) in that redundant nodes might be
deleted from it and corresponding replacement nodes (constructed) from the
stored duplicates might be added to it. Thus, the semantics of the for-loop in
line 44 is that it stops iff each node in $\mathbf{D}_{\times}$ _at the
present time_ has been processed. the remaining nodes in $\mathbf{D}_{\times}$
(those that are non-redundant and thus have not been pruned) are re-added to
${\mathbf{Q}}$ in prioritized order according to $\mathit{pr}$ (lines 47–49),
as accomplished by the function insertSorted. Likewise, all non-pruned nodes
in $\mathbf{D}_{\supset}$ (note that pruning always considers all collections
${\mathbf{Q}}_{dup}$, ${\mathbf{Q}}$, $\mathbf{D}_{\checkmark}$,
$\mathbf{D}_{\times}$ and $\mathbf{D}_{\supset}$) which are no longer
supersets of any _known_ minimal diagnosis, are added to ${\mathbf{Q}}$ again
(lines 50–58). Finally, the known minimal diagnoses that have been returned by
the previous execution of DynamicHS and are consistent with the latest added
measurement (the elements of $\mathbf{D}_{\checkmark}$), are put back to the
ordered queue ${\mathbf{Q}}$. The justification for this step is given by the
fact that, for the current DPI, there might be “new” minimal diagnoses that
are more probable than the ones known from the previous iteration. Omitting
this step therefore would (generally) compromise the best-first property of
the hitting set computation.

prune: Using its first argument $X$, the function runs through the node
collections ${\mathbf{Q}}_{dup}$, ${\mathbf{Q}}$, $\mathbf{D}_{\supset}$ and
$\mathbf{D}_{calc}$ when called in line 35, and through ${\mathbf{Q}}_{dup}$,
${\mathbf{Q}}$, $\mathbf{D}_{\supset}$, $\mathbf{D}_{\times}$ and
$\mathbf{D}_{\checkmark}$ when called in line 46 (cf. second argument), and

  * •

_(relabeling of old conflicts)_ replaces all labels $\mathsf{nd.cs}[i]$ which
are proper supersets of $X$ by $X$ for all nodes $\mathsf{nd}$ and for all
$i=1,\dots,|\mathsf{nd}|$, and

  * •

_(deletion of redundant nodes)_ deletes each redundant node $\mathsf{nd}$ for
which $X$ is a witness of redundancy, and

  * •

_(potential replacement of deleted nodes)_ for each of the deleted nodes
$\mathsf{nd}$, if available, uses a suitable (non-redundant) node
$\mathsf{nd}^{\prime}$ (constructed) from the elements of ${\mathbf{Q}}_{dup}$
to replace $\mathsf{nd}$ by $\mathsf{nd}^{\prime}$.

A node $\mathsf{nd}^{\prime}$ qualifies as a _replacement node for
$\mathsf{nd}$_ iff $\mathsf{nd}^{\prime}$ is non-redundant and has the same
_set_ of edge labels along its branch from the root node as $\mathsf{nd}$,
i.e., iff $\mathsf{nd}$ is set-equal (not equal in terms of the list of edge
labels) to $\mathsf{nd}^{\prime}$. This node replacement is necessary from the
point of view of completeness (cf. (?)). Importantly, ${\mathbf{Q}}_{dup}$
must be pruned before the other collections of nodes (${\mathbf{Q}}$,
$\mathbf{D}_{\supset}$, $\mathbf{D}_{\times}$, $\mathbf{D}_{\checkmark}$,
$\mathbf{D}_{calc}$) are pruned, to guarantee that all nodes in
${\mathbf{Q}}_{dup}$ represent possible _non-redundant_ replacement nodes when
it comes to pruning nodes from these collections.

Additionally, the argument $X$ is used to update the conflicts stored for
reuse (set $\mathbf{C}_{calc}$). The principle is to run through
$\mathbf{C}_{calc}$ once, while deleting all proper supersets of $X$, and to
finally add $X$ to $\mathbf{C}_{calc}$.

$\textstyle{\scriptsize1⃝\langle
1,2\rangle^{C}}$$\textstyle{\scriptsize2⃝\langle
2,3,4\rangle^{C}}$$\scriptstyle{1}$$\textstyle{\scriptsize3⃝\langle
1,3,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\scriptsize5⃝\langle
3,4,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\scriptsize6⃝\checkmark_{(\mathcal{D}_{1})}^{*}}$$\scriptstyle{3}$$\textstyle{\scriptsize7⃝\checkmark_{(\mathcal{D}_{2})}^{*}}$$\scriptstyle{4}$$\textstyle{\scriptsize4⃝dup}$$\scriptstyle{1}$$\textstyle{\scriptsize8⃝\checkmark_{(\mathcal{D}_{3})}^{*}}$$\scriptstyle{3}$$\textstyle{\scriptsize9⃝\checkmark_{(\mathcal{D}_{4})}^{*}}$$\scriptstyle{5}$$\textstyle{\tiny10⃝\times_{(\supset\mathcal{D}_{1})}}$$\scriptstyle{3}$$\textstyle{\tiny11⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny12⃝\times_{(\supset\mathcal{D}_{4})}}$$\scriptstyle{5}$

iteration 1 ($\mathit{dpi}_{0}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4}\\}$
$\qquad\Rightarrow m_{1}:\,A\to C\phantom{\lnot}\;$ to $\mathit{N}^{\prime}$
$\qquad\Rightarrow\mathbf{D}_{\checkmark}=\\{\mathcal{D}_{2},\mathcal{D}_{4}\\},\mathbf{D}_{\times}=\\{\mathcal{D}_{1},\mathcal{D}_{3}\\}$

[0.5ex]1pt3mm

$\textstyle{\scriptsize1⃝\langle 1,2\rangle}$$\textstyle{\scriptsize2'⃝\langle
2,4\rangle}$$\scriptstyle{1}$$\textstyle{\scriptsize3'⃝\langle
1,5\rangle}$$\scriptstyle{2}$$\textstyle{\scriptsize5⃝\langle
3,4,5\rangle}$$\scriptstyle{2}$$\textstyle{\scriptsize7⃝\checkmark_{(\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\scriptsize4⃝dup}$$\scriptstyle{1}$$\textstyle{\scriptsize9⃝\checkmark_{(\mathcal{D}_{4})}}$$\scriptstyle{5}$$\textstyle{\tiny13⃝\langle
4,5\rangle^{C}}$$\scriptstyle{3}$$\textstyle{\tiny11⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny12⃝\times_{(\supset\mathcal{D}_{4})}}$$\scriptstyle{5}$$\textstyle{\tiny14⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny15⃝\times_{(\supset\mathcal{D}_{4})}}$$\scriptstyle{5}$

iteration 2 ($\mathit{dpi}_{1}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2},\mathcal{D}_{4}\\}$
$\qquad\Rightarrow m_{2}:\;\,A\to\lnot B\phantom{\lnot}\;$ to
$\mathit{N}^{\prime}$
$\qquad\Rightarrow\mathbf{D}_{\checkmark}=\\{\mathcal{D}_{2}\\},\mathbf{D}_{\times}=\\{\mathcal{D}_{4}\\}$

[0.5ex]1pt3mm

$\textstyle{\scriptsize1'⃝\langle 1\rangle}$$\textstyle{\scriptsize2'⃝\langle
2,4\rangle}$$\scriptstyle{1}$$\textstyle{\scriptsize5⃝\langle
3,4,5\rangle}$$\scriptstyle{2}$$\textstyle{\scriptsize7⃝\checkmark_{(\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny13⃝\langle
4,5\rangle}$$\scriptstyle{3}$$\textstyle{\tiny11⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny16⃝\langle
3,4\rangle^{C}}$$\scriptstyle{5}$$\textstyle{\tiny14⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny18⃝\checkmark_{(\mathcal{D}_{5})}^{*}}$$\scriptstyle{5}$$\textstyle{\tiny17⃝dup}$$\scriptstyle{3}$$\textstyle{\tiny19⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$

iteration 3 ($\mathit{dpi}_{2}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2},\mathcal{D}_{5}\\}$
$\quad\Rightarrow m_{3}:\;\,A\to\lnot C\phantom{\lnot}\;$ to
$\mathit{P}^{\prime}$
$\qquad\Rightarrow\mathbf{D}_{\checkmark}=\\{\mathcal{D}_{2}\\},\mathbf{D}_{\times}=\\{\mathcal{D}_{5}\\}$

[0.5ex]1pt3mm

$\textstyle{\scriptsize1'⃝\langle 1\rangle}$$\textstyle{\scriptsize2''⃝\langle
4\rangle}$$\scriptstyle{1}$$\textstyle{\scriptsize7⃝\checkmark_{(\mathcal{D}_{2})}}$$\scriptstyle{4}$

iteration 4 ($\mathit{dpi}_{3}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2}\\}$

[0.5ex]1pt3mm

Figure 3: DynamicHS executed on example DPI given in Tab. 1.

$\textstyle{\scriptsize1⃝\langle
1,2\rangle^{C}}$$\textstyle{\scriptsize2⃝\langle
2,3,4\rangle^{C}}$$\scriptstyle{1}$$\textstyle{\scriptsize3⃝\langle
1,3,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\scriptsize4⃝\langle
3,4,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\scriptsize5⃝\checkmark_{(\mathcal{D}_{1})}^{*}}$$\scriptstyle{3}$$\textstyle{\scriptsize6⃝\checkmark_{(\mathcal{D}_{2})}^{*}}$$\scriptstyle{4}$$\textstyle{\scriptsize7⃝\times}$$\scriptstyle{1}$$\textstyle{\scriptsize8⃝\checkmark_{(\mathcal{D}_{3})}^{*}}$$\scriptstyle{3}$$\textstyle{\scriptsize9⃝\checkmark_{(\mathcal{D}_{4})}^{*}}$$\scriptstyle{5}$$\textstyle{\tiny10⃝\times_{(\supset\mathcal{D}_{1})}}$$\scriptstyle{3}$$\textstyle{\tiny11⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny12⃝\times_{(\supset\mathcal{D}_{4})}}$$\scriptstyle{5}$

iteration 1 ($\mathit{dpi}_{0}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4}\\}$
$\qquad\Rightarrow m_{1}:\;\,A\to C\phantom{\lnot}\;$ to $\mathit{N}^{\prime}$

[0.5ex]1pt3mm

$\textstyle{\tiny13⃝\langle 1,2\rangle^{C}}$$\textstyle{\tiny14⃝\langle
2,4\rangle^{C}}$$\scriptstyle{1}$$\textstyle{\tiny15⃝\langle
1,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\tiny16⃝\langle
4,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\tiny17⃝\checkmark_{(\mathcal{D}_{2})}^{*}}$$\scriptstyle{4}$$\textstyle{\tiny18⃝\times}$$\scriptstyle{1}$$\textstyle{\tiny19⃝\checkmark_{(\mathcal{D}_{4})}^{*}}$$\scriptstyle{5}$$\textstyle{\tiny20⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny21⃝\times_{(\supset\mathcal{D}_{4})}}$$\scriptstyle{5}$

iteration 2 ($\mathit{dpi}_{1}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2},\mathcal{D}_{4}\\}$
$\qquad\Rightarrow m_{2}:\;\,A\to\lnot B\phantom{\lnot}\;$ to
$\mathit{N}^{\prime}$

[0.5ex]1pt3mm

$\textstyle{\tiny22⃝\langle 1\rangle^{C}}$$\textstyle{\tiny23⃝\langle
2,4\rangle^{C}}$$\scriptstyle{1}$$\textstyle{\tiny24⃝\langle
4,5\rangle^{C}}$$\scriptstyle{2}$$\textstyle{\tiny25⃝\checkmark_{(\mathcal{D}_{2})}^{*}}$$\scriptstyle{4}$$\textstyle{\tiny26⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$$\textstyle{\tiny27⃝\langle
3,4\rangle^{C}}$$\scriptstyle{5}$$\textstyle{\tiny28⃝\checkmark_{(\mathcal{D}_{5})}^{*}}$$\scriptstyle{3}$$\textstyle{\tiny29⃝\times_{(\supset\mathcal{D}_{2})}}$$\scriptstyle{4}$

iteration 3 ($\mathit{dpi}_{2}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2},\mathcal{D}_{5}\\}$
$\quad\Rightarrow m_{3}:\;\,A\to\lnot C\phantom{\lnot}\;$ to
$\mathit{P}^{\prime}$

[0.5ex]1pt3mm

$\textstyle{\tiny30⃝\langle 1\rangle^{C}}$$\textstyle{\tiny31⃝\langle
4\rangle^{C}}$$\scriptstyle{1}$$\textstyle{\tiny32⃝\checkmark_{(\mathcal{D}_{2})}^{*}}$$\scriptstyle{4}$

iteration 4 ($\mathit{dpi}_{3}$)
$\qquad\Rightarrow\mathbf{D}=\\{\mathcal{D}_{2}\\}$

[0.5ex]1pt3mm

Figure 4: HS-Tree executed on example DPI given in Tab. 1.

Example 5 Consider our example DPI $\mathit{dpi}_{0}$ given in Tab. 1. The
goal is the localization of the faulty axioms, i.e., of those elements of
$\mathcal{K}$ that prevent the satisfaction of all given measurements (in this
case, there is only one negative measurement, i.e., $\lnot A$ must not be
entailed by the correct knowledge base). We now illustrate the workings of
both DynamicHS (Fig. 3) and HS-Tree (Fig. 4) in that we play through a
complete sequential diagnosis session on this particular example, under the
assumption that $\mathcal{D}^{*}=[\mathit{ax}_{1},\mathit{ax}_{4}]$ is the
actual diagnosis.

_Inputs (Sequential Diagnosis):_ Concerning the inputs to Alg. 1, we assume
that $\mathit{ld}:=5$ (i.e., in each iteration, if existent, five leading
diagnoses are computed), $\mathsf{heur}$ is a heuristic that prefers
measurements the more, the more leading diagnoses they eliminate in the worst
case (cf. the split-in-half heuristic in (?)), and $\mathit{pr}$ is chosen in
a way all elements of $\mathcal{K}$ have an equal fault probability which
leads to a breadth-first construction of the hitting set tree(s).

_Inputs (HS-Tree and DynamicHS):_ The inputs to Alg. 1 are passed to DynamicHS
in line 8. In addition to these, DynamicHS (see Alg. 3) accepts the arguments
$\mathit{P}^{\prime}$, $\mathit{N}^{\prime}$ (current sets of positive and
negative measurements gathered throughout the execution of Alg. 1 so far; both
initially empty), $\mathbf{D}_{\checkmark}$ and $\mathbf{D}_{\times}$ (the
minimal diagnoses found in the previous iteration which are consistent and
inconsistent, respectively, with the last added measurement; both initially
empty), and $\mathsf{state}$ (stores the state of the current DynamicHS-Tree
within and between all its iterations) which consists of the collections
${\mathbf{Q}}$ (list of open nodes; initially the list containing an empty
node $[\,]$), ${\mathbf{Q}}_{dup}$ (list of duplicate nodes; initially empty),
$\mathbf{D}_{\supset}$ (set of non-minimal diagnoses; initially empty), as
well as $\mathbf{C}_{calc}$ (set of already computed conflicts; initially
empty). These variable initializations take place in lines 3–5 of Alg. 1.
Unlike DynamicHS, HS-Tree takes only the arguments $\mathit{P}^{\prime}$ and
$\mathit{N}^{\prime}$ beyond the general sequential diagnosis inputs
$\mathit{ld}$, $\mathit{pr}$ and $\mathsf{heur}$. That is, the queue
${\mathbf{Q}}$, the computed diagnoses $\mathbf{D}_{calc}$, and the computed
conflicts $\mathbf{C}_{calc}$ are instance variables in case of HS-Tree due to
its statelessness.

_Notation in Figures:_ Axioms $\mathit{ax}_{i}$ in $\mathcal{K}$ are referred
to by $i$ (in node and edge labels) for simplicity. Circled numbers indicate
the chronological order in which nodes are labeled, i.e., node $\scriptsizei⃝$
is labeled at point in time $i$ (starting from $1$). We use
$\left\langle\dots\right\rangle$ to denote the conflicts that label the
internal hitting set tree nodes, and tag these conflicts by C if they are
freshly computed by a findMinConflict call (line 37 in dLabel), and leave them
without a tag if they are the product of a redundancy check and a subsequent
relabeling (lines 45–46 in updateTree).191919The rationale behind this
distinction between the individual conflicts used as node labels is that their
computation time tends to differ significantly (as we will discuss in more
detail in Sec. 5.4.2). For that reason, we will later also denote the
operations used to compute the conflicts tagged by C as “hard”, and those that
yield conflicts without any tag as “easy” (see Sec. 3.3.3).202020Note that
there are no reused conflicts (found in lines 29–36 in dLabel) in this
particular example. Therefore, we do not introduce a distinct conflict tag for
this case. For the leaf nodes, we use the following labels:
$\checkmark_{(\mathcal{D}_{i})}$ to denote a minimal diagnosis, named
$\mathcal{D}_{i}$, stored in $\mathbf{D}_{calc}$, $\times$ to denote a
duplicate in HS-Tree (see (L2) criterion above),
$\times_{(\supset\mathcal{D}_{i})}$ to denote a non-minimal diagnosis (stored
in $\mathbf{D}_{\supset}$ by DynamicHS), where $\mathcal{D}_{i}$ is some
minimal diagnosis that proves the non-minimality, and $\mathit{dup}$ to denote
a duplicate in DynamicHS (stored in ${\mathbf{Q}}_{dup}$). Branches
representing minimal diagnoses are additionally tagged by a ∗ if logical
reasoning (findMinConflict call, line 37 in DynamicHS, and line 27 in HS-Tree)
is necessary to prove it is a diagnosis, and untagged otherwise (i.e., the
branch is known to be a diagnosis from a previous iteration, and stored in
$\mathbf{D}_{\checkmark}$; only pertinent to DynamicHS). Below each graph
showing the respective hitting set tree, the figures show the current
iteration $i$ of Alg. 1, the leading diagnoses $\mathbf{D}$ output (Alg. 1,
line 8 for DynamicHS and line 10 for HS-Tree, respectively), the measurement
$m_{i}$ added to one of the measurement sets ($\mathit{P}^{\prime}$ or
$\mathit{N}^{\prime}$) of the the DPI (Alg. 1, lines 12–14), as well as the
sets $\mathbf{D}_{\checkmark}$ and $\mathbf{D}_{\times}$ (Alg. 1, line 16) in
case of DynamicHS.

_Iteration 1:_ In their first iteration, HS-Tree and DynamicHS essentially do
the same, i.e., they build the same tree (compare Figs. 3 and 4). The only
difference is that DynamicHS stores the duplicate branches (labeled by
$\mathit{dup}$) and the ones corresponding to non-minimal diagnoses (labeled
by $\times_{(\supset\mathcal{D}_{i})}$), whereas HS-Tree simply discards these
branches (those labeled by $\times$ or $\times_{(\supset\mathcal{D}_{i})}$).
Note that duplicates are stored by DynamicHS at _generation_ time (line 21),
hence the duplicate ($\mathit{dup}$) found has number \scriptsize4⃝ (and not
\scriptsize7⃝, as the respective branch for HS-Tree). The leading diagnoses
computed by both algorithms are
$\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4}\\}=\\{[1,3],[1,4],[2,3],[2,5]\\}$.
The soundness and completeness of this result can also be read from Tab. 2
which illustrates the evolution of the minimal diagnoses ($\mathbf{diag}$) and
minimal conflicts ($\mathbf{conf}$) for the varying DPI (successively extended
$\mathit{P}^{\prime}$ and $\mathit{N}^{\prime}$ sets) in this example. We
emphasize that the leading diagnoses returned by both algorithms _must_ be
equal in any iteration (given the same parameters $\mathit{ld}$ and
$\mathit{pr}$) since both methods are sound, complete and best-first minimal
diagnosis computers. As a consequence, when using the same measurement
computation technique (and heuristic $\mathsf{heur}$), both algorithms also
_must_ give rise to the same proposed next measurement $m_{i}$ in each
iteration.

Table 2: Evolution of minimal diagnoses and minimal conflicts after successive extension of the example DPI $\mathit{dpi}_{0}$ (Tab. 1) by positive ($\mathit{P}^{\prime}$) or negative ($\mathit{N}^{\prime}$) measurements $m_{i}$ shown in Figures 3 and 4, respectively. Newly arisen minimal conflicts (which are neither subsets nor supersets of prior minimal conflicts) are underlined. iteration $j$ | $\mathit{P}^{\prime}$ | $\mathit{N}^{\prime}$ | $\mathbf{diag}(\mathit{dpi}_{j-1})$ | $\mathbf{conf}(\mathit{dpi}_{j-1})$
---|---|---|---|---
1 | – | – | $[1,3],[1,4],[2,3],[2,5]$ | $\left\langle 1,2\right\rangle,\left\langle 2,3,4\right\rangle,\left\langle 1,3,5\right\rangle,\left\langle 3,4,5\right\rangle$
2 | – | $A\to C$ | $[1,4],[2,5]$ | $\left\langle 1,2\right\rangle,\left\langle 2,4\right\rangle,\left\langle 1,5\right\rangle,\left\langle 4,5\right\rangle$
3 | – | $A\to C,\;A\to\lnot B$ | $[1,4],[1,2,3,5]$ | $\left\langle 1\right\rangle,\left\langle 2,4\right\rangle,\underline{\left\langle 3,4\right\rangle},\left\langle 4,5\right\rangle$
4 | $A\to\lnot C$ | $A\to C,\;A\to\lnot B$ | $[1,4]$ | $\left\langle 1\right\rangle,\left\langle 4\right\rangle$

_First Measurement:_ Accordingly, both algorithms lead to the first
measurement $m_{1}:A\to C$, which corresponds to the question “must it be true
that $A$ implies $C$?”. This measurement turns out to be negative, e.g., by
consulting a knowledgeable expert for the domain described by $\mathcal{K}$,
and is therefore added to $\mathit{N}^{\prime}$. This effectuates a transition
from the initial DPI $\mathit{dpi}_{0}$ to a new DPI $\mathit{dpi}_{1}$ (which
includes the additional element $A\to C$ in $\mathit{N}^{\prime}$), and thus a
change of the relevant minimal diagnoses and conflicts (see Tab. 2).

_Tree Update:_ From the second iteration (where $\mathit{dpi}_{1}$ is
considered) on, the behaviors of DynamicHS and HS-Tree start to differ.
Whereas HS-Tree simply constructs a new hitting set tree from scratch for
$\mathit{dpi}_{1}$, DynamicHS runs a tree update (function updateTree) to make
the existing tree built for $\mathit{dpi}_{0}$ reusable for
$\mathit{dpi}_{1}$. In the course of this tree update, two witnesses of
redundancy (the new minimal conflicts $\left\langle 2,4\right\rangle$ and
$\left\langle 1,5\right\rangle$) are found while analyzing the (conflicts
along the) branches of the two invalidated diagnoses $[1,3]$ and $[2,3]$
(\scriptsize6⃝ and \scriptsize8⃝). For instance, $\mathsf{nd}=[1,3]$ is
redundant since the (_former_ , for $\mathit{dpi}_{0}$, _minimal_) conflict
$\mathsf{nd.cs}[2]=\left\langle 2,3,4\right\rangle$ is a proper superset of
the _now minimal_ conflict $X=\left\langle 2,4\right\rangle$ _and_
$\mathsf{nd}$’s outgoing edge of $\mathsf{nd.cs}[2]$ is $\mathsf{nd}[2]=3$
which is an element of $\mathsf{nd.cs}[2]\setminus X=\left\\{3\right\\}$.
Since there are no appropriate duplicates that allow the construction of a
replacement node for any of the two redundant branches $[1,3]$ and $[2,3]$,
both of these branches are removed from the tree. Further, the by now non-
minimal conflicts at \scriptsize2⃝ and \scriptsize3⃝ are replaced, each by the
respective witness of redundancy that is a subset of it (e.g., $\left\langle
2,3,4\right\rangle$ is replaced by $\left\langle 2,4\right\rangle$). This
relabeling is signified by the prime (’) in the new node numbers
\scriptsize2'⃝ and \scriptsize3'⃝, respectively.

Other than that, only a single further change is induced by updateTree.
Namely, the branch $[1,2,3]$, a non-minimal diagnosis for $\mathit{dpi}_{0}$,
is returned to the queue of unlabeled nodes ${\mathbf{Q}}$ because there is no
longer a diagnosis in the tree witnessing its non-minimality (both such
witnesses $[1,3]$ and $[2,3]$ have been discarded). Note that, first,
$[1,2,3]$ is indeed no longer a diagnosis, i.e., hitting set of all minimal
conflicts for $\mathit{dpi}_{1}$ (cf. Tab. 2) and, second, there is still a
non-minimality witness for all other branches (\tiny12⃝ and \tiny13⃝)
representing non-minimal diagnoses for $\mathit{dpi}_{0}$, which is why they
remain labeled by $\times_{(\supset\mathcal{D}_{i})}$.

_Iteration 2:_ Observe the crucial differences between HS-Tree and DynamicHS
in the second iteration (compare Figs. 3 and 4).

First, while HS-Tree has to compute all the conflicts labeling internal nodes
by potentially expensive findMinConflict calls (see the C tags), DynamicHS
performs a (generally) cheaper reduction of the existing conflicts in the
course of the pruning actions we discussed above. However, note that not all
conflicts are necessarily always kept up-to-date after a DPI-transition. This
is part of the _lazy updating policy_ pursued by DynamicHS, detailed in Sec.
3.3.2. For instance, node \scriptsize5⃝ is still labeled by the now non-
minimal conflict $\left\langle 3,4,5\right\rangle$ at the time updateTree
terminates. Hence, the subtree comprising nodes \tiny13⃝, \tiny14⃝ and
\tiny15⃝ is not present in case HS-Tree is used. Importantly, this lazy
updating strategy has no negative impact on the soundness or completeness of
DynamicHS (see Sec. 3.3.2 and Theorem 1).

Second, the verification of the minimal diagnoses ($\mathcal{D}_{2}$,
$\mathcal{D}_{4}$) found in iteration 2 requires logical reasoning in HS-Tree
(see ∗ tags of $\checkmark$ nodes) whereas it comes for free in DynamicHS due
to the storage and reuse of $\mathbf{D}_{\checkmark}$ (the minimal diagnoses
returned by the previous iteration which are consistent with the lastly added
measurement).

_Remaining Execution:_ After the second measurement $m_{2}$ is added to
$\mathit{N}^{\prime}$, causing a DPI-transition once again, DynamicHS reduces
the conflict that labels the root node. This leads to the pruning of the
complete right subtree. The left subtree is then further expanded in iteration
3 (see generated nodes \tiny16⃝, \tiny17⃝, \tiny18⃝ and \tiny19⃝) until the
two leading diagnoses $\mathcal{D}_{2}=[1,4]$ and $\mathcal{D}_{5}=[1,2,3,5]$
are located and the queue ${\mathbf{Q}}$ of unlabeled nodes becomes empty
(which proves that no further minimal diagnoses exist). Eventually, the
addition of the third measurement $m_{3}$ to $\mathit{P}^{\prime}$ brings
sufficient information to isolate the actual diagnosis. This is reflected by a
pruning of all branches except for the one representing the actual diagnosis
$[1,4]$.

_Performance Comparison:_ As Figs. 3 and 4 show, DynamicHS generates 19 nodes
and requires 6 conflict computations, as opposed to 32 nodes and 14
computations in case of HS-Tree. These reductions in terms of tree rebuilding
and conflict computation costs represent two main factors responsible for
runtime improvements of DynamicHS over HS-Tree. ∎

###  3.3 Advanced Techniques in DynamicHS

DynamicHS embraces several sophisticated techniques specialized in improving
its (time or space) performance, which we discuss next.

####  3.3.1 Efficient Redundancy Checking

We now detail the workings of the function redundant (called in line 45 of
Alg. 3):

The definition of node redundancy given in Sec. 3.2.5 directly suggests a
method for checking whether or not a node is redundant, which we call
_complete redundancy check (CRC)_. It runs through all conflicts
$\mathsf{nd.cs}[i]$ used as labels along the branch to node $\mathsf{nd}$
(i.e., $i\in\left\\{1,\dots,|\mathsf{nd.cs}|\right\\}$) and calls
findMinConflict with arguments
$(\left\langle\mathsf{nd.cs}[i]\setminus\left\\{\mathsf{nd}[i]\right\\},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\right\rangle)$
to test if there is a witness of redundancy (see Sec. 3.2.5) for
$\mathsf{nd}$. A witness of redundancy exists for $\mathsf{nd}$ iff, for some
$i$, this call to findMinConflict returns a conflict $X$. Because, this
conflict then must be a subset of
$\mathsf{nd.cs}[i]\setminus\left\\{\mathsf{nd}[i]\right\\}$, meaning that
$\mathsf{nd}$ is redundant. Hence, if such an $X$ is found, then CRC is
successful (returns $\mathit{true}$) and the witness $X$ is used as an
argument passed to the subsequent call of the prune method (Alg. 3, line 46).
Otherwise, i.e., if all calls of findMinConflict made by the CRC return ’no
conflict’, it is proven that the node is not redundant and CRC returns
$\mathit{false}$.

The CRC enables sound (if CRC true, then node redundant) and complete (if node
redundant, then CRC true) redundancy checking. However, a drawback of the CRC
is that it requires $|\mathsf{nd}|$ calls to the (expensive) method
findMinConflict in the worst case, where $|\mathsf{nd}|$ is in
$O(|\mathbf{conf}(\mathit{dpi})|)$ since a node cannot hit any more than each
minimal conflict for the current DPI $\mathit{dpi}$. As a remedy to that, we
devised a more efficient, sound but incomplete, so-called _quick redundancy
check (QRC)_ , which is executed previous to the CRC and requires only a
single call of findMinConflict. The concept is that a positive QRC makes the
more expensive CRC obsolete; and, in case of a negative outcome, CRC must be
executed, but the overhead amounts to only a single findMinConflict call.

To check the redundancy of $\mathsf{nd}$, QRC executes findMinConflict with
arguments $(\langle
U_{\mathsf{nd.cs}}\setminus\mathsf{nd},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle)$.212121For
a collection of sets $Z$, we denote by $U_{Z}$ the union of all sets in $Z$.
If ’no conflict’ is returned, the QRC terminates negatively, which prompts the
execution of the CRC. Otherwise, if a conflict $X$ is returned, QRC checks
whether $X$ is a proper subset of some conflict in $\mathsf{nd.cs}$, i.e.,
whether $X\subset\mathcal{C}$ for $\mathcal{C}=\mathsf{nd.cs}[k]$ for some
$k$. In case of a positive subset-check, the QRC returns positively and it
follows that $\mathsf{nd}$ is redundant, regardless of the particular $k$. The
reason is that the argument $U_{\mathsf{nd.cs}}\setminus\mathsf{nd}$ passed to
findMinConflict does not include any element of $\mathsf{nd}$, and hence the
output conflict cannot include such elements either. Thus, if
$X\subset\mathsf{nd.cs}[k]$ holds, then
$X\subset\mathsf{nd.cs}[k]\setminus\mathsf{nd}$, and therefore
$X\subset\mathsf{nd.cs}[k]\setminus\\{\mathsf{nd}[i]\\}$ for all $i$, and in
particular for $i=k$. So,
$X\subset\mathsf{nd.cs}[k]\setminus\\{\mathsf{nd}[k]\\}$, which is equivalent
to the definition of redundancy (see page 3.2.5).

To see why the QRC is incomplete, i.e., that $\mathsf{nd}$ _can_ be redundant
even if the outcome of the QRC is negative, consider the following example:

Example 6 Let $\mathsf{nd}=[1,2]$ and $\mathsf{nd.cs}=[\left\langle
1,2\right\rangle,\left\langle 2,3\right\rangle]$. Assume that $X:=\left\langle
2\right\rangle$ is a new minimal conflict and that $\left\\{3\right\\}$ is not
a conflict. Clearly, this implies that $\mathsf{nd}$ is redundant because
$\mathsf{nd.cs}[1]\setminus X=\left\\{1\right\\}$ and $\mathsf{nd}[1]=1$.
However, $U_{\mathsf{nd.cs}}\setminus\mathsf{nd}=\left\\{3\right\\}$, which is
not a conflict, which is why findMinConflict given the DPI $(\langle
U_{\mathsf{nd.cs}}\setminus\mathsf{nd},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\rangle)$
as argument returns ’no conflict’. Hence, the QRC returns negatively although
$\mathsf{nd}$ is in fact redundant.∎

The crucial aspect which makes this incompleteness possible is the potential
overlapping of conflicts. Exactly this overlapping effectuates in the above
example that more than one element (actually even all elements) of the
outdated non-minimal conflict $\left\langle 1,2\right\rangle$ are eliminated
from $U_{\mathsf{nd.cs}}=\left\\{1,2,3\right\\}$ by deleting
$\mathsf{nd}=[1,2]$. As a consequence, the new reduced conflict $\left\langle
2\right\rangle$ is not contained any longer in the set tested by
findMinConflict.

In fact, we can conclude that the QRC is sound _and complete_ in the special
cases where all minimal conflicts are pairwise disjoint or, more generally,
where $\mathsf{nd}$ does not include any element that occurs in multiple
conflicts in $\mathsf{nd.cs}$.

####  3.3.2 Lazy Updating Policy

Updating DynamicHS’s hitting set tree after the detection of some witness of
redundancy $X$ involves going through all nodes of the tree and checking their
redundancy wrt. $X$ (cf. Sec. 3.2.5). To avoid these costs as much as
possible, DynamicHS aims at minimizing the number of performed updates under
preservation of its correctness. This can be seen from line 44, where only the
set $\mathbf{D}_{\times}$ including the most “suspicious” nodes (i.e., the
diagnoses invalidated by the latest added measurement) is checked for
redundancy. In general, this means that we allow some differences between the
tree used by DynamicHS to compute diagnoses and the one that would be obtained
when building Reiter’s HS-Tree for the current DPI from scratch. More
specifically, we allow the presence of non-minimal conflicts that are used as
node labels as well as—conditioned by these non-minimal conflicts—the presence
of unnecessary nodes (while, of course, seeking to minimize the number of such
occurrences; cf. prune function). Still, every time a conflict is used to
label a (newly processed) node, the algorithm guarantees that it is a minimal
conflict for the current DPI (cf. the conflict-minimality test in the course
of the conflict reuse check in dLabel, lines 31–36).

This _lazy updating policy_ takes effect, e.g., in iteration 2 of the example
execution of DynamicHS shown in Fig. 3 (see Example 4). Here the, at this
point, already non-minimal conflict $\mathcal{C}_{\mathit{\lnot
min}}:=\left\langle 3,4,5\right\rangle$ still appears as a node label, while
$\mathcal{C}_{\mathit{min}}:=\left\langle 4,5\right\rangle$ is now a minimal
conflict for the current DPI.

Notwithstanding the correctness proof of DynamicHS given in Sec. 3.4, we next
argue briefly why the presence of such non-minimal conflicts
$\mathcal{C}_{\mathit{\lnot min}}$ does neither counteract the soundness nor
the completeness of DynamicHS. To this end, we first point out that (*) only
nodes can be labeled $\mathit{valid}$ by DynamicHS which are diagnoses for the
current DPI (see line 37 in dLabel; and line 8 along with the definition of
$\mathbf{D}_{\checkmark}$):

  * •

Assume the _completeness_ is compromised. Then the processing of some minimal
diagnosis must be prevented from reaching line 37 in dLabel (note that it is
unavoidable that processed nodes are recognized as diagnoses in line 8). Since
the presence of all still relevant (i.e., non-redundant) nodes is not harmed
by the presence of redundant nodes, which just constitute _additional_
branches, each node corresponding to a minimal diagnosis $\mathcal{D}$ will
sooner or later be processed by dLabel. As $\mathcal{D}$ does not reach line
37 and since a minimal diagnosis does hit all (minimal) conflicts, a labeling
of $\mathcal{D}$ by $\mathit{nonmin}$ (line 28) is the only possible case.
That is, there must be a node labeled $\mathit{valid}$ (and thus stored in
$\mathbf{D}_{calc}$) which is a proper subset of $\mathcal{D}$. This is a
contradiction to (*).

  * •

Assume the _soundness_ is compromised. Then some node $\mathsf{nd}$ is labeled
$\mathit{valid}$ which is not a minimal diagnosis. Due to (*), it must be the
case that $\mathsf{nd}$ is a diagnosis, but a non-minimal one. First, a non-
minimal diagnosis can never be identified in line 8 because of Property 1.2.
Second, since the queue ${\mathbf{Q}}$ is always sorted such that node
$\mathsf{n}$ is ranked prior to node $\mathsf{n}^{\prime}$ whenever
$\mathsf{n}\subset\mathsf{n}^{\prime}$ (cf. Sec. 3.2.1), the non-minimal
diagnosis $\mathsf{nd}$ can only be labeled $\mathit{valid}$ if some minimal
diagnosis $\mathcal{D}$ ($\subset\mathsf{nd}$) —processed prior to
$\mathsf{nd}$— is not found to be a diagnosis (and thus not labeled
$\mathit{valid}$ and not stored in $\mathbf{D}_{calc}$). Hence, the
completeness must be compromised. This is a contradiction to the argumentation
in the above bullet.

####  3.3.3 Avoidance of Expensive Reasoning

As explained in Sec. 2, DynamicHS aims at reducing the reaction _time_ of a
sequential diagnosis system. One crucial time-consuming and recurring
operation in hitting-set-based diagnosis computation algorithms is the
reasoning in terms of logical consistency checks. To optimize computation
time, DynamicHS is therefore equipped with strategies that minimize the amount
of and time spent for reasoning by exploiting its statefulness in terms of the
hitting set tree maintained throughout its iterations. We discuss the concept
behind these strategies next.

_Ways of Reducing the Cost for Reasoning._ In DynamicHS, the logical inference
engine is called (solely) by the findMinConflict function, which is involved
in the determination of node labels in the tree expansion phase (dLabel
function) and in the evaluation of node redundancy in the tree update phase
(redundant function). As discussed in Sec. 2.3, a single execution of
findMinConflict given the DPI
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$ generally
requires multiple reasoner calls and their number depends critically on the
size of the universe $\mathcal{K}$ from which a minimal conflict should be
computed. Note, what we, for simplicity, refer to as a _reasoner call_
actually corresponds to a check if some $\mathcal{C}\subseteq\mathcal{K}$ is a
conflict for a DPI
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$. By the
definition of a conflict (see Sec. 2.3), this means checking whether some
$x\in\mathit{N}\cup\\{\bot\\}$ exists such that
$\mathcal{C}\cup\mathcal{B}\cup\mathit{P}\models x$. Consequently, a reasoner
call corresponds to a maximum of $|\mathit{N}|+1$ logical consistency checks.
E.g., if QuickXPlain (?, ?) is used to implement the findMinConflict function,
as in our evaluations (cf. Sec. 5), then the worst-case number of consistency
checks executed by a single call of findMinConflict on the DPI
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$ is in
$O(|\mathcal{K}|(|\mathit{N}|+1))$ (?). The hardness of consistency checking
tends to increase with the size of the knowledge base on which the check is
performed (cf., e.g., (?)).222222Further evidence that larger knowledge bases
lead to worse reasoning performance is given in (?, ?). In other words, the
smaller the size of $\mathcal{K}\cup\mathcal{B}\cup\mathit{P}$ is, the more
efficient consistency checking will tend to be in the course of
findMinConflict operating on the DPI
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$.

In summary, the lower the cardinality of the first entry $\mathcal{K}$ (number
of system components) of the tuple
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$ provided as an
input to findMinConflict is, the lower the hardness and the number of executed
consistency checks will tend to be, and thus the faster findMinConflict will
tend to execute. Hence, there are basically three different ways of scaling
down the necessary reasoning throughout DynamicHS:

  1. (i)

Reducing the number and hardness of consistency checks made while
findMinConflict executes,

  2. (ii)

reducing the number of findMinConflict calls, or

  3. (iii)

entirely avoiding findMinConflict calls (and replacing them by equivalents
that do not involve reasoning).

In its various stages, DynamicHS embraces all these three approaches, as we
explain next.

_In the tree expansion phase_ , any findMinConflict call in the course of the
conflict reuse check (lines 29–36) starts from an _already computed_
conflict—and _not_ from the entire set of system components
$\mathcal{K}$—trying to verify its minimality or, alternatively, extracting a
subset which constitutes a minimal conflict (for the current DPI). That is,
findMinConflict is given a set of at most $|\mathcal{C}_{\max}|$ elements as
an input,232323When we say that findMinConflict gets a set $S$ as an input, we
always mean by $S$ the _first_ argument of the 4-tuple (DPI) passed to the
function as an argument. where $\mathcal{C}_{\max}$ is the conflict of maximal
size (for the original242424Recall from Property 1.3 that minimal conflicts
can only become smaller throughout a sequential diagnosis session, i.e., there
cannot be any minimal conflict whose size exceeds $|\mathcal{C}_{\max}|$. DPI,
i.e., the one given as an input to Alg. 1). Note that, in many practical
applications involving systems of non-negligible size, $|\mathcal{C}_{\max}|$
is significantly (if not orders of magnitude) smaller than the number of
components of the diagnosed system (cf., e.g., (?, ?, ?)). Thus, DynamicHS
applies strategy (i) in this stage.

_In the tree update phase_ , and particularly during redundancy detection
(line 45), the quick redundancy check (QRC) is employed to potentially replace
the complete redundancy check (CRC) by making only a single findMinConflict
call instead of multiple ones (cf. Sec. 3.3.1). Moreover, any call of
findMinConflict made in the course of the redundancy detection in general
involves a significantly reduced input set, as compared to the overall number
of components $|\mathcal{K}|$ of the diagnosed system. The cardinality of this
input set is bounded by the cardinality of the union of all minimal conflicts
(for the original252525Cf. Footnote 24 DPI). So, during redundancy checking,
both strategies (i) and (ii) are pursued.

_In the tree pruning phase_ (prune function), which constitutes a part of the
tree update phase, no reasoning is required at all (i.e., no findMinConflict
calls). This is accomplished by leveraging the stored hitting set tree as well
as adequate instructions operating on sets and lists (cf. Example 5 below). At
this point, note that a stateless algorithm, in contrast, _has to_ draw on
logical reasoning to reconstruct (the still relevant) parts of the tree, and
thus to achieve essentially the same as DynamicHS’s pruning actions.
Importantly, operations relying on a logical inference engine can be expected
to have a (much) higher time complexity than the list concatenations, set-
equality or subset checks performed by DynamicHS in lieu of these operations.
For instance, reasoning with propositional logic is already NP-complete (?),
not to mention more expressive languages such as Description logics (?),
whereas set- and list-operations are (mostly linear) polynomial time
operations. So, as far as the tree pruning is concerned, DynamicHS can be
viewed as trading cheaper (reasoner-free) operations for expensive reasoner
calls. It thus makes use of strategy (iii).

_Different Types of Reasoning Operations._ Given the preceding discussion, we
can at the core distinguish the following three categories of findMinConflict
function calls based on their input DPI $\langle
X,\mathcal{B},\mathit{P},\mathit{N}\rangle$ (where
$\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\rangle$ is the DPI
relevant to the current iteration of DynamicHS):262626It is important to note
that the used _intuitive_ terminology “hard”, “medium” and “easy” is to be
understood _by tendency_ , but does not allow _general_ conclusions about the
relative or absolute hardness of the respective findMinConflict calls. That
is, e.g., an “easy” call might not be fast or easy at all. Or a “medium” call
might be faster than an “easy” one, e.g., because the latter operates on a set
of logical sentences that is particularly hard to reason with (cf. (?)).
However, as we verified in our experimental evaluation (see Sec. 5), the used
terminology does largely reflect the actual relative computation times of the
findMinConflict calls in our considered dataset. More precisely, on average
“hard” calls turned out to be _always_ (and at least four times and up to more
than 100 times) more time-intensive than “medium” and “easy” calls; and,
“easy” calls terminated faster than “medium” ones in 77 % of the studied
cases.

  * •

_”hard”_ : Size of $X$ in the order of number of system components, i.e.,
$|X|\approx|\mathcal{K}|$, _and_ a conflict is returned. (_multiple “hard”
reasoner calls_)

  * •

_”medium”_ : Size of $X$ in the order of number of system components, i.e.,
$|X|\approx|\mathcal{K}|$, _and_ ’no conflict’ is returned. (_single “hard”
reasoner call_)

  * •

_”easy”_ : Size of $X$ low compared to the number of system components, i.e.,
$|X|\ll|\mathcal{K}|$. (_few “easy” reasoner calls_)

“Hard” findMinConflict calls are those executions of line 37 (in dLabel) that
compute a fresh conflict, and “medium” ones those which lead to the finding of
a diagnosis (output ’no conflict’). In contrast, “easy” findMinConflict
invocations are those geared towards redundancy checking (line 45, updateTree)
and minimality testing for reused conflicts (line 31, dLabel). In terms of
this characterization, compared against HS-Tree, DynamicHS tries to
substantially reduce the “hard” (and “medium”) findMinConflict operations at
the cost of performing an as small as possible number of “easy” ones.

Table 3: Stats wrt. the number of different kinds of reasoning operations (findMinConflicts calls) throughout the execution of DynamicHS (DHS) and HS-Tree (HST), respectively, on the example DPI from Tab. 1. “U$i$” in the first column refers to the tree update performed by DynamicHS subsequent to iteration $i$. Note, HS-Tree does not (need to) perform any tree updates. | # “hard” | # “medium” | # “easy”
---|---|---|---
iteration | DHS | HST | DHS | HST | DHS | HST
1 | 4 | 4 | 4 | 4 | 0 | 0
U1 | 0 | – | 0 | – | 2 | –
2 | 1 | 4 | 0 | 2 | 0 | 0
U2 | 0 | – | 0 | – | 1 | –
3 | 1 | 4 | 1 | 2 | 0 | 0
U3 | 0 | – | 0 | – | 1 | –
4 | 0 | 2 | 0 | 1 | 0 | 0
total | 6 | 14 | 5 | 9 | 4 | 0

Example 7 Reconsider our example DPI in Tab. 1 and the evolution of the
hitting set computation throughout a sequential diagnosis session for
DynamicHS and HS-Tree discussed in Example 4. Tab. 3 shows the number of
“hard”, “medium” and “easy” findMinConflict calls throughout the sequential
session executed by both algorithms. The “hard” and “medium” calls are denoted
by C and ∗, respectively, in the hitting set trees depicted by Figs. 3 and 4
(“easy” calls are not indicated as tree updates are not displayed in the
figures). We can see that DynamicHS trades a significant reduction of “hard”
(57 %) and “medium” (44 %) reasoner operations for some “easy” ones.∎

####  3.3.4 Space-Saving Duplicate Storage and On-Demand Reconstruction

Basically, there are several options how to organize the storage of duplicate
nodes. These options range from storing all of them _explicitly_ to storing
only a minimal set of (stubs of) duplicate nodes that _implicitly_ allow all
duplicates to be reconstructed on demand. Since DynamicHS performs the
duplicate check at node generation time (cf. line 20), it uses the more
natural way of handling duplicate storage given by the latter strategy. This
means directly adding detected duplicate nodes—generated tree branches whose
_set_ of edge labels equals the _set_ of edge labels of an active branch (node
in ${\mathbf{Q}}$ or $\mathbf{D}_{\supset}$)—to the collection
${\mathbf{Q}}_{dup}$ without further extending them as the hitting set tree
grows. Hence, each node stored in ${\mathbf{Q}}_{dup}$ is potentially only a
partial duplicate node and might need to be combined with some other (partial)
duplicate node or some active node in the hitting set tree to explicitly
generate (or: reconstruct) a duplicate that is only implicitly stored. For
instance, assume two nodes $\mathsf{n}_{1},\mathsf{n}_{2}$ that have been
detected as duplicates and added to ${\mathbf{Q}}_{dup}$, where
$\mathsf{n}_{1}=[3,2],\mathsf{n}_{1}.\mathsf{cs}=[\left\langle
1,2,3\right\rangle,\left\langle 2,4\right\rangle]$ and
$\mathsf{n}_{2}=[2,3,1],\mathsf{n}_{2}.\mathsf{cs}=[\left\langle
1,2,3\right\rangle,\left\langle 3,4\right\rangle,\left\langle
1,4\right\rangle]$ (cf. nodes with numbers \scriptsize5⃝ and \scriptsize9⃝ in
Fig. 5, discussed in more detail in Example 5). Then, an implicit duplicate
constructible from $\mathsf{n}_{1}$ and $\mathsf{n}_{2}$ is
$\mathsf{n}_{1,2}=[3,2,1],\mathsf{n}_{1,2}.\mathsf{cs}=[\left\langle
1,2,3\right\rangle,\left\langle 2,4\right\rangle,\left\langle
1,4\right\rangle]$, where the last node label (conflict $\left\langle
1,4\right\rangle$) and edge (labeled by $1$) of $\mathsf{n}_{2}$ have been
appended to $\mathsf{n}_{1}$. The rationale behind this node combination is as
follows: $\mathsf{n}_{1}$ was recognized as duplicate first, while the first
part (i.e., the first two node and edge labels) of $\mathsf{n}_{2}$ was still
in the queue ${\mathbf{Q}}$ of open nodes. This first part of $\mathsf{n}_{2}$
was then extended by the node label $\left\langle 1,4\right\rangle$ and the
edge label $1$, but was subsequently itself spotted as a duplicate. Node
$\mathsf{n}_{1}$, however, given it had still been in ${\mathbf{Q}}$, would
have undergone the same extension. This extension is so to say “made good for”
by combining $\mathsf{n}_{1}$ with $\mathsf{n}_{2}$ to (re)construct
$\mathsf{n}_{1,2}$.

In general, to reconstruct a duplicate node $\mathsf{n}_{i,j}$ from a
combination of two nodes $\mathsf{n}_{i},\mathsf{n}_{j}$, the following
criteria have to be met:

  1. (RD1)

The first $|\mathsf{n}_{i}|$ elements of $\mathsf{n}_{j}$ interpreted as a set
are equal to the elements of $\mathsf{n}_{i}$ interpeted as a set; there are
no conditions on the conflict labels $\mathsf{n}_{i}.\mathsf{cs}$ and
$\mathsf{n}_{j}.\mathsf{cs}$ of the combined nodes.

  2. (RD2)

The reconstructed node $\mathsf{n}_{i,j}$ is built by setting272727Notation:
Given a list $\mathsf{n}$, $\mathsf{n}[k..l]$ refers to the sublist including
all elements from the $k$-th (included) until the $l$-th (included).
$\mathsf{n}_{i,j}[1..|\mathsf{n}_{i}|]=\mathsf{n}_{i}$ and
$\mathsf{n}_{i,j}[|\mathsf{n}_{i}|+1..|\mathsf{n}_{j}|]=\mathsf{n}_{j}[|\mathsf{n}_{i}|+1..|\mathsf{n}_{j}|]$
as well as
$\mathsf{n}_{i,j}.\mathsf{cs}[1..|\mathsf{n}_{i}|]=\mathsf{n}_{i}.\mathsf{cs}$
and
$\mathsf{n}_{i,j}.\mathsf{cs}[|\mathsf{n}_{i}|+1..|\mathsf{n}_{j}|]=\mathsf{n}_{j}.\mathsf{cs}[|\mathsf{n}_{i}|+1..|\mathsf{n}_{j}|]$,
i.e., the first part of $\mathsf{n}_{i,j}$ and $\mathsf{n}_{i,j}.\mathsf{cs}$,
respectively, is equal to $\mathsf{n}_{i}$ and $\mathsf{n}_{i}.\mathsf{cs}$,
to which the last part of $\mathsf{n}_{j}$ and $\mathsf{n}_{j}.\mathsf{cs}$ is
appended.

  3. (RD3)

Either  (a) $\mathsf{n}_{i},\mathsf{n}_{j}$are each (reconstructed282828Note
the recursive character of this definition. That is, all combinations of
explicit and already reconstructed nodes are possible. E.g., a reconstructed
node $\mathsf{n}_{6}$ can be the result of combining two explicit nodes
$\mathsf{n}_{1}$ and $\mathsf{n}_{2}$ to reconstruct a node $\mathsf{n}_{3}$,
which in turn is combined with some explicit node $\mathsf{n}_{4}$, which in
turn is combined with a reconstructed node $\mathsf{n}_{5}$. or explicit)
nodes from ${\mathbf{Q}}_{dup}$, or  (b) node $\mathsf{n}_{i}$ is from the
node combination closure ${\mathbf{Q}}^{*}_{dup}$ of ${\mathbf{Q}}_{dup}$
which is the union of ${\mathbf{Q}}_{dup}$ with the set of all nodes
reconstructible292929Formally, ${\mathbf{Q}}^{*}_{dup}$ can be defined as the
fixpoint $S^{*}$ of the sequence of sets $S_{0},S_{1},\dots$ resulting from
the iterative application of the $\mathit{Comb}$ function starting from
$S_{0}:={\mathbf{Q}}_{dup}$ where $S_{i+1}=\mathit{Comb}(S_{i})$ and
$\mathit{Comb}$ is defined as