\documentclass[11pt,theapa,leqno,notitlepage]{article}
\usepackage{jair}
\jairheading{19}{2003}{469-512}{12/02}{10/03}
\ShortHeadings{Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board}{Console, Picardi, \& Theseider Dupr\'e}
\firstpageno{469}
\usepackage{makeidx}
\usepackage{mycommands}
\usepackage{myalgo}
\newenvironment{ite}{
\begin{itemize}
\setlength{\topsep}{0.5mm}
\setlength{\labelwidth}{2mm}
\setlength{\labelsep}{0.5mm}
\setlength{\parsep}{0.5mm}
\setlength{\itemsep}{\parskip}
\setlength{\leftmargin}{0mm}
\setlength{\leftmargini}{4mm}
}{\end{itemize}}

\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\newcommand{\bi}{ \begin{itemize} }
\newcommand{\ei}{ \end{itemize} }

\newenvironment{linelist}{
\begin{ite}
\renewcommand{\labelitemi}{-}
}{\end{ite}}
 
%%\bibliographystyle{named}

\begin{document}

%%\setlength{\textfloatsep}{0.5cm}
%%\setlength{\intextsep}{0.5cm}
%%\setlength{\floatsep}{0.5cm}
%%\setlength{\dblfloatsep}{0.5cm}
%%\setlength{\dbltextfloatsep}{0.5cm}

\title{\bfseries Temporal Decision Trees:
\\
Model-based Diagnosis of Dynamic Systems On-Board}
%\author{}


%%\author{\normalsize Luca Console, Claudia Picardi \\
%%\normalsize Dipartimento di Informatica\\
%%\normalsize Universit\`a di Torino\\
%%\normalsize Corso Svizzera 185\\
%%\normalsize I-10149, Torino, Italy\\
%%\texttt{\normalsize \{lconsole,picardi\}@di.unito.it} \\
%%\and
%%\normalsize Daniele Theseider Dupr\'e\\
%%\normalsize Dipartimento di Informatica\\
%%\normalsize Universit\`a del Piemonte Orientale\\
%%\normalsize Spalto Marengo 33\\
%%\normalsize I-15100, Alessandria, Italy\\
%%\texttt{\normalsize dtd@mfn.unipmn.it}
%%}
\author{\name Luca Console \email luca.console@di.unito.it \\
\name Claudia Picardi \email claudia.picardi@di.unito.it \\
\addr Dipartimento di Informatica, Universit\`a di Torino, \\
Corso Svizzera 185, I-10149, Torino, Italy
\AND
\name Daniele Theseider Dupr\'e \email dtd@mfn.unipmn.it\\
\addr Dipartimento di Informatica, Universit\`a del Piemonte Orientale \\
\addr Spalto Marengo 33, I-15100, Alessandria, Italy}

\maketitle


\begin{abstract}
The automatic generation of
decision trees based on off-line reasoning on models
of a domain is a reasonable compromise between
the advantages of using a model-based approach in technical domains
and the constraints imposed by embedded applications.
In this paper we extend the approach to deal with temporal
information. We introduce a notion of temporal
decision tree, which is designed to make use
of relevant information as long as it is acquired,
and we present an algorithm for compiling such trees from
a model-based reasoning system.
\end{abstract}


\section{Introduction}
\label{intro}


The embedding of software components inside physical
systems became widespread in the last decades
due to the convenience of including electronic control
into the systems themselves.
This phenomenon occurs in several
industrial sectors, ranging from large-scale products 
such as cars to much more expensive systems like aircraft and spacecrafts.

The case of automotive systems is paradigmatic. In fact, the number
and complexity of vehicle subsystems which are managed
by software control increased significantly since the mid 80s and
will further increase in the next decades (see \citeR{Roadmap:02}),
due to the possibility of introducing, at costs that are
acceptable for such wide scale products,
more flexibility in the systems, for e.g.\ increased performance and
safety, and reduced emissions.
Systems such as fuel injection control, ABS (to prevent blockage
of the wheels while braking), 
ASR (to avoid slipping wheels),
ESP (controlling the stability of the vehicle), 
would not be possible at feasible costs without electronic control.
%Apart from these devices, even current generation engines
%(especially Diesel ones)
%are completely managed by electronic controls.
% DTD: e' gia' detto sopra "fuel injection control"

The software modules are usually
% non ne sono sicuro, in che senso? DTD
% embedded in the systems themselves or are
installed on dedicated Electronic Control Units (ECUs)
and they play a very important role since they have complete
control of a subsystem: human ``control'' becomes simply an input
to the control system, together with inputs from appropriate sensors.
For example, the position of the accelerator pedal is
%currently
an input to the ECU which controls fuel delivery to
the injectors.

A serious problem with these systems is that the software must
behave properly also in presence of faults and must guarantee
high levels of availability and safety for the controlled system
and for the vehicle. The controlled systems, in fact, are in many
cases safety critical: the braking system is an obvious
example. This means that monitoring the systems behaviour,
detecting and isolating failures, performing the appropriate
recovery actions is a critical task that must be performed by
control software. If any problem is detected or suspected the
software must react, modifying the way the system is controlled,
with the primary goal of guaranteeing safety and availability.
According to recent estimates, about $75\%$ of the ECU software
deals with detecting problems and performing recovery
actions, that is to the tasks of diagnosis and repair
(see again \citeR{Roadmap:02}).


Thus the design of the diagnostic software is a very critical and
time consuming activity, which is currently performed manually by
expert engineers who use their knowledge to
perform the ``Failure Mode and Effect Analysis
(FMEA)'' \footnote{The result of FMEA is a table which lists, for
each possible fault of each component of a system, the effect of
the faults on the component and on the system as a whole and the
possible strategy to detect the faults. This table is compiled
manually by engineers, based on experience knowledge and on a
blueprint of the system.} and define diagnostic and recovery
strategies. 
%which can be regarded as a set of handwritten rules
%(error line code).

The problem is complex and critical per-se, but it is made even
more difficult by a number of other issues and constraints that
have to be taken into account: 

\begin{itemize}
\item
The resources that
are available on-board must be limited, in terms of memory and
computing power, to keep costs low. This has to be combined with
the problem that near real time performance is needed,
especially in situations that may be safety critical. For example, for direct
injection fuel delivery systems, where fuel is maintaned at a very high pressure 
(more than 1000
bar) there are cases where the system
must react to problems within a rotation of the engine (e.g.\ 15 milliseconds
at 4000 rpm), to prevent serious damage of the engine and danger to
passengers. In fact, a fuel leakage can be very dangerous if it comes from a high pressure line.
In this case it is important to distinguish whether a loss of pressure is due to such a leak, in order to activate some emergency action (for example, stop the engine), or to some other failure which can simply be signalled to the user.
\item
In order to keep costs acceptable for a
large scale product, the set of sensors available on board is
usually limited to those necessary for controlling the systems
under their correct behaviour; thus, it is not always easy to
figure out the impact that faults may have on the quantities
monitored by the sensors, whose physical, logical and temporal
relation to faults may be not straightforward.
%which may be far away (in physical and
%logical terms) from the point of the failure.
%This complicates
%the work of engineers who have to study how the failure may
%impact on the remote sensors.

\item
%Finally, and most important from the conceptual point of view,
The devices to be diagnosed are complex from the behavioural point
of view: they have a dynamic and time-varying
behaviour; they are embedded in complex systems and they
interact with other subsystems; 
in some cases the control system automatically compensates
deviations from the nominal behaviour.
\end{itemize}

These aspects make the design of software modules for control and
diagnosis very challenging but also very expensive and time
consuming. There is then a significant need for improving this
activity, making it more reliable, complete and efficient through
the use of automated systems to support and complement the
experience of engineers, in order to meet the growing
standards which are required for monitoring, diagnosis and
repair strategies.

Model-based reasoning (MBR) proved to be an interesting opportunity for
automotive applications and indeed some 
applications to real systems have been experimented in the 90s
\cite<e.g.,>{Cascio:97,Mosterman:98,Struss:98,Sachenbacher:2000}.
The type of models adopted in MBR are conceptually not too
far away from those adopted by engineers. In particular, the component
oriented approach typical of MBR fits quite well with the
problem of dealing with several variants of systems, assembled starting from
the same set of basic components.
For a more thorough discussion of the advantages of the MBR approach,
see \citeauthor{Console:ijcai:99} \citeyear{Console:ijcai:99}.

Most of the applications developed so far, however, concentrated
on off-board diagnosis, that is diagnosis in the workshop, and not
on on-board diagnosis. 
The case of on-board systems seems to be more complicated since,
due to the restrictions on hardware to be put on-board,
it is still questionable if diagnostic
systems can be designed to reason on first-principle models on-board.
For this reason other approaches have been developed in
order to exploit the advantages of MBR also in on-board
applications. In particular, a {\em
compilation-based} scheme to the design of on-board diagnostic
systems for vehicles was experimented in the Vehicle Model Based
Diagnosis (VMBD) BRITE-Euram Project (1996-99), and applied to a
Common-rail fuel injection system {\cite{Cascio:corto:99}}.
In this approach
a model-based diagnostic system
is used to generate a compact
on-board diagnostic system in the form of a 
decision tree.
Similarly, automated FMEA reports generated by Model-Based
Reasoning in the Autosteve system can be used to generate
diagnostic decision trees \cite{Price:99}.
Yet similar is the idea proposed by Darwiche {\citeyear{Darwiche:99}}, where
diagnostic rules
are generated from a model
in order to meet resource constraints.

% \begin{itemize}
% \item
% A model-based diagnostic system, which can be used
% to solve problems off-line (and then for off-board
% diagnosis in the garage),
% is used to solve
% a set of significant cases (that is, at least a good
% sample of the cases that have to be faced on-board).
% The solution
% includes the set of candidate diagnoses and, more important,
% the recovery action(s) that should
% be performed on-board in that case.
% \item
% Cases and the corresponding
% recovery actions are used to generate a compact
% on-board diagnostic system.
% Specifically, in {\cite{Cascio:aicomm:99DX}} decision
% trees are generated,
% using an algorithm based on {\sc id3} \cite{Quinlan:86}.
% A decision tree represents knowledge for a decision
% process in a sequence of tests or observations 
% on an external environment.
% Usually, a good test to be performed at each step can be
% chosen depending on the
% outcome of previous ones; this is the reason why 
% the decision process is suitably represented by
% a tree. In the {\sc id3} algorithm, the information-theoretic
% concept of entropy is used to choose a measurement that
% performs the best (from a best-first point of view)
% discrimination among the alternative possible decisions
% remaining, given the previous observations.
% \end{itemize}
% FINE PEZZO

These approaches have interesting advantages. On the one hand, 
they share most of the benefits of model-based systems, such as relying
on a comprehensive representation
of the system behaviour and a well defined characterization
of diagnosis. On the other hand,
decision trees and other compact representations
make sense for representing on-board
diagnostic strategies, being efficient in space and time.
Furthermore, algorithms for synthesizing decision trees 
from examples are well established in the machine learning community.
In this specific case the examples are the solutions (diagnoses
and recovery actions) generated by a model-based system.

However, the basic notion of decision tree and the approaches for
learning such trees from examples have a major limitation for our
kind of applications: they do not cope properly with the temporal
behaviour of the systems to be diagnosed, and, in particular, with
the fact that incremental discrimination of possible faults,
leading to a final decision on an action to be taken on-board,
should be based on observations acquired {\em across time},
thus taking into account temporal patterns.
%Dealing with dynamic behaviour, i.e., with the fact
%that the behaviour of a system depends on its internal state and,
%more generally, that such a behaviour manifests itself across time,
%can be critical for diagnosing complex systems. It is then
%necessary to collect observations across time, in order to
%discriminate different faults that have similar sets of effects,
%but with different temporal patterns.

%This has to be reflected in the decision tree, which must
%include the possibility of reasoning about time and taking into
%account temporal patterns.


For such a reason, in the work described in this paper we
introduce a new notion of decision tree, the {\em temporal
decision tree}, which takes into account the temporal dimension,
and we introduce an algorithm for synthesizing
% PIU' GENERALE DI learning X IL CASO ESAUSTIVO DTD
temporal decision trees.


Temporal decision trees extend traditional decision trees in the
fact that nodes have a temporal label which specifies when
a condition should be checked in order to select one of
the branches or to make a decision.
As we shall see, this allows taking into account that in some
cases the order and the delay between observable measures
influences the decision to be made and thus provides
important power to improve the decision process.
Waiting, however, is not always possible and thus the
generation of the trees includes a notion of deadline
for each possible decision. Thus, the temporal decision process
supports the possibility of selecting the best decision, 
exploiting observations and their temporal locations (patterns)
and taking into account that in some cases at some point 
a decision has to be taken anyway to prevent serious problems.

The rest of the paper is organized as follows.
In section \ref{background} we summarize some basic ideas
about model-based diagnosis (MBD), the use of decision trees in conjunction
with it, and the temporal dimension in MBD and in decision trees.
In section \ref{tdt:basic} we provide basic formal
definitions about decision trees, which form the basis for
their extension to temporal decision trees 
in section \ref{tdt:sect}.
We then describe (section \ref{buildingtdt}) the problem
of synthesizing temporal decision trees and our solution
(section \ref{tdtalgo}).




\section{Model-based Diagnosis and Decision Trees}
\label{background}

In this section we briefly recall the basic notions of model-based diagnosis
and we discuss how decision trees can be used
for diagnostic purposes, focusing on how they have been used
in VMBD in conjunction with the model-based approach
\cite{Cascio:corto:99}.

\subsection{The Atemporal Case}
First of all let us sketch the atemporal case and the ``traditional'' use of diagnostic decision trees.
\subsubsection{Atemporal model-based diagnosis}
The starting point for model-based diagnosis is a model of
the structure and behaviour of the device to be diagnosed.
More specifically, we assume a component centered approach
in which:
% By model of the structure and behaviour we mean that
\begin{itemize}
\item
A model is provided for each component type; a component
is characterized by 
\begin{itemize}
\item 
A set of variables (with a distinguished set of interface variables);
\item
A set of {\em modes}, including an {\em ok} mode
(correct behaviour) and possibly a set of fault modes.
\item
A set of relations involving
component variables and modes, describing the
behaviour of the component in such a mode.
These relations may model
the correct behaviour of the device and, in some cases, the behaviour
in presence of faults (faulty behaviour).
\end{itemize}
\item
A model for the device is given as a list of the component instances
and of their connections (connections between interface variables).
\end{itemize}
In the Artificial Intelligence approach,
models are usually qualitative, that is the domain of
each variable is a finite set of values.
Such an abstraction has proven to be
useful for diagnostic purposes.

The model can be used for simulating the behaviour
of a system and then for computing diagnoses. In fact, given
a set of observations about the system behaviour, diagnoses
can be determined after comparing the behaviour
predicted by the model (in normal conditions or in the
presence of single or multiple faults) and the observed behaviour.

In order for the model to be useful for on-board diagnosis,
for each fault mode $F$ (or combination of fault modes) the model must 
include the recovery action the control software
should perform in case $F$ occurs.
In general these actions have a cost,
mainly related to the resulting reduction of functionality of the system.
Moreover, two actions $a_1$ and $a_2$
can be related in the following sense:
\begin{itemize}
\item
$a_1$, the recovery action associated with fault $F_1$,
carries out operations that \textit{include} those performed by $a_2$,
the recovery action associated with $F_2$;
\item
$a_1$ can be used as a recovery action also when $F_2$ occurs; it may however
carry out unneeded operations, thus reducing the system functionality more than strictly necessary.\item
However, in case we cannot
discriminate between $F_1$ and $F_2$, applying $a_1$ is a rational choice.
\end{itemize}
In section \ref{actionmodel} we will present a model for actions
which formalizes this relation.

Thus the main goal of the on-board diagnostic procedure is to decide
the best action to be performed, given the observed malfunction.
This type of procedure can be efficiently represented using decision trees.

\subsubsection{Decision trees}
Decision trees can be used to implement classification
problem solving and thus some form of
diagnostic procedure.
Each node of the tree corresponds to an observable.
In on-board diagnosis, observables correspond either to direct sensor readings, or to the results of computations carried out by the ECUs on the available measurements. In the following the word ``sensor'' will denote both types of observables; it is worth pointing out that the latter may require some time to be performed. In this paper we mainly assume that a sensor reading takes no time; however the apporach we propose deals also with the case in which a sensor reading is time consuming, as pointed out in section \ref{sect:challenge}.
%%In on-board diagnosis, observables correspond to 
%%readings from actual sensors or outputs of
%%the so called ``virtual sensors", that is values obtained through
%%computations performed by the ECUs from available measurements. 
A node
can have as many descendants as the number of qualitative values
associated with the sensor. The leaves of the tree correspond to actions
that can be performed on board.
Thus, given the available sensor readings,
the tree can be very easily used to make a decision on the recovery
action to be performed.

%As we shall see in section \ref{buildingtdt}, 
Such decision trees can be generated automatically
from a set of examples or cases. By example here we mean 
a possible assignment of values to observables and the
corresponding diagnosis, or possible alternative
diagnoses, and a selected recovery action
which is appropriate for such a set of suspect diagnoses.
This set can be produced using
a model-based diagnostic systems, which, given a set of observables
can compute the diagnoses and recovery actions.

In the atemporal case, with finite qualitative domains, the number of
possible combinations of observations is finite, and usually small,
therefore considering all cases exhaustively (and not just a sample)  
is feasible and
there are two equivalent ways of building such an exhaustive
set of cases:
\begin{enumerate}
\item
{\em Simulation approach:} for each fault $F$, we
run the model-based system to predict the observations
corresponding to $F$.
\item
{\em Diagnostic approach:}
we run a diagnosis engine on combinations
(all relevant combinations) of observations, to compute
the candidate diagnoses for each one of these cases.
\end{enumerate}
In either case, the resulting decision tree contains the same
information as the set of cases; if, once sensors are placed in the system,
observations have no further cost, the decision
tree is just a way to save space with respect to a table,
and speed up lookup of information.

In this way the advantages of the model-based approach and of
the use of compact decision trees can be combined:
the model-based engine produces diagnoses based on reusable component models
and can be used as the diagnoser off-board; 
compact decision trees, synthesized from cases classified
by the model-based engine, can be installed on-board.


\subsection{Towards Temporal Decision Trees}
\label{underlying}

In this section we briefly recall some basic notions on
temporal model-based diagnosis 
(see \citeR{Brusoni:aij:98} for a general discussion on temporal
diagnosis), and we informally introduce temporal decision trees.

\subsubsection{Temporal MBD}

The basic definition of MBD is conceptually similar to
the atemporal case. Let us consider the main differences.


As regards the model of each component type we consider a 
further type of variable: state variables used to model 
the dynamic behaviour of the component.
The set of relations describing the behavior
of the component (for each mode) is augmented with
temporal information (constraints);
we do not make specific assumptions on the model
of time, even though, as we shall see in the following,
this has an impact on the cases which can be considered for
the tree generation.
As an example, these constraints may specify a delay between an input and
an output or in the change of state of the component.

As regards recovery actions, 
a deadline for performing the action must be specified;
this represents the maximum time
that can elapse between fault detection and the recovery
action; this is the amount of time available for 
the control software to perform discrimination.
This piece of information is specific to each
component instance, rather than component type,
because the action and the deadline are related to the potential
unacceptable effects that a fault could have on the overall system;
the same fault of the same
component type could be very dangerous for one
instance and tolerable for another.


Diagnosis is started when observations
indicate that the system 
is not behaving correctly. 
Observations correspond to
(possibly qualitative) values of variables across time.
In general, in the temporal case a diagnosis is an assignment
of a mode of behaviour to component instances across time
such that the observed behaviour is explained by
the assignment given the model.
For details on different ways of defining explanation in this case
see Brusoni et al. \citeyear{Brusoni:aij:98}.
For the purposes of this paper we are only interested in the fact
that, given a set of observables, a diagnosis (or a set of
candidate diagnoses if no complete discrimination is possible)
can be computed and a recovery action is determined.

This means that the starting point of our approach is a table containing
the results of running the model-based diagnostic system on a set
of cases, (almost) independently of the model-based diagnostic system
used for generating the table.

We already mentioned that 
in the static case, with finite qualitative domains, 
an exhaustive set of cases can be considered.
In the temporal case, if the model of time is purely qualitative,
a table with temporal information cannot be built
by prediction, while it can be built running the diagnosis engine
on a set of cases with quantitative information:
diagnoses which make qualitative predictions that are inconsistent
with the quantitative information can be ruled out.
Of course, this cannot in general be done exhaustively, even if
observations
are assumed to be acquired at discrete times;
if it is not,
the decision tree generation will actually be {\em learning} from
examples.

% In the following we assume that the model either includes temporal
% constraints that are used to generate precise enough predictions
% on the temporal location of observations, or a diagnostic system
% is run on a not necessarily exhaustive set of cases.


Thus a simulation approach can only be used in case
the temporal constraints in the model are precise enough to
predict at least partial information on the temporal location of the
observations, e.g., in case the model includes
quantitative temporal constraints.

The diagnostic approach can be used also in case of weaker
(qualitative) temporal constraints in the model.

As regards the observations, we consider the general case where
a set of snapshots is available; each snapshot is labelled
with the time of observation and reports the value of
the sensors (observables) at that time. This makes the approach
suitable for different notions of time
in the underlying model and on the observations
(see again the discussion in \citeR{Brusoni:aij:98}).

\begin{exm}\label{example:teset} 
The starting point for generating a temporal decision tree is a table
like the one in Figure \ref{tdt:example:teset}.

\begin{figure}[h]
\begin{center}{\footnotesize\setlength{\tabcolsep}{0.8ex}
    \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
    & \multicolumn{8}{|c|}{$s_1$} & \multicolumn{8}{|c|}{$s_2$} 
    & \multicolumn{8}{|c|}{$s_3$} & & \\ \cline{2-25} 
    & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & \raisebox{1ex}[0pt]{\namestyle{Act}} & \raisebox{1ex}[0pt]{\namestyle{Dl}}\\ \hline
    $\namestyle{sit}_1$ & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{h} & \namestyle{h} & & &
    \namestyle{l} & \namestyle{v} & \namestyle{v} & \namestyle{v} & \namestyle{v} & \namestyle{v} & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{l} & \namestyle{l} & & &
    $a$ & $5$ \\ \hline

    $\namestyle{sit}_2$ & \namestyle{h} & \namestyle{h} & \namestyle{h} & & & & & &
    \namestyle{h} & \namestyle{n} & \namestyle{n} & & & & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & & & & & &
    $b$ & $2$ \\ \hline
    $\namestyle{sit}_3$ & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} &
    \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{v} & \namestyle{v} & \namestyle{v} & \namestyle{v} &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{v} & \namestyle{v} &
    $b$ & $7$ \\ \hline
    $\namestyle{sit}_4$ & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & &
    \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{l} & \namestyle{v} & &
    \namestyle{n} & \namestyle{n} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & &
    $c$ & $6$ \\ \hline
    $\namestyle{sit}_5$ & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & & & & &
    \namestyle{h} & \namestyle{n} & \namestyle{n} & \namestyle{n} & & & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & & & & &
    $c$ & $3$ \\ \hline
    $\namestyle{sit}_6$ & \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{h} & \namestyle{h} & \namestyle{h} & & &
    \namestyle{l} & \namestyle{v} & \namestyle{v} & \namestyle{z} & \namestyle{z} & \namestyle{z} & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{l} & \namestyle{v} & & &
    $d$ & $5$ \\ \hline
    $\namestyle{sit}_7$ & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & & &
    \namestyle{l} & \namestyle{l} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{v} & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{l} & \namestyle{v} & & &
    $b$ & $5$ \\ \hline
    $\namestyle{sit}_8$ & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & \namestyle{h} & & &
    \namestyle{h} & \namestyle{h} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{l} & & &
    \namestyle{n} & \namestyle{n} & \namestyle{n} & \namestyle{l} & \namestyle{v} & \namestyle{z} & & &
    $c$ & $5$ \\ \hline
    \end{tabular}}
\end{center}
\caption{An example of a set of cases for learning temporal decision trees.}\label{tdt:example:teset}
\end{figure}

Each row of the table corresponds to a situation (case or ``example"
in the  terminology of machine learning) and it reports:
\begin{itemize}
\item
For each sensor $s_i$ the values that have been observed at
each snapshots (in the example we have 8 snapshots, labelled 
as $0$ to $7$); \namestyle{n}, \namestyle{l}, \namestyle{h} and
\namestyle{v} correspond to the qualitative values of the sensor
measurements; \namestyle{n} for {\em normal}, \namestyle{l} for {\em low}, \namestyle{h} for {\em high}, \namestyle{v} for {\em very low} and \namestyle{z} for {\em zero}.
\item
The recovery action \namestyle{Act} to be performed in that
situation.
\item
The deadline \namestyle{Dl} for performing such an action.\theoend
\end{itemize}
\end{exm}

A table as the one in the above example represents a set of situations that may be encountered
in case of faults and, as noticed above, it can be generated using
either a diagnostic or a simulation approach.
In the next section we shall introduce the notion
of temporal decision trees and show how the pieces of information about
sensor histories like those in the table above
can be exploited in the generation of such trees.



\subsubsection{Introduction to temporal decision trees}
\label{introtdt}

Traditional decision trees do not include a notion
of time, i.e., the fact that data may be observable at different
times or that different faults may be distinguished
only by the temporal patterns of data.
Thus, neglecting the notion of time
may lead to limitations in the decision process. 

For such a reason in this work we introduce a notion of
temporal decision tree. Let us analyse the intuition behind
temporal decision trees and the decision process they support.
Formal definitions will be provided later in the paper.

Let us consider, for example, the fault situations $\namestyle{sit}_3$ and $\namestyle{sit}_4$ in Figure \ref{tdt:example:teset}, and let us assume, for the sake of simplicity, that the only available sensor is $s_2$. The two fault situations have to be distinguished in the control software because
they require different recovery actions. Both of them can be detected by the fact that $s_2$ shows a \namestyle{l}ow value. Moreover, in both situation after a while $s_2$ starts showing a \namestyle{v}ery low value.

The only way to discriminate these two situations is to make use of temporal information, that is to exploit the fact that in $\namestyle{sit}_3$ value \namestyle{v} shows up after 4 time units from fault detection, while in $\namestyle{sit}_4$ the same value shows up after 6 time units.

%%Consider two possible faults $F_1$ and $F_2$ of a system,
%%which have to be distinguished in the control software because
%%they require different recovery actions.
%%Suppose that both $F_1$ and $F_2$
%%produce an abnormal value for a sensor $s_1$, but
%%$F_1$ also produces an abnormal value for sensor $s_2$ after time
%%$d_1$ while $F_2$ produces the same abnormal value for $s_2$
%%after time $d_2 > d_1$.
%%The two faults cannot be distinguished 
%%without temporal information.
%%
%%Similarly, in case $F_1$ produces abnormal values for $s_1$
%%and, after $d_1$, for $s_2$, while $F_2$ only affects $s_1$,
%%we have to take the delay $d_1$ into account in order to
%%distinguish the case where the effect on $s_2$ is absent
%%from the one where it just has not occurred yet.

In order to take into account this in a decision tree,
we have to include time into the tree.
In both examples, the best decision
procedure is to wait after observing thst $s_2 = \namestyle{l}$ (that is, after dectecting that a fault has occurred). After 4 time units we can make a decision, depending on whether 
$s_2 = \namestyle{v}$ or not. This corresponds to the procedure described by the tree
in Figure \ref{esempietto}.
\begin{figure}[h]
\begin{center}{\footnotesize
\setlength{\unitlength}{1mm}
\begin{picture}(40,28)
\put(15,25){$s_2$}
\put(5,15){\makebox{\includegraphics[scale=0.7, viewport= 26mm 102mm 57mm 115mm, clip=true]{Figures/tdt_first_example.eps}}}
\put(3.5,20){\namestyle{...}}
\put(21.5,20){\namestyle{l}}
\put(3,13){\ldots}
\put(20,12.5){$s_2$ after 4}
\put(16,3){\makebox{\includegraphics[scale=0.7, viewport= 26mm 102mm 57mm 115mm, clip=true]{Figures/tdt_first_example.eps}}}
\put(20,7.5){\namestyle{l}}
\put(33,7.5){\namestyle{v}}
\put(15.5,0.5){$\namestyle{sit}_4$}
\put(36,0.5){$\namestyle{sit}_3$}
\end{picture}
}\end{center}
\caption{A simple example of temporal decision tree}
\label{esempietto}
\end{figure}

%After observing an abnormal value for $s_1$, the
%system waits for $d_1$ units of time,
%and then makes a decision, depending on
%whether at that time an abnormal value for $s_2$ is read.
%%However, this behaviour is only
%%reasonable in case the recovery actions
%%associated with faults $F_1$ and $F_2$ allow the system to wait for
%%$d_1$ more units
%%of time after fault detection (i.e.\ in this example,
%%after observing an abnormal
%%value for $s_1$).

Obviously, waiting is not always the solution or is not always possible.
In many cases, in fact, safety or other constraints may impose some
deadlines for performing recovery actions. 
This has to be reflected in the generation of the decision procedure.
Suppose, in the example above, that the deadline for $\namestyle{sit}_3$ was 3 rather than 6: in this case the two situations would have been indistinguishable, beacause it would have been infeasible to wait 4 time units. 
%%Suppose, in the example above, that $F_1$ requires
%%that a recovery action $a_1$ is performed within $d_0 < d_1$ units
%%of time, otherwise the system may have a serious
%%damage or safety may be affected
%%(while $F_2$ does not require recovery actions).
%%In this case we cannot wait $d_1$ units of time so we have to
%%perform the recovery action anyway before $d_0$; then we may take
%%some further time to decide which was the actual fault.

Thus, an essential idea for generating small decision trees in the
temporal case is to take advantage of the fact
that {\em in some cases there is nothing
better than waiting}\footnote{A different approach would be that of weighing the amount of elapsed time agains the possibility of better discriminating faults; such an approach is something we are considering in the future work on temporal decision trees, as outlined in section \ref{conclusions}.}, in order to get a good discrimination,
provided that safety and integrity of the physical system are kept into
account, and that deadlines for recovery actions are always met.

More generally, one should exploit all the information
about temporal patterns of observables and about deadline,
like the ones in Figure \ref{tdt:example:teset}, to
produce an optimal diagnostic procedure.

%MA FACCIAMO QUANTO DETTO NEL PARAGRAFO SEGUENTE? DTD
%
%More generally, the problem is that of trading off costs,
%including the cost
%of performing the recovery action, the cost of not performing it
%in case the fault is present, 
% the cost of not performing it, ????
%the cost of waiting.

Another idea we use in our approach is the integration of
incremental discrimination, which is the basis for the
generation and traversal of a decision tree, with the incremental
acquisition of information across time.

In the atemporal case, the decision tree should be
generated in order to guide the incremental acquisition 
of information: different subtrees of a node
are relative to different sets of faults 
and therefore may involve different measurements:
in a subtree T we perform the 
measurements that are useful for discriminating
the faults compatible with the measurements that
made us reach subtree T, starting from the root.
For off-board diagnosis, this allows reducing the average
number of measurements to get to a decision
(i.e.\ the average depth of the tree), which
is useful because measurements have a cost -
e.g.\ time for an operator to take them from the system;
for on-board diagnosis, even in case all measurements are
simply sensor readings, which have no cost once
the sensor has been made part of the system, we are interested
in generating {\em small} decision trees to save space.

In the temporal case there is a further issue:
the incremental acquisition of information is naturally constrained by the flow of time.
If we do not want to store sensor values across time --- which seems a natural choice since we have memory constraints --- information must be acquired when it is available and it is not possible to read sensors once the choice of waiting has been made.
%%acquisition of information is naturally incremental
%%since we must assume the qualitative values of system variables change with a temporal
%%granularity that is large enough to perform some 
%%processing in between. 
%%Since we are interested in saving space on board,
%%this suggests integrating tree traversal and
%%measurements so that {\em no sensor data has to be stored}:
%%if visiting node $N$ involves reading a sensor value at time $t$,
%%any child $N'$ of $N$ requires a sensor reading at time $t' > t$.
%%We shall use the term {\em monotonic} to denote trees that respect
%%this property.
This issue will be taken into account in the generation
of temporal decision trees.


\section{Basic Notions on Decision Trees}\label{tdt:basic}

Before moving to a formal definition of temporal
decision trees, in this section we briefly recall some definitions
and algorithms for the atemporal case. In particular, we recall the 
standard \idthree\ algorithm \cite{Quinlan:86}, which will be the basis
for our algorithm for the temporal case.
The definitions in this section are the standard ones (see any
textbook on Artificial Intelligence, \citeR<e.g.,>{Russel:95}).

\subsection{Decision Trees}

We adopt the following formal definition of decision tree,
which will be extended in section 
\ref{tdt:subsect:tdtdef}
to temporal decision trees.

\begin{dfn}
Let us consider a decision process $\mathcal P$ where $\mathbb A$ is the set of available 
decisions, $\mathbb O$ is the set of tests that can be performed on the external environment, and 
$\namestyle{out} (o_i) = \{ v_1, \ldots, v_{k_i}\}$ are the possible outcomes of test $o_i \in 
\mathbb O$. A {\em decision tree} for $\mathcal P$ is a labelled tree structure $ \mathbf{T} = 
\langle r, N, E, \mathcal L\rangle$ where:
\begin{compactitem}
  \item $\langle r, N, E\rangle$ is a tree structure with root $r$, set of nodes
  $N$ 
  and set of edges $E \subseteq N \times N$; $N$ is partitioned in a
  set of {\em internal} nodes $N_I$ and a set of {\em leaves} $N_L$.
  \item $\mathcal L$ is a labelling function defined over $N \cup E$.
  \item If $n \in N_I$, $\mathcal L (n) \in \mathbb O$; in other words each internal node is 
  labelled with the name of a test.
  \item If $(n,c) \in E$ then $\mathcal L((n,c)) \in \namestyle{out}(\mathcal L(n))$; that is, 
  an edge directed from $n$ to $c$ is labelled with a possible outcome of the test associated with $n$.
  \item Moreover, if $(n,c_1), (n,c_2) \in E$ and $\mathcal L((n,c_1)) = \mathcal L((n,c_2))$
  then $c_1 = c_2$, and for each $v \in \namestyle{out}(\mathcal L(n))$ there is $c$ such that

  $(n,c) \in E$ and $\mathcal L((n,c)) = v$; that is, $n$ has exactly one outgoing edge for each 
  possible outcome of test $\mathcal L(n)$.
  \item If $l \in N_L$, $\mathcal L(l) \in \mathbb A$; in other words each leaf is labelled with 
  a decision. \theoend
\end{compactitem}
\end{dfn}
When the decision-making agent uses the tree, it starts from the root. Every time it reaches an 
inner node $n$, the agent performs test $\mathcal L(n)$, observes its outcome $v$ and follows the 
$v$-labelled edge. When the agent reaches a leaf $l$, it makes decision $a = \mathcal L(l)$.


\subsection{Building Decision Trees}\label{tdt:subsect:genalgo}

Figure \ref{tdt:genalg} shows a generic recursive 
algorithm that can be used to build a decision
tree starting from a set of \varname{Examples} and a set of \varname{Tests}.

\begin{figure}[h]
\begin{center}
\framebox{
\begin{minipage}{14cm}
\begin{myalgo}
    \alinenum \bfun \funname{BuildTree} (set \varname{Examples}, set \varname{Tests})
    \alinenum \brets a decision tree $\varname{T} = \langle \varname{root}, \varname{Nodes},
                            \varname{Edges}, \varname{Labels}\rangle$
    \alinenum\bbegin
    \blockstart
        \alinenum\bif all $\varname{ex}\in\varname{Examples}$
            correspond to the same decision \bthen\label{tdt:genalg:endrec1}
        \blockstart
            \alinenum\bret \funname{BuildLeaf}(\varname{Examples});
        \blockend
        \alinenum\bif \varname{Tests} is empty \bthen \label{tdt:genalg:endrec2}
        \blockstart
            \alinenum\bret \funname{BuildLeaf}(\varname{Examples});
        \blockend
        \alinenum $\varname{test} \leftarrow$ \funname{ChooseTest}
            ($\varname{Tests}$, $\varname{Examples}$);\label{tdt:genalg:choose}
        \alinenum$\varname{root} \leftarrow$ \bnew node;
        \alinenum$\varname{Nodes} \leftarrow \{\varname{root}\}$;
            $\varname{Edges} \leftarrow \varnothing$;
            $\varname{Labels}(\varname{root}) \leftarrow \varname{test}$;
        \alinenum $\varname{T} \leftarrow \langle \varname{root}, \varname{Nodes},
            \varname{Edges}, \varname{Labels} \rangle$;
        \alinenum $\varname{Tests\_Update} \leftarrow \varname{Tests} \setminus \{ \varname{test} \}$;
            \label{tdt:genalgo:newo}
        \alinenum \bfor \beach possible outcome $\varname{value}$ of \varname{test} \bdo \bbegin
        \blockstart
            \alinenum $\varname{SubExamples} \leftarrow \{\varname{ex} \in \varname{Examples}
                \mid \textrm{\varname{test} has outcome \varname{value}
                in \varname{ex}} \}$;\label{tdt:genalgo:newe}
            \alinenum \bif \varname{SubExamples} is not empty \bthen \bbegin
            \blockstart
                \alinenum $\varname{SubTree} \leftarrow$ \funname{BuildTree}
                    ($\varname{SubExamples}$, $\varname{Tests\_Update}$);
                \alinenum \funname{Append}(\varname{T}, \varname{root}, \varname{SubTree});
                    \label{tdt:genalg:append}
                \alinenum $\varname{Labels}((\varname{root}, \funname{Root}(\varname{SubTree})))
                    \leftarrow \varname{value}$; \label{tdt:genalg:addlab}
            \blockend
            \alinenum \bend ;
        \blockend
        \alinenum \bend ;
        \alinenum \bret \varname{T};\label{tdt:genalg:return}
    \blockend
    \alinenum \bend .
\end{myalgo}
\end{minipage}
}
\end{center}
\caption{Generic algorithm for building a decision tree}\label{tdt:genalg}
\end{figure}

Recursion ends when either the remaining examples do not need further 
discrimination because they all correspond to the same decision, or 
all available observables have been used, and the values observed match cases with different
decisions. 
In the latter case observables are not enough for
getting to the proper decision and if an agent 
is actually using the tree, it should
take into account this.

In case no terminating condition holds, the algorithm chooses
an observable variable \varname{test}
to become the root
label for subtree $\mathbf{T}$.
Depending on how \funname{ChooseTest} is implemented we get
different specific algorithms and different decision trees. 

A subtree is built for each possible outcome \varname{value} of
\varname{test} in a recursive call of \funname{BuildTree}, with sets
\varname{Tests\_Update} and \varname{SubExamples} as inputs. \varname{Tests\_Update} is
obtained by removing \varname{test} from the set of tests, in order to avoid using it
again. \varname{SubExamples} is the subset of
\varname{Examples} containing only those examples that have \varname{value} as outcome
for \varname{test}. 

As mentioned before, there are as many specific algorithms, and, in general,
results, as there are implementations of \funname{ChooseTest}. 
It is in general desirable to generate 
a tree with minimum average depth, for two reasons:
\begin{compactitem}
    \item Minimizing average depth means minimizing the average number of
    tests and thus speeding up the decision process.
    \item In machine learning, a small number of tests also means
    a higher degree of generalization on the particular examples 
    used in building the tree.
\end{compactitem}

\subsection{ID3}
Unfortunately, finding a decision tree with minimum average depth is an
intractable problem; however, there exists a good best-first heuristic for choosing tests in
order to produce trees that are ``not too deep''.
This heuristic was proposed in the \idthree\ algorithm \cite{Quinlan:86}, 
and is base on the concept of {\em entropy}
from {\em information theory}.
In the following we recall this approach in some detail also in order to introduce
some notation which will be used in the rest of the paper.
\begin{dfn} Given a (discrete) probability distribution
$\mathbf{P} = \{ p_1, \ldots, p_n \}$ its {\em entropy} $\mathcal E (\mathbf P)$ is:
\begin{equation}\label{tdt:entropy:prob}
  \mathcal E(\mathbf P) = -\sum_{i=1}^{n} p_i \log_2 p_i
\end{equation}\nopagebreak\theoend
\end{dfn}
Entropy measures the {\em degree of disorder}. When we choose a test, we want it to split the 
examples with the lowest degree of disorder with respect to the decisions associated with them. 

Given a set of examples $\mathbb E$ we introduce the sets:
$$ \restr{\mathbb E}{a} = \{ e \in \mathbb E \mid \textrm{the decision 
associated with example $e$ is $a$}\}. $$ If the set of available decisions is $\mathbb A = \{a_1, 
\ldots, a_n\}$ then $\restr{\mathbb E}{\mathbb A} = \{\restr{\mathbb E}{a_1},\ldots,\restr{\mathbb 
E}{a_n}\}$ is a partition of $\mathbb E$.
\begin{dfn}
    For each $a_i \in \mathbb A$, $i=1,\ldots,n$, we define the
    {\em probability
    of $a_i$ with respect to $\mathbb E$} as follows:
    $$
        P(a_i; \mathbb E) = \frac{|(\restr{\mathbb E}{a_i})|}{|\mathbb E|}
    $$
\theoend
\end{dfn}

It is worth noting that, if examples are endowed with their {\em a priori} probabilities, we can redefine $P(a_i ; \mathbb E)$ in order to take them into account. The basic formulation of \idthree\ assumes however that all examples are equiprobable and it computes the probability distribution from the frequencies of the examples.
    
The entropy of ${\mathbb E}$ is:
\begin{equation} \label{tdt:entropy:wholeset}
    \mathcal E (\mathbb E) = -\sum_{i=1}^n P(a_i;\mathbb
    E)\log_2 P(a_i; \mathbb E).
\end{equation}
If all decisions are equiprobable, we get $\mathcal E(\mathbb E) = \log_2 n$, which is the maximum 
degree of disorder for $n$ decisions. 
If all decisions but one have 
probability equal to $0$, then $\mathcal E(\mathbb E) = 0$: the degree of disorder is minimum. 

Entropy is used as follows for test selection.
A test $o$ with possible
outcomes $v_1, \ldots, v_k$, splits the set of examples into:
$$ \restr{\mathbb E}{o\rightarrow v_i} = \{ e \in \mathbb E \mid \textrm{test $o$
has value $v_i$ in $e$}\}. 
$$ $\restr{\mathbb E}{o} = \{\restr{\mathbb E}{o\rightarrow
v_1}, \ldots , \restr{\mathbb E}{o\rightarrow v_k}\}$ is again a partition of $\mathbb
E$. In particular, if while building the tree we choose test $o$, $\restr{\mathbb
E}{o\rightarrow v_j}$ is the subset of examples we use in building the subtree for the
child corresponding to $v_j$. The lowest the degree of disorder in $\restr{\mathbb
E}{o\rightarrow v_j}$, the closer we are to a leaf. Therefore, following
equation \eqref{tdt:entropy:wholeset}:
$$ \mathcal E (\restr{\mathbb E}{o\rightarrow v_j}) = - \sum_{i=1}^n
P(a_i;\restr{\mathbb E}{o\rightarrow v_j}) \log_2 P(a_i;\restr{\mathbb E}{o\rightarrow
v_i}).
$$

Finally, we define the entropy of a test $o$ as the average entropy on its possible
outcomes:
\begin{dfn}
    The {\em entropy of a test $o$ with respect to a set of
    examples $\mathbb E$} is:
    \begin{equation}\label{tdt:entropy:test}
        \mathcal E(o;\mathbb E) = \sum_{j=1}^k P(o\rightarrow v_j) \mathcal
        E(\restr{\mathbb E}{o\rightarrow v_j}),
    \end{equation}
    where\footnote{Again, if examples are endowed with {\em a priori}
    probabilities, this definition can be changed in order to take them
    into account} $\displaystyle P(o\rightarrow v_j) =
    \frac{|(\restr{\mathbb E}{o\rightarrow v_j})|}{|\mathbb
    E|}$.\theoend
\end{dfn}
The \idthree\ algorithm simply consists of choosing the test with lowest entropy.
Figure \ref{tdt:id3alg} shows the implementation of \funname{ChooseTest} that yields \idthree.

\begin{figure}[h]
\begin{center}
\framebox{
\begin{minipage}{14cm}
\begin{myalgo}
    \alinenum \bfun \funname{ID3ChooseTest} (set \varname{Tests}, set \varname{Examples})
    \alinenum \brets a test \varname{best\_test}
    \alinenum\bbegin
    \blockstart
        \alinenum $\varname{best\_test} \leftarrow$ any element in
            \varname{Tests};
        \alinenum $\varname{min\_entropy} \leftarrow \log_2 |\varname{Examples}|$;
        \alinenum \bfor \beach $\varname{test} \in \varname{Tests}$
            \bdo \bbegin
        \blockstart
            \alinenum $\varname{part} \leftarrow \funname{Partition}(\{ \varname{Examples} \}, 
                \varname{test})$;
            \alinenum $\varname{ent} \leftarrow \funname{Entropy}(\varname{part})$;
            \alinenum \bif $(\varname{ent} <
                \varname{min\_entropy})$ \bthen \bbegin
            \blockstart
                \alinenum $\varname{min\_entropy} \leftarrow
                    \varname{ent}$;
                \alinenum $\varname{best\_test} \leftarrow
                    \varname{test}$;
            \blockend
            \alinenum \bend ;
        \blockend
        \alinenum \bend ;
        \alinenum \bret \varname{best\_test};
    \blockend
    \alinenum \bend .
\end{myalgo}
\end{minipage}
}
\end{center}
\caption{\idthree\ implementation of \funname{ChooseTest}}\label{tdt:id3alg}
\end{figure}


\section{Extending Decision Trees}
\label{tdt:sect}
In this section we formally introduce the notion of temporal decision tree, and we show how timing information can be added to the set of examples used in tree building. Moreover we introduce a model for recovery action that expresses information needed by the algorithm.

\subsection{Temporal Decision Trees}
\label{tdt:subsect:tdtdef}

In section \ref{introtdt} we motivated the monotonicity requirement
for temporal decision trees, so that their traversal requires
information relative to increasing time and then no information
has to be stored.

We now discuss how temporal information is actually included in the tree
and matched with temporal information on the observations.
The tree has to be used when
some abnormal value is detected for some sensor
(fault detection). We then intend the time of fault detection
as the {\em reference time} for temporal labels of observations in the tree.
If we look for example at the data shown in Figure \ref{tdt:example:teset}, we see that, for every fault situation, there is always at least one sensor whose value at time $0$ is different than \namestyle{n}normal. The reason is that, for each fault situation, we associate a $0$ time label to the first snapshot in which there is a sensor showing some deviation from nominal behaviour.

The following definition provides the extension for the temporal
dimension in decision trees.
\begin{dfn}
A {\em temporal decision tree} is a decision tree $\langle r, N_I, N_L, E, \mathcal L
\rangle$ endowed with a time-labelling function $\mathcal T$ such that:
\begin{myenum}
  \item $\mathcal T : N_I \mapsto \realnum^+$; we call $\mathcal T(n)$ a
  {\em time label};
  \item if $n' \in N_I$ and there exist $n$ such that $(n,n') \in E$ (in other words,
  $n'$ is child of $n$), then $\mathcal T(n') \geq \mathcal T(n)$.\label{tdt:tempcond}
  \theoend
\end{myenum}
\end{dfn}

Since we assume not to store any information, but rather to use information
for traversing the tree as dictated by the tree itself,
a first branching for discrimination 
is provided depending on {\em which} is the sensor that
provided such a value. We then assume to have different temporal
decision trees, one for each sensor which could possibly provide
the first abnormal value, or, alternatively, that the root node
has no time label, and the edges from the root are not labelled
with different values of a single observable, but with different
sensors which could provide the first abnormal observation.
Each tree, or subtree in the second alternative, can be
generated independently of the other ones, only using
the examples where the sensor providing fault detection is the same.
This generation is what will be described in the rest of the paper.

Let us tree how a temporal decision tree (or forest, in the case of multiple detecting sensors) can be exploited by an on-board diagnostic agent in order to choose a recovery action. When the first abnormal value is detected, the agent activates a time counter 
and starts visiting the appropriate tree from the root. 
When it reaches an inner node $n$, the agent 
retrieves both the associated test $s = \mathcal L(n)$ and the time label $t = \mathcal T(n)$. 
Then it waits until the time counter reaches $t$, performs test $s$ and chooses one of the child nodes depending on the outcome. When the agent reaches a leaf, it performs the corresponding recovery action.

With respect to the atemporal case, the agent has now the option to wait. From the point of view 
of the agent it may seem pointless to wait when it could look at sensor values, since reading 
sensor values has no cost. However, from the point of view of the tree things are quite different: 
we do not want to add a test that makes the tree deeper and at the same time is not necessary.

Condition \myref{tdt:tempcond} states that the agent can only move forward in time.
This corresponds to the assumption that sensor readings are not stored, discussed in section \ref{introtdt}.

\begin{exm}\label{example:atree}
Let us consider the diagnostic setting described in example \ref{example:teset}. 
Figure \ref{tdt:1stexample} shows a temporal decision tree for such setting, that is a temporal decision tree that uses the sensors and recovery actions mentioned in Figure \ref{tdt:example:teset}. If such a tree is run on the fault situations in the table, a proper recovery action is selected within the deadline. \theoend
\end{exm}

\begin{figure}[h]
\begin{center}{\footnotesize
\includegraphics[scale=0.8, viewport= 20mm 95mm 175mm 160mm, clip=true]{Figures/tdt_tree_1stexample.eps}
}\end{center}
\caption{A temporal decision tree for the situations described in Figure \ref{tdt:example:teset}.}
\label{tdt:1stexample}
\end{figure}

\subsection{Adding Timing Information to the Set of Examples}

In order to generate temporal decision trees, we need temporal information in the examples.
%%Each set of examples is then associated with an ascending sequence of time labels $t_1 < ... < 
%%t_{\namestyle{last}}$, referring to the time elapsed from the instant of fault detection,
%%i.e.\ the first abnormal observation.
%%Then the set of examples can be regarded as a table where:
%%\begin{compactitem}
%%\item Each row corresponds to a fault situation.
%%\item For each sensor $s_i$ {\em and for each time label $t_j$} there is a column 
%%representing the value measured by $s_i$ after a time $t_j$ has elapsed from fault detection, in each fault situation.
%%\item A distinguished column \namestyle{Act} shows the recovery action associated with each fault 
%%situation.
%%\end{compactitem}
%%\begin{compactitem}
%%\item A distinguished column \namestyle{Dl} shows the {\em deadline} by which a recovery action 
%%has to be performed for each fault situation. The deadline is expressed as the last time label 
%%that can be used for that particular fault situation.
%%\end{compactitem}
%%For a given fault situation, sensor values for time labels exceeding the deadline are useless; the 
%%corresponding cells in the table may then be empty without any loss of information. Figure 
%%\ref{tdt:tfstablesketch} sketches how the table may appear; let us give a more formal definition. 
%%\begin{figure}[h]
%%\begin{center}{\footnotesize
%%    \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
%%    & \multicolumn{4}{|c|}{$\namestyle{sens}_1$} & \multicolumn{4}{|c|}{$\ldots$} 
%%    & \multicolumn{4}{|c|}{$\namestyle{sens}_m$} & \namestyle{Act} & \namestyle{Dl}\\ \hline 
%%    & $t_1$ & $t_2$ & $\ldots$ & $t_{\namestyle{last}}$ 
%%    & $t_1$ & $t_2$ & $\ldots$ & $t_{\namestyle{last}}$
%%    & $t_1$ & $t_2$ & $\ldots$ & $t_{\namestyle{last}}$ & & \\ \hline
%%    $\namestyle{sit}_1$ &&&&&&&&&&&&&& \\ \hline
%%    $\ldots$ &&&&&&&&&&&&&& \\ \hline
%%    $\namestyle{sit}_n$ &&&&&&&&&&&&&& \\ \hline
%%    \end{tabular}}
%%\end{center}
%%\caption{Sketch of a te-set}\label{tdt:tfstablesketch}
%%\end{figure}
We already introduced informally the notion of a set of examples (or ``fault situations'') with temporal information when describing the table in Figure \ref{tdt:example:teset}. The following definition formalizes the same notion. 

\begin{dfn}

A {\em temporal example-set (te-set for short)} $\mathbb E$ is a collection of {\em fault 
situations} $\namestyle{sit}_1, \ldots, \namestyle{sit}_n$ characterized by a number of sensors 
$\namestyle{sens}_1, \ldots, \namestyle{sens}_m$ and an ascending sequence of time labels $t_1 < 
\ldots < t_{\namestyle{last}}$ representing the instants in time for which sensor readings are 
available. In this context we call {\em observation} a pair $\langle \namestyle{sens}_i, t_j 
\rangle$. A te-set is organized in a table as follows:
\begin{myenum}
    \item The table has $n$ rows, one for each fault situation.
    \item The table has $m \times \namestyle{last}$ observation columns containing the outcomes of
    the different observations for each fault situation. We denote by 
    $\namestyle{Val}(\namestyle{sit}_h, \langle \namestyle{sens}_i, t_j \rangle)$ the value
    measured by sensor $\namestyle{sens}_i$ at time $t_j$ in fault situation $\namestyle{sit}_h$.
    \item The table has a distinguished column \namestyle{Act} containing the recovery action 
    associated with each fault situation. We denote by $\namestyle{Act}(\namestyle{sit}_h)$ the 
    recovery action associated with $\namestyle{sit}_h$.
    \item The table has a second distinguished column \namestyle{Dl} containing the deadline for 
    each fault situation. We denote by $\namestyle{Dl}(\namestyle{sit}_h)$ the deadline for 
    $\namestyle{sit}_h$, and we have that $\namestyle{Dl}(\namestyle{sit}_h) \in \{ t_1, \ldots, 
    t_{\namestyle{last}} \}$ for each $h = 1, \ldots, n$. We define a {\em global deadline} for a 
    te-set $S$ as $\namestyle{Dl}(S) = \min \{ \namestyle{Dl}(\namestyle{sit}) \mid \namestyle{sit} 
    \in S\}$.
\end{myenum}
We moreover assume that  a probability\footnote{$P(\namestyle{sit};\mathbb E)$ can be computed as 
a frequency, that is $P(\namestyle{sit};\mathbb E) = 1/n$, where $n$ is the number of fault 
situations, or it can be known {\em a priori} and added to the set of examples.} 
$P(\namestyle{sit};\mathbb E)$ is associated with each $\namestyle{sit} \in \mathbb E$  , such 
that $\sum_{\namestyle{sit} \in \mathbb E} P(\namestyle{sit};\mathbb E) = 1$. For every 
$\mathbb{E}' \subset \mathbb E$ and for every $\namestyle{sit} \in \mathbb{E}'$ we introduce the 
following notation: $P(\mathbb{E}';\mathbb E) = \sum_{\namestyle{sit} \in \mathbb{E}'} 
P(\namestyle{sit}; \mathbb{E})$ and $P(\namestyle{sit};\mathbb{E}') = 
\frac{P(\namestyle{sit};\mathbb E)}{P(\mathbb{E}';\mathbb E)}$. \theoend
\end{dfn}

\subsection{A Model for Recovery Actions}\label{actionmodel}
The algorithms we shall introduce require a more detailed model of recovery actions. In particular 
we want to better characterize what happens when it is not possible to uniquely identify {\em the} 
most appropriate recovery action. Moreover, we want to quantify the loss we incur in when this 
happens.

We start with a formal definition:
\begin{dfn}\label{tdt:dfn:actmodel}
A {\em basic model for recovery actions} is a triple $\langle \mathbb A, \prec, \chi \rangle$ 
where:
\begin{myenum}
\item $\mathbb A = \{ a_1, \ldots, a_K \}$ is a finite set of symbols denoting {\em basic recovery 
actions}.
\item $\prec \subseteq \mathbb A \times \mathbb A$ is a partial strict order relation on $\mathbb 
A$. We say that $a_i$ is {\em weaker} than $a_j$, written as $a_i \prec a_j$, if $a_j$ produces 
more recovery effects than $a_i$, in the sense that $a_j$ could be used in place of $a_i$ (but not 
the vice versa). We therefore assume that there are no drawbacks in actions, that is any action can be performed at any time with no negative consequences, apart from the cost of the action itself (see below). This is clearly a limitation and something to be tackled in future work (see the discussion
in section \ref{conclusions}).

\item $\chi: \mathbb A \mapsto \realnum^+$ is the {\em cost} function, and is such that if $a_i 
\prec a_j$ then $\chi (a_i) < \chi (a_j)$. $\chi$ associates a cost with each basic recovery 
action, expressing possible drawbacks of the action itself. Recovery actions performed on-board 
usually imply a performance limitation or the abortion of some ongoing activity; costs are meant 
to estimate monetary losses or inconveniences for the users resulting from these. The requirement 
of monotonicity with respect to $\prec$ stems from the following consideration: if $a_i \prec a_j$ 
and $\chi(a_i) \geq \chi(a_j)$ it would not make any sense to ever perform $a_i$, since $a_j$ 
could be performed with the same effects at the same (or lower) cost. We moreover assume that costs are independent from the fault situation (a consequence of the no-drawbacks assumption mentioned in the previous point). \theoend
\end{myenum}
\end{dfn}
\begin{exm}\label{example:actmodel:basic}
Let us consider again the four recovery actions $a,b,c,d$ that appear in the te-set of Figure \ref{tdt:example:teset}. Figure \ref{tdt:actions:basic:example} shows a basic action model for them. The graph expresses the oredering relation $\prec$, while costs are shown next to action names.
\theoend 
\end{exm}
\begin{figure}[h]
\begin{center}
\footnotesize
\setlength{\unitlength}{1mm}
\begin{picture}(50,39)
\put(9,0){\makebox{\includegraphics[scale=0.6, viewport= 4cm 18cm 9.7cm 24.5cm, clip=true]{Figures/tdt_example_actmodel_a.eps}}}
\put(29,35){$a$ - $\chi$: $100$}
\put(29,1){$d$ - $\chi$: $10$}
\put(0.5,17.5){$b$ - $\chi$: $20$}
\put(38,17.5){$c$ - $\chi$: $50$}
\end{picture}
\end{center}
\caption{A basic action model.}\label{tdt:actions:basic:example}
\end{figure}

We have seen in the previous section that with each fault situation is associated a recovery 
action; usually this association depends on the fault, but it may also depend on the operating 
conditions in which the fault occurs. 

What happens when we cannot discriminate multiple fault 
situations? In section \ref{tdt:subsect:genalgo}, while outlining the generic algorithm for the 
atemporal case, we referred the solution to the decision-making agent. In this case we want to be 
more precise.
\begin{dfn}\label{tdt:dfn:merge}
Let $\langle \mathbb A, \prec, \chi \rangle$ be a basic model for recovery actions. We define the 
function $\namestyle{merge}: 2^{\mathbb A} \mapsto 2^{\mathbb A}$ as follows:
\begin{equation}\label{tdt:eq:mergedef}
\namestyle{merge}(S) = \{ a_i \in S \mid \textrm{there is no $a_j \in S$ such that $a_i \prec a_j$}\}
\end{equation}
We moreover define:
\begin{equation}
\namestyle{merge-set}(\mathbb A) = \{ \namestyle{merge}(S) \mid S \in 2^{\mathbb A} \} \subseteq 
2^{\mathbb A} 
\end{equation}
$\namestyle{merge-set}(\mathbb A)$ is the set of {\em compound recovery actions} which includes basic 
recovery actions in the form of singletons. \theoend
\end{dfn}
The intuition behind \namestyle{merge} is that when we cannot discriminate multiple fault 
situations we simply merge the corresponding recovery actions. This means that we collect all 
recovery actions, and then remove the unnecessary ones (equation \eqref{tdt:eq:mergedef}). An action 
in a set becomes unnecessary when the set contains a stronger action. Thus given a te-set $\mathbb E$, we define:
\begin{equation}
\namestyle{Act}(\mathbb E) = \namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit}) \mid \namestyle{sit} \in \mathbb E \}).
\end{equation}

If we take into account compound actions, we can extend the notion of model for recovery actions as follows:
\begin{dfn}\label{tdt:def:extactmodel}
Let $\mathbf A = \langle \mathbb A, \prec, \chi \rangle$ be a basic model for recovery actions. An 
{\em extended model} for $\mathbf A$ is a triple $\langle \mathbb A, \prec_{\namestyle{ext}}, 
\chi_{\namestyle{ext}} \rangle$ where:
\begin{myenum}
\item $\prec_{\namestyle{ext}} \subseteq \namestyle{merge-set}(\mathbb A) \times 
\namestyle{merge-set}(\mathbb A)$ and given $A, A' \in \namestyle{merge-set}(\mathbb A)$, $A 
\prec_{\namestyle{ext}} A'$ if for every $a \in A$ either $a \in A'$ or there exists $a' \in A'$ 
such that $a \prec a'$. Notice that $\{ a_i \} \prec_{\namestyle{ext}} \{a_j\}$ if and only if $a_i \prec 
a_j$.
\item $\chi_{\namestyle{ext}} : \namestyle{merge-set}(\mathbb A) \mapsto \realnum^+$ is a cost function 
over compound actions such that for every $A \in \namestyle{merge-set}(\mathbb A)$, $\max_{a \in A} 
\chi(a) \leq \chi_{\namestyle{ext}}(A) \leq \sum_{a \in A}$. Moreover, if $A \prec_{\namestyle{ext}} A'$ then it 
must hold that $\chi_{\namestyle{ext}}(A) < \chi_{\namestyle{ext}} (A')$.
\end{myenum}
\end{dfn}
While $\prec_{\namestyle{ext}}$ is uniquely determined by $\prec$, the same does not hold for 
$\chi_{\namestyle{ext}}$: for this reason there is more than one extended model for any basic 
model. 
The requirement that $\max_{a \in A} \chi(a) \leq \chi_{\namestyle{ext}}(A)$ is motivated as follows: if there existed $a \in A$ such that $\chi_{\namestyle{ext}}(A) \leq \chi(a)$ then it 
would make sense never to perform $a$, substituting it for $A$. In fact, $\{ a \} 
\prec_{\namestyle{ext}} A$ and $A$ would have the same or lower cost. We also ask 
$\chi_{\namestyle{ext}}$ - as we did for basic models - to be monotonic with respect to 
$\prec_{\namestyle{ext}}$.

In the following we shall consider only extended models for recovery actions, thus we shall drop the 
\namestyle{ext} prefix from both $\prec$ and $\chi$.

\begin{exm}\label{example:actmodel:ext}
Figure \ref{tdt:example:actmodel} shows a possible extension for the basic model in Figure \ref{tdt:actions:basic:example}. In this case the cost of the compound action $\{b,c\}$ is given by the sum of the individual costs of $b$ and $c$. \theoend
\end{exm}
\begin{figure}[h]
\begin{center}
\footnotesize
\setlength{\unitlength}{1mm}
\begin{picture}(54,39)
\put(11,0){\makebox{\includegraphics[scale=0.6, viewport= 4cm 18cm 9.7cm 24.5cm, clip=true]{Figures/tdt_example_actmodel_b.eps}}}

\put(30.2,34.7){$\{a\}$ - $\chi$: $100$}
\put(30.2,1){$\{d\}$ - $\chi$: $10$}
\put(30.2,26.3){$\{b,c\}$ - $\chi$: $70$}
\put(0,13.5){$\{b\}$ - $\chi$: $20$}
\put(40,13.5){$\{c\}$ - $\chi$: $50$}
\end{picture}
\end{center}
\caption{An extended action model.}\label{tdt:example:actmodel}
\end{figure}

\section{The Problem of Building Temporal Decision Trees}
In this section we outline the peculiarities of building temporal decision trees, showing the differences with respect to the ``traditional'' case.
\label{buildingtdt}
\subsection{The Challenge of Temporal Decision Trees}\label{sect:challenge}
What makes the generation of temporal decision trees more difficult from standard ones is the requirement that time labels do not decrease when moving from the root to the leaves: this corresponds to assuming that sensor values cannot be stored; when the decision-making agent decides to wait it gives up using all values that sensors show while it is waiting.

If we release this restriction we can actually generate temporal decision trees with a minor variation of \idthree, essentially by considering each pair formed by a sensor and a time label as an individual test.
In other words \funname{ID3ChooseTest} selects a sensor $s$ and a time label $t$ such that reading $s$ at time $t$ allows for the maximum discrimination among examples.

However in systems as the ones we are considering, that is low-memory real-time systems, the possibility of performing the diagnostic task without discarding dynamics but also without having to store sensor values across time is a serious issue to take into account. For this reason the definition of temporal decision tree includes the requirement that time labels be not decreasing on root-leaf paths. 

Figure \ref{tdt:algo:temp:generic} shows a generic algorithm for building temporal decision trees that can help us outline the difficulties of the task. Line \ref{tdt:genalg:temp:valobs} shows a minor modification aimed at taking into account deadlines: an observation can be used on a given set of examples only if its time label does not exceed its global deadline. Violating this condition would result in a tree that selects a recovery action only after the deadline for the corresponding fault situation has expired.

\begin{figure}[h]
\begin{center}
\framebox{
\begin{minipage}{14cm}
\begin{myalgo}
    \alinenum \bfun \funname{BuildTemporalTree} (te-set \varname{Examples}, set \varname{Obs},
    action model \varname{ActModel})
    \alinenum \brets a temporal decision tree $\varname{T} = 
    \langle \varname{root}, \varname{Nodes}, \varname{Edges}, \varname{Labels},
    \varname{TLabels} \rangle$
    \alinenum\bbegin
    \blockstart
        \alinenum\bif for all $\varname{sit}\in\varname{Examples}$
            $\namestyle{Act}(\varname{sit})$ is the same \bthen
        \blockstart
            \alinenum\bret \funname{BuildLeaf}(\varname{Examples}, \varname{ActModel});
        \blockend
        \alinenum $\varname{deadline} \leftarrow \namestyle{Dl}(\varname{Examples})$;
        \alinenum $\varname{UsefulObs} \leftarrow \{ \varname{o}\in \varname{Obs} \mid \textrm{$\exists 
        \varname{s1}, \varname{s2} \in \varname{Examples}$ s.t. $\namestyle{Val}(\varname{s1}, 
        \varname{o}) \neq \namestyle{Val}(\varname{s2}, \varname{o})$} \} $;
        \alinenum $\varname{ValidObs} \leftarrow \{ \langle \varname{sensor}, \varname{tlabel} 
        \rangle \in \varname{UsefulObs} \mid \varname{tlabel} \leq \varname{deadline} \}$; \label{tdt:genalg:temp:valobs}
        \alinenum\bif \varname{ValidObs} is empty \bthen 
        \blockstart
            \alinenum\bret \funname{BuildLeaf}(\varname{Examples}, \varname{ActModel});
        \blockend
        \alinenum $\langle\varname{sensor}, \varname{tlabel}\rangle \leftarrow$ 
        \funname{ChooseObs}
        ($\varname{ValidObs}$, $\varname{Examples}$, $\varname{ActModel}$);
        \alinenum$\varname{root} \leftarrow$ \bnew node;
        \alinenum$\varname{Nodes} \leftarrow \{\varname{root}\}$;
            $\varname{Edges} \leftarrow \varnothing$;
            $\varname{Labels}(\varname{root}) \leftarrow \varname{sensor}$;
            $\varname{TLabels}(\varname{root}) \leftarrow \varname{tlabel}$; 
        \alinenum $\varname{T} \leftarrow \langle \varname{root}, \varname{Nodes},
            \varname{Edges}, \varname{Labels}, \varname{TLabels} \rangle$;
        \alinenum $\varname{Obs\_Update} \leftarrow 
            \{ \langle \varname{sens}, \varname{tst} \rangle \in \varname{UsefulObs} \mid \varname{tst} 
            \geq \varname{tlabel} \}$; \label{tdt:genalgo:temp:obsupd}
        \alinenum \bfor \beach possible measure $\varname{value}$ of \varname{sensor} \bdo \bbegin 
        \label{tdt:genalgo:temp:mainloop}
        \blockstart
            \alinenum $\varname{SubExamples} \leftarrow \{\varname{sit} \in \varname{Examples}
                \mid \namestyle{Val}(\varname{sit},\langle \varname{sensor},\varname{tlabel} 
                \rangle) = \varname{value} \}$; \label{tdt:genalgo:temp:partition}
            \alinenum \bif \varname{SubExamples} is not empty \bthen \bbegin
            \blockstart
                \alinenum $\varname{SubTree} \leftarrow$ \funname{BuildTemporalTree}
                    (\varname{SubExamples}, \varname{Obs\_Update}, \varname{ActModel});
                \alinenum \funname{Append}(\varname{T}, \varname{root}, \varname{SubTree});
                \alinenum $\varname{Labels}((\varname{root}, \funname{Root}(\varname{SubTree})))
                    \leftarrow \varname{value}$;
            \blockend
            \alinenum \bend ;
        \blockend
        \alinenum \bend ;
        \alinenum \bret \varname{T};
    \blockend
    \alinenum \bend .
\nolinenum
    \alinenum \bfun \funname{BuildLeaf} (te-set \varname{Examples}, action model 
    \varname{ActModel})\label{tdt:loose:algo:buildleaf}
    \alinenum \brets a loose temporal decision tree $\varname{T} = 
    \langle \varname{leaf}, \{\varname{leaf}\}, \varnothing, \varname{Labels},
    \varnothing \rangle$
    \alinenum\bbegin
    \blockstart
        \alinenum $\varname{all\_act} \leftarrow \{ \namestyle{Act}(\varname{sit}) \mid
            \varname{sit} \in \varname{Examples} \}$;
        \alinenum $\varname{comp\_act} \leftarrow \namestyle{merge}(\varname{all\_act})$;
        \alinenum $\varname{leaf} \leftarrow$ \bnew node;
        $\varname{Labels}(\varname{leaf}) \leftarrow \varname{comp\_act}$;
        $\varname{T} \leftarrow \langle \varname{leaf}, \{ \varname{leaf} \},
        \varnothing, \varname{Labels}, \varnothing \rangle$;
        \alinenum \bret \varname{T};
    \blockend
    \alinenum \bend .\label{tdt:loose:algo:buildleafend}
\end{myalgo}
\end{minipage}
}
\end{center}
\caption{Generic algorithm for building a temporal decision tree} \label{tdt:algo:temp:generic} 

\end{figure}

The major change with respect to the standard algorithm is however shown in line \ref{tdt:genalgo:temp:obsupd}: once we select an 
observation pair $\langle \varname{sensor}, \varname{tlabel} \rangle$ we must remove from the set 
of observations all those pairs whose time label is lower than \varname{tlabel}\footnote{Actually this assumes that reading a sensor and moving downwards the tree accordingly can be done so swiftly that the qualitative sensor values have no time to change in the meanwhile. If this is not the case, one can choose to remove also the pairs with time labels equal to \varname{tlabel}, or more generally those with time labels lower than $\varname{tlabel}+k$ where $k$ is the time needed by the diagnostic agent to carry out tree operations. For the sake of simplicity, however, in the following we will assume that $k$ is $0$, since the choice of $k$ does not affect the approach we propose.}.

As a consequence of these operations - ruling out invalid observations and discarding those that are in the past - the set of observations available when building a child node can be different from the one used for its parent in more than one way:

\begin{compactitem}
    \item Some observations can be invalid for the parent and valid for the child. The recursive 
    call for the child works on a smaller set of examples; therefore the global deadline may be 
    further ahead in time, allowing more observations to be used.
    \item Some observations can become unavailable for the child because 
    they have a time label lower than that used for the parent.
\end{compactitem}
Of course the problematic issue is the latter: some observations are lost, and among them there 
may be some information which is {\em necessary} for properly selecting a recovery action.

\begin{figure}[h]
\begin{center}{\footnotesize
    \begin{tabular}{|l|c|c|c|} \hline
    & $\langle s,0\rangle$ & $\langle s,1 \rangle$ & \namestyle{Act} \\ \hline 
    $\namestyle{sit}_1$  & x & x & a\\ \hline
    $\namestyle{sit}_2$  & x & y & b\\ \hline
    $\namestyle{sit}_3$  & y & y & c\\ \hline
    $\namestyle{sit}_4$  & y & z & d\\ \hline
    \end{tabular}}
\end{center}
\caption{A te-set causing some problems to standard \idthree\ algorithm if used for temporal decision trees.}\label{tdt:fig:badexm}
\end{figure}

Let us consider as an example the te-set in Figure \ref{tdt:fig:badexm}, with four fault situations, two time labels ($0$ and $1$) and only one sensor ($s$). Each fault situation is characterized by a different recovery action, and the te-set obviously allows to discriminate all of them. However the entropy criterion would first select the observation $\langle s, 1 \rangle$, which is more discriminating. The observation $\langle s, 0 \rangle$ would then become unavailable, and the resulting tree could never discriminate $\namestyle{sit}_2$ and $\namestyle{sit}_3$. 

%%Let us 
%%consider an extreme case: at the first call \funname{ID3ChooseTest} selects an observation whose 
%%time label is $t_{\namestyle{last}}$, that is the maximum possible, because with the best-first search with entropy as an heuristic this turns out to be the ``best'' observations, that is the most discriminating one. This means that in building 
%%most of the tree the algorithm will be able to use only observations with time label equal to 
%%$t_{\namestyle{last}}$, actually discarding most of the observations and of the information in the 
%%original set of examples.

This shows that there is a relevant difference between building standard decision trees and building temporal decision trees. 
Let us look again at the generic algorithm for standard decision trees presented in Figure 
\ref{tdt:genalg}: the particular strategy implemented in \funname{ChooseTest} does not affect the 
capability of the tree of selecting the proper recovery action, but only the size of the tree. 
Essentially the tree contains the same information as the set of examples - at least for what 
concerns the association between observations and recovery actions. We can say that {\em the tree 
has always the same discriminating power as the set of examples}, meaning that the only case when 
the tree is not capable of deciding between two recovery actions is when the set of examples 
contains two fault situations with identical observations and different actions.

If we consider the algorithm in Figure \ref{tdt:algo:temp:generic} we see that the order in which observations are selected - that is, the particular implementation of \funname{ChooseObs} - can affect the discriminating power of the tree, and not only its size. Since from one recursive 
call to the following some observations are discarded, we can obtain a tree with {\em less 
discriminating information than the original set of examples}. Our primary task is then to avoid 
such a situation, that is to build a tree which is small, but which does not sacrifice relevant 
information. As a consequence, we cannot exploit the strategy of simply selecting an observation 
with minimum entropy.

In the next sections we shall formalize the new requirements for the output tree, and propose an 
implementation of \funname{ChooseObs} which meets them.
\subsection{Each Tree Has a Cost}

In the previous section we informally introduced the notion of discriminating power. In this section we shall introduce a more general notion of {\em expected cost} of a temporal decision tree. Intuitively, the expected cost associated with a temporal decision tree is the expected cost of a recovery action selected by the tree, with respect to the probability distribution of the fault situations. 

Expected cost is a stronger notion than discriminating power: on the one hand if a tree discriminates better than another, than it has also a lower expected cost (we shall soon prove this statement). On the other hand expected cost adds something to the notion of discriminating power, since any two trees are comparable from the point of view of cost, while they may not be from the point of view of the discrimination they carry out.

Before defining expected cost, we need to introduce some preliminary definitions.

We shall make use of a function, named \namestyle{examples}, that given an initial set of examples $\mathbb E$ and a tree $\mathbf T$ associates to each node of the tree a subset of $\mathbb E$. To understand the meaning of such a function before formally defining it, let us imagine to run the tree on $\mathbb E$ and at a certain point of the decision process to reach a node $n$: \namestyle{examples} tells us which is the subset of fault situations which we have not yet discarded. 
\begin{dfn}\label{tdt:dfn:examples}
Let $\mathbb E$ be a te-set with sensors $s_1, \ldots, s_m$, time labels $t_1, \ldots, 
t_{\namestyle{last}}$ and actions model $\langle \mathbb A, \prec, \chi \rangle$. Moreover let 
$\mathbf T = \langle r, N, E, \mathcal L, \mathcal T \rangle$ be a temporal decision tree such 
that for every internal node $n \in N$ we have $\mathcal L(n) \in \{s_1, \ldots,s_m \}$ and 
$\mathcal T(n) \in \{ t_1, \ldots, t_{\namestyle{last}} \}$. We define a function 
$\namestyle{examples}(\cdot ; \mathbb E): N \mapsto 2^{\mathbb E}$ as follows:
\begin{multline}
\namestyle{examples}(r;\mathbb E) = \mathbb E \quad \textrm{where $r$ is the root of $\mathbf T$;}\\
\shoveleft{\namestyle{examples}(n ; \mathbb E) = \{ \namestyle{sit} \in \namestyle{examples}(p; \mathbb E) 
\mid \namestyle{Val}(\namestyle{sit}, \langle \mathcal L (p), \mathcal T(p) \rangle) = \mathcal 
L((p,n)) \} }
\\ \textrm{where $n \in N$, $n \neq r$ and $(p,n) \in E$.}
\end{multline}
\namestyle{examples} is well defined since for any $n \in N$ different from the root there exists 
exactly one $p \in N$ such that $(p,n) \in E$. \theoend
\end{dfn}
Notice that, if $\mathbb E$ is the set of examples used for building $\mathbf T$, $\namestyle{examples}(n; \mathbb E)$ corresponds to the subset of examples used while creating node $n$.

\begin{exm}\label{example:examples}
Let us consider Figure \ref{tdt:examplesfun:example}: it shows the same tree as Figure \ref{tdt:1stexample}, but for every node $n$ we can also see the set of fault situations $\namestyle{examples}(n;\mathbb E)$, where $\mathbb E$ is the te-set of Figure \ref{tdt:example:teset}. \theoend
\end{exm}
\begin{figure}[h]
\begin{center}{\footnotesize
\includegraphics[scale=0.8, viewport= 20mm 95mm 175mm 180mm, clip=true]{Figures/tdt_examplesfun_example.eps}
}\end{center}
\caption{A temporal decision tree showing the value of $\namestyle{example}(n,\mathbb E)$.}
\label{tdt:examplesfun:example}
\end{figure}

In the following when using function \namestyle{examples} we shall omit the second argument, denoting the initial te-set, when there is no ambiguity about which te-set is considered.

Not every tree can be used on a given set of examples: actually we need some compatibility between the two, which is characterized by the following definition.
\begin{dfn}
Let $\mathbb E$ be as in previous definition. We say that a temporal decision tree $T = \langle r, 
N, E, \mathcal L, \mathcal T \rangle$ is {\em compatible with $\mathbb E$} if:
\begin{compactitem}
\item For every internal node $n \in N$, $\mathcal L(n) \in \{ s_1,\ldots, s_m \}$, $\mathcal T(n) 
\in \{ t_1, \ldots, t_{\namestyle{last}} \}$ and $\mathcal T(n) \leq 
\namestyle{Dl}(\namestyle{examples}(n;\mathbb E))$.
\item For every leaf $l \in N$, $\mathcal L (l) \in \namestyle{merge}(\mathbb A)$ and $\mathcal 
L(l) = \namestyle{merge}(\namestyle{Act}(\namestyle{examples}(l; \mathbb E)))$.
\end{compactitem}
\end{dfn}
It is straightforward to see that a tree is compatible with the set of examples used in building it.

We have the following property\footnote{For the sake of readability, all proofs are collected in a separate appendix at the end of the paper.}:
\begin{prp}\label{prp:1}
Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T\rangle$ be a temporal decision tree compatible with a te-set $\mathbb E$. Let $l_1, \ldots, l_f \in N$ denote the leaves of $T$. Then 
$\namestyle{examples}(l_1), \ldots, \namestyle{examples}(l_f)$ is a partition of $\mathbb E$.
\end{prp}

For each $\namestyle{sit} \in \mathbb E$ we then denote by $\namestyle{leaf}_{\mathbf T}
(\namestyle{sit})$ the unique leaf $l$ of $\mathbf T$ such that $\namestyle{sit} \in 
\namestyle{examples}(l)$. We are now ready to formalize the notion of discriminating power.
\begin{dfn}\label{tdt:dfn:discrpow}
Let $\mathbf T = \langle r_{\mathbf T}, N_{\mathbf T}, E_{\mathbf T}, \mathcal{L}_{\mathbf T}, 
\mathcal{T}_{\mathbf T} \rangle$, $\mathbf U = \langle r_{\mathbf U}, N_{\mathbf U}, E_{\mathbf 
U}, \mathcal{L}_{\mathbf U}, \mathcal{T}_{\mathbf U} \rangle$ denote two temporal decision trees 
compatible with the same te-set $\mathbb E$. Let moreover $\langle \mathbb A, \prec, \chi \rangle$ be 
the recovery action model used in building $\mathbf T$ and $\mathbf U$. We say that $\mathbf T$ is 
{\em more discriminating than $\mathbf U$ with respect to $\mathbb E$} if:
\begin{myenum}
\item for every $\namestyle{sit} \in \mathbb E$ either $\mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T} (\namestyle{sit})) \prec \mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} (\namestyle{sit}))$ or 
$\mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T} (\namestyle{sit})) = \mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} (\namestyle{sit}))$;
\item there exists $\namestyle{sit} \in \mathbb E$ such that $\mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T} (\namestyle{sit})) \prec \mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} (\namestyle{sit}))$. \theoend
\end{myenum}
\end{dfn}
Notice that the second condition makes sure that the two trees are not equal (in which case they would be {\em equally discriminating}), something that the first condition alone cannot guarantee.

\begin{exm}\label{example:discrimination}
Let us consider the tree in Figure \ref{tdt:examplesfun:example} above and the tree in Figure \ref{tdt:tree:2ndexample} below. The former is more discriminating than the latter. In fact, the two trees associate the same actions to $\namestyle{sit}_1, \namestyle{sit}_2, \namestyle{sit}_3, \namestyle{sit}_4, \namestyle{sit}_5$ and $\namestyle{sit}_6$. However the former associates action $b$ with $\namestyle{sit}_7$ and action $c$ with $\namestyle{sit}_8$, while the latter associates to both $\namestyle{sit}_7$ and $\namestyle{sit}_8$ the compound action $\{b,c\}$. \theoend
\end{exm}

Unfortunately we cannot easily use discriminating power -  as defined above - as a preference 
criterion for decision trees. The reason is that it does not define a {\em total} order on 
decision trees, but only a partial one. The following situations may arise:

\begin{compactitem}
\item For some $\namestyle{sit}$, $\mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T}
(\namestyle{sit})) \prec \mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} 
(\namestyle{sit}))$; for some other $\namestyle{sit}$, $\mathcal{L}_{\mathbf U} 
(\namestyle{leaf}_{\mathbf U} (\namestyle{sit})) \prec \mathcal{L}_{\mathbf T} 
(\namestyle{leaf}_{\mathbf T} (\namestyle{sit}))$.
\item For a given $\namestyle{sit}$, $\mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T} 
(\namestyle{sit})) \nprec \mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} 
(\namestyle{sit}))$, nor $\mathcal{L}_{\mathbf U} (\namestyle{leaf}_{\mathbf U} (\namestyle{sit})) 
\nprec \mathcal{L}_{\mathbf T} (\namestyle{leaf}_{\mathbf T} (\namestyle{sit}))$. 
\end{compactitem}
From the point of view of discriminating power alone, it is reasonable for $\mathbf T$ and 
$\mathbf U$ not to be comparable in the above cases. Nonetheless, there may be a reason for 
preferring one over the other, and this reason is {\em cost}. For example if we consider the 
second situation, even if $\mathcal{L}_{\mathbf T}(\namestyle{sit})$ and $\mathcal{L}_{\mathbf 
U}(\namestyle{sit})$ are not directly comparable from the point of view of their strength, one of 
the two may be cheaper than the other and thus preferable. 

We therefore introduce the notion of expected cost of a tree.
\begin{dfn}\label{tdt:dfn:expcost}
Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T \rangle$ be a temporal decision tree 
compatible with a te-set $\mathbb E$ and an action model $\mathbf A = \langle \mathbb A, \prec, \chi 
\rangle$. We inductively define an {\em expected cost} function $\mathcal{X}_{\mathbb E,\mathbf A} 
: N \mapsto \realnum^+$ on tree nodes as follows: 
\begin{equation}
\mathcal{X}_{\mathbb E,\mathbf A} (n) = 
\begin{cases} 
\displaystyle \chi ( \mathcal L (l)) & \textrm{if $l \in N$ is a leaf;}\\
\displaystyle \sum_{c: (n,c) \in E} P(\mathcal L(n) \rightarrow \mathcal L((n,c))) \cdot 
\mathcal{X}_{\mathbb E,\mathbf A} (c) & \textrm{if $n \in N$ is an inner node.}
\end{cases}
\end{equation}
where $P(\mathcal L(n) \rightarrow \mathcal L((n,c)))$ is the probability of sensor $\mathcal L(n)$ showing a value $v = \mathcal L((n,c))$ and is given by:
$$ P(\mathcal L(n) \rightarrow \mathcal L((n,c))) = \frac{P(\namestyle{examples}(c);\mathbb E)}
{P(\namestyle{examples}(n);\mathbb E)} = P(\namestyle{examples}(c);\namestyle{examples}(n)). $$
The {\em expected cost of $\mathbf T$ with respect to $\mathbb E$ and $\mathbf A$}, denoted by 
$\mathcal{X}_{\mathbb E,\mathbf A}(\mathbf T)$ , is then defined as:
\begin{equation}
\mathcal{X}_{\mathbb E,\mathbf A} (\mathbf T) = \mathcal{X}_{\mathbb E,\mathbf A} (r) \quad 
\textrm{where $r$ is the root of $\mathbf T$}
\end{equation}
\theoend
\end{dfn}

The above definition states that:
\begin{compactitem}
\item The expected cost of a tree leaf $l$ is simply the cost of its recovery action $\mathcal 
L(l)$;
\item The expected cost of an inner node $n$ is given by the weighted sum of its children's expected 
costs; weight for child $c$ is given by the probability $P(\mathcal L(n) \rightarrow \mathcal L((n,c)))$.
\item The expected cost of a temporal decision tree $\mathbf T$ is the expected cost of its root.
\end{compactitem}
%%The expected cost of a tree depends on the te-set and the actions model over which it is built; 
%%however in the following we will consider this to be implicitly stated and we will remove 
%%subscripts $\namestyle{SIT},\mathbf A$ from function $\mathcal X$. 

The following proposition states that the weighted sum for computing the expected cost of the root can be performed directly on tree leaves.
\begin{prp}\label{prp:2}
Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T \rangle$ denote a temporal decision tree, and let $l_1, \ldots, l_u$ be its leaves. Then
\begin{equation}
\mathcal X_{\mathbb E,\mathbf A}(\mathbf T) = \sum_{i=1}^u  \chi(\mathcal L(l_i)) \cdot 
P(\namestyle{examples}(l); \mathbb E)  \label{tdt:eq:expcost1}
\end{equation}
\end{prp}

The next proposition shows that expected cost is monotonic with respect to the ``better discrimination'' relation, and therefore it is a good preference criterion for temporal 
decision trees, since a tree with the lowest possible expected cost is the most discriminating 
one, and moreover it is the cheapest among equally discriminating trees.
\begin{prp}\label{tdt:prp:xpcost:2}
Let $\mathbf T = \langle r_{\mathbf T}, N_{\mathbf T}, E_{\mathbf T}, \mathcal{L}_{\mathbf T}, 
\mathcal{T}_{\mathbf T} \rangle$, $\mathbf U = \langle r_{\mathbf U}, N_{\mathbf U}, E_{\mathbf 
U}, \mathcal{L}_{\mathbf U}, \mathcal{T}_{\mathbf U} \rangle $ be two temporal decision trees 
compatible with the same te-set $\mathbb E$ and the same actions model $\mathbf A$. If $\mathbf T$ is 
more discriminating than $\mathbf U$ then $\mathcal{X}_{\mathbb E, \mathbf A}(\mathbf T) < 
\mathcal{X}_{\mathbb E,\mathbf A}(\mathbf U)$.
\end{prp}

%%\vspace{-8mm}
\begin{figure}[t]
\begin{center}{\footnotesize
\includegraphics[scale=0.8, viewport= 30mm 112mm 175mm 177mm, clip=true]{Figures/tdt_tree_2ndexample.eps}
}\end{center}
\caption{A temporal decision tree less discriminating than the one in Figure \ref{tdt:examplesfun:example}.}
\label{tdt:tree:2ndexample}
\end{figure}

\begin{exm}\label{example:xcost}
Let us compute the expected cost of tree $\mathbf{T}_1$ in Figure \ref{tdt:examplesfun:example} and of tree $\mathbf{T}_2$ in Figure \ref{tdt:tree:2ndexample}, with respect to the te-set $\mathbb E$ in Figure \ref{tdt:example:teset} and the action model $\mathbf{A}$ in Figure \ref{tdt:example:actmodel}. We shall assume that all fault situations are equiprobable, that is each of them has probability $1/8$. By exploiting proposition \ref{prp:2} we obtain:
\begin{eqnarray*}
\mathcal X_{\mathbb E,\mathbf A}(\mathbf{T}_1) & = & P(\namestyle{sit}_1)\chi(a) + P(\namestyle{sit}_7)\chi(b) +  P(\namestyle{sit}_6)\chi(d) + P(\namestyle{sit}_3)\chi(b) + P(\namestyle{sit}_4)\chi(c) + \\
&& + P(\{\namestyle{sit}_2, \namestyle{sit}_5\})\chi(\{b,c\}) +P(\namestyle{sit}_8)\chi(c) =\\
& = & \frac{1}{8} \cdot 100 + \frac{1}{8} \cdot 20 + \frac{1}{8} \cdot 10 + \frac{1}{8} \cdot 20 + \frac{1}{8} \cdot 50 + \frac{1}{4} \cdot 70 + \frac{1}{8} \cdot 50 =\\
& = & 12.5 + 2.5 + 1.25 + 2.5 + 6.25 + 17.5 + 6.25 = 48.75\\
\mathcal X_{\mathbb E,\mathbf A}(\mathbf{T}_2) & = & P(\namestyle{sit}_1)\chi(a) + P(\namestyle{sit}_6)\chi(d) + P(\namestyle{sit}_3)\chi(b) + P(\namestyle{sit}_4)\chi(c) +\\
&& + P(\{\namestyle{sit}_2, \namestyle{sit}_5, \namestyle{sit}_7, \namestyle{sit}_8\})\chi(\{b,c\}) =\\
& = & \frac{1}{8} \cdot 100 + \frac{1}{8} \cdot 10 + \frac{1}{8} \cdot 20 + \frac{1}{8} \cdot 50 + \frac{1}{2} \cdot 70 = \\
& = & 12.5 + 1.25 + 2.5 + 6.25 + 35 = 57.5
\end{eqnarray*}
We can see that the less discriminating tree, that is $\mathbf{T}_2$, has a higher expected cost.
\theoend
\end{exm}
\subsection{Restating the Problem}\label{tdt:subsect:problem}
In the previous section we introduced expected cost as a preference criterion for decision trees. 
Given this notion, we can restate the problem of building temporal decision tree as that of building a tree with minimum possible expected cost. This section formally shows that the notion of ``minimum possible expected cost'' is well defined, and more precisely it corresponds to the cost of a tree that exploits all observations in the te-set. The goal can then be expressed as {\em finding a reasonably small tree among those whose expected cost is minimum}.

In this section, as well as formalizing the above mentioned notions, we introduce some formal machinery that will be useful in proving the correctness of our algorithm.

\begin{dfn}
Let $\mathbb E$ denote a te-set. Moreover, let $t_1, \ldots, t_{\namestyle{last}}$ denote the 
time labels of $\mathbb E$. We say that $\namestyle{sit}_i, \namestyle{sit}_j \in \mathbb E$ are 
{\em pairwise indistinguishable}, and we write $\namestyle{sit}_i \thicksim \namestyle{sit}_j$, if 
for all $t_i < \min\{\namestyle{Dl}(\namestyle{sit}_i), \namestyle{Dl}(\namestyle{sit}_j)\}$ and 
for all sensors $s$ we have that $\namestyle{Val} (\namestyle{sit}_i , \langle s, t_i \rangle) = 
\namestyle{Val} (\namestyle{sit}_j, \langle s, t_i \rangle)$. \theoend
\end{dfn}
As a relation, $\thicksim$ is obviously reflexive and symmetric, but it is not transitive. If we 
consider a $\namestyle{sit}_k$ with a particularly strict deadline, it might well be that 
$\namestyle{sit}_i \thicksim \namestyle{sit}_k$, $\namestyle{sit}_k \thicksim \namestyle{sit}_j$, 
but $\namestyle{sit}_i \nsim \namestyle{sit}_j$. We now introduce a new relation $\approx$ which 
is the transitive closure of $\thicksim$.
\begin{dfn}
Let $\mathbb E$ denote a te-set. We say that $\namestyle{sit}_i, \namestyle{sit}_j \in \mathbb E$ 
are {\em indistinguishable}, and we write $\namestyle{sit}_i \approx \namestyle{sit}_j$, if there 
exists a finite sequence $\namestyle{sit}_{k_1}, \ldots, \namestyle{sit}_{k_u} \in \mathbb E$ such 
that 
\begin{compactitem}
\item $\namestyle{sit}_{k_1} = \namestyle{sit}_i$;
\item $\namestyle{sit}_{k_u} = \namestyle{sit}_j$;
\item for every $g = 1, \ldots, u-1$, $\namestyle{sit}_{k_g} \thicksim \namestyle{sit}_{k_{g+1}}$. 
\theoend
\end{compactitem}
\end{dfn}
$\approx$ is an equivalence relation over $\mathbb E$, and we denote by $\mathbb E/\ordapprox$ the 
corresponding quotient set. We have the following definition:
\begin{dfn}\label{tdt:dfn:lowxpcost}
Let $\mathbb E$ be a te-set, with actions model $\mathbf A$. The {\em expected cost of $\mathbb 
E$}, denoted by $\overline{\mathcal{X}}_{\mathbb E, \mathbf A}$, is defined as:
\begin{equation}\label{tdt:eq:lowxpcost}
    \overline{\mathcal X}_{\mathbb E, \mathbf A} = \sum_{\eta \in \mathbb E/\ordapprox} 
    \chi(\namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit}) \mid \namestyle{sit} \in \eta \})) 
    \cdot P(\eta ; \mathbb E)
\end{equation}
\theoend
\end{dfn}
\begin{exm}\label{example:minxcost}
Let us consider the te-set $\mathbb{E}$ in Figure \ref{tdt:example:teset} and the action model $\mathbf{A}$ in Figure \ref{tdt:example:actmodel}. The only two indistinguishable fault situations in $\mathbb{E}$ are $\namestyle{sit}_2$ and $\namestyle{sit}_5$. Thus we have:
\begin{eqnarray*}
\overline{\mathcal X}_{\mathbb E,\mathbf A} & = & P(\namestyle{sit}_1)\chi(a) + P(\{\namestyle{sit}_2, \namestyle{sit}_5\})\chi(\{b,c\}) + P(\namestyle{sit}_3)\chi(b) + P(\namestyle{sit}_4)\chi(c) + \\
&&  +  P(\namestyle{sit}_6)\chi(d) + P(\namestyle{sit}_7)\chi(b) + P(\namestyle{sit}_8)\chi(c) =\\
& = & \frac{1}{8} \cdot 100 + \frac{1}{4} \cdot 70 + \frac{1}{8} \cdot 20 + \frac{1}{8} \cdot 50 + \frac{1}{8} \cdot 10 + \frac{1}{8} \cdot 20 + \frac{1}{8} \cdot 50 =\\
& = & 12.5 + 17.5 + 2.5 + 6.25 + 1.25 + 2.5 + 6.25  = 48.75
\end{eqnarray*}
Notice that the tree in Figure \ref{tdt:examplesfun:example} has the same cost as the te-set, thus its cost is the minimum possible, as we show below. Of course we may still be able to build another smaller tree with the same cost. \theoend
\end{exm}

Now we need to show that $\overline{\mathcal X}_{\mathbb E, \mathbf A}$ is actually the minimum 
possible expected cost for a temporal decision tree compatible with $\mathbb E$.
\begin{thr}\label{tdt:thr:lowxpcost}
Let $\mathbb E$ be a te-set with actions model $\mathbf A$. We have that:
\begin{romanenum}
\item There exists a decision tree $\overline{\mathbf{T}}$ compatible with $\mathbb E$ such that 
$\mathcal{X}_{\mathbb E, \mathbf A} (\overline{\mathbf T}) = \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$.
\item For every temporal decision tree $\mathbf T$ compatible with $\mathbb E$, $\overline{\mathcal 
X}_{\mathbb E, \mathbf A} \leq \mathcal{X}_{\mathbb E, \mathbf A}(\mathbf T)$. \theoend
\end{romanenum}
\end{thr}

Now we can state more precisely the problem of building a temporal decision tree:
\begin{quotation}
\noindent{\itshape Given a te-set $\mathbb E$ with actions model $\mathbf 
A$, we want to build a temporal decision tree $\mathbf T$ over $\mathbb E$, such that 
$\mathcal{X}_{\mathbb E, \mathbf A}(\mathbf T) = \overline{\mathcal X}_{\mathbb E, \mathbf A}$. 
Moreover, we want to keep the tree reasonably small by exploiting entropy.}
\end{quotation}
%%Notice that the tree $\overline{\mathbf T}$ defined in lemma \ref{tdt:lmm:lowxpcost:2} satisfies 
%%the first requirement, but it is not small at all. Actually it is the biggest temporal decision 
%%tree among those compatible with $\mathbb E$.

\section{The Algorithm}
In this section we describe in detail our proposal for building temporal decision trees from a given te-set and action model. We also discuss the complexity of the algorithm we introduce, and give an example of how the algorithm works.
\label{tdtalgo}
\subsection{Preconditions}
%%Before proposing a solution to \namestyle{Problem P1} we want to further analyze the generic 
%%algorithm in figure \ref{tdt:algo:temp:generic}. This will lead us smoothly to the solution, and 
%%will also help in formally proving that the solution is correct.
%%
%%In the generic algorithm, once we have chosen a pair $\langle \varname{sensor}, \varname{tlabel} 
%%\rangle$, we partition the original te-set \varname{Examples} according to the value measured by 
%%\varname{sensor} at time \varname{tlabel} in the different fault situations (line 
%%\ref{tdt:genalgo:temp:partition}). Thus we obtain a sequence of te-sets, stored one at a time in 
%%variable \varname{SubExamples} and passed on to recursive calls which build the different 
%%subtrees. However function \funname{BuildTemporalTree} does not exploit all information in the 
%%te-set, but only the observations in its input variable \varname{Obs}.
%%
%%Since after the choice of a pair some observations are discarded (line 
%%\ref{tdt:genalgo:temp:obsupd}), we actually do not pass on to recursive calls the members of a 
%%partition of the original te-set, but smaller te-sets, obtained from the partition members by 
%%removing some observations (the algorithm does not physically remove them, but it rather deletes 
%%them from the list of usable observations in \varname{Obs}; however the effect is the same). 
%%
%%What we want to show here is that, if all the te-sets generated in the \bfor loop at line 
%%\ref{tdt:genalgo:temp:mainloop} have always the same expected cost as they would have without 
%%removing observations, then the algorithm builds a tree with the lowest possible expected cost. 
%%More formally:
%%\begin{prp}
%%\end{prp}
Our goal is now to define an implementation of function \funname{ChooseObs} such that, once 
plugged into function \funname{BuildTemporalTree}, yields a solution to the problem of building temporal decision trees as stated in section \ref{tdt:subsect:problem}. 
First however we shall analyze some properties of \funname{BuildTemporalTree} as defined in Figure 
\ref{tdt:algo:temp:generic}: this will lead us smoothly to the solution and will help us prove 
formally its correctness. In order to accomplish this task we need to introduce some notation that 
allows us to speak about algorithm properties.

Let $\mathbb E$ be a te-set with fault situations $\{\namestyle{sit}_1, \ldots, \namestyle{sit}_n 
\}$, sensors $\{ s_1, \ldots, s_m \}$, time labels $\{t_1, \ldots, t_{\namestyle{last}} \}$ and 
action model $\mathbf A$. We aim at computing our tree $\mathbf T$ by 
executing:
\begin{equation}\label{tdt:eq:p1:mainexec}
\mathbf T \leftarrow \funname{BuildTemporalTree}(\{\namestyle{sit}_1, \ldots, \namestyle{sit}_n 
\}, \{s_1, \ldots, s_m\} \times \{t_1, \ldots, t_{\namestyle{last}} \}, \mathbf A)
\end{equation}
Each execution of \funname{BuildTemporalTree} comprises several recursive calls to the same 
function; given two recursive calls $c, c'$ we shall write $c \sqsubset c'$ when $c$ occurs 
immediately inside $c'$. Moreover we shall denote by $c_0$ the {\em initial} call. Finally, we shall call {\em terminal} a recursive call which does not have any further inner call.

For a given call $c$, we shall denote by $\doublel \varname{Example} \doubler_c$, $\doublel 
\varname{Obs} \doubler_c$, $\doublel \varname{ActModel} \doubler_c$ the actual values of the 
formal parameters in $c$. With a slight abuse of notation, we shall also write $\doublel 
\varname{var} \doubler_c$ to denote the value of those variables \varname{var} in $c$ that, once 
set, never change their value (\varname{deadline}, \varname{UsefulObs}, \varname{ValidObs}, \varname{sensor}, \varname{tlabel}, \varname{Obs\_Update}). 
Finally, we shall denote by $\doublel \varname{T} \doubler_c$ the tree returned by call $c$.

%%Let us test this notation by proving a simple property:
%%\begin{prp}
%%Any execution of \funname{BuildTemporalTree} terminates.
%%\end{prp}
%%\begin{proof}
%%The only way in which \funname{BuildTemporalTree} could not terminate is because of an infinite 
%%sequence of nested recursive calls $c_0 \sqsupset c_1 \sqsupset \ldots \sqsupset c_n \sqsupset 
%%\ldots$. However we can notice that if $c \sqsubset c'$ then 
%%$$\doublel \varname{UsefulObs} \doubler_c \subset \doublel \varname{Obs} \doubler_c =  \doublel \varname{Obs\_Update} \doubler_{c'} \subseteq \doublel \varname{UsefulObs} \doubler_{c'} $$
%%The reason why $\doublel \varname{UsefulObs} \doubler_c \subset \doublel \varname{Obs} \doubler_c$ is that there is always at least one observation which is not useful on $\doublel \varname{Examples} \doubler_c$, that is the observation that has been used in $c'$.
%%Since a call $c$ with $\doublel \varname{UsefulObs} \doubler_c = \varnothing$ does not produce any nested call, assuming an infinite sequence of nested calls means having an infinite sequence of sets 
%%$\doublel \varname{UsefulObs} \doubler_{c_0} \supset \doublel \varname{UsefulObs} \doubler_{c_1} \supset \ldots \supset \doublel \varname{UsefulObs} \doubler_{c_n} \supset \ldots$. Since $\doublel 
%%\varname{UsefulObs} \doubler_{c_0} $ is finite this is impossible.
%%\end{proof}

Each recursive call $c$ works on a different te-set, which is defined by $\doublel 
\varname{Examples} \doubler_c$ and $\doublel \varname{Obs} \doubler_c$. The actions model however 
is always the same, since for $c \sqsubset c'$ we have $\doublel \varname{ActModel} \doubler_c = 
\doublel \varname{ActModel} \doubler_{c'}$. We shall denote by $\mathbb{E}_c$ the te-set used in 
call $c$, which is determined by its input parameters. 

The following proposition is critical for proving the correctness of our approach. It states that we can obtain a tree with minimum expected cost if and only if we guarantee that there is no increase in the expected cost of the te-set when passing from the set of observations \varname{Obs} to the set \varname{Obs\_Update}:
\begin{prp}\label{tdt:prp:fundprop}
Let us consider an execution of \funname{BuildTemporalTree} starting with a main call $c_0$. The 
initial te-set, which we want to build a tree over, is $\mathbb E = \mathbb{E}_{c_0}$ with 
$\mathbf A = \doublel \varname{ActModel} \doubler_{c_0}$. For any recursive call $c$, let us 
denote by $\mathbb{E}_c^*$ the te-set determined by $\doublel \varname{Examples} \doubler_c$ and 
$\doublel \varname{Obs\_Update} \doubler_{c}$. Then: 
\begin{myenum} 
\item $\mathcal{X}_{\mathbb E, \mathbf A} (\actval{T}{c_0}) \geq \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$
\item $\mathcal{X}_{\mathbb E, \mathbf A} (\actval{T}{c_0}) = \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$ if and only if for every non terminal\footnote{We exclude terminal calls because 
they do not even compute \varname{Obs\_Update}.} recursive call $c$ generated by $c_0$ it holds 
that $\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} = \overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A}$
\end{myenum}
\end{prp}

\subsection{Implementing \textsc{ChooseObs}}
Proposition \ref{tdt:prp:fundprop} suggests that we need to provide an implementation for \funname{ChooseObs} such that at each recursive call $c$, 
$\overline{\mathcal X}_{\mathbb{E}_{c}, \mathbf A} = \overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A}$. Let us examine in more detail the relations between $\actval{Obs}{c}$ and 
$\actval{Obs\_Update}{c}$. 

As a first step, $\actval{UsefulObs}{c}$ is obtained by removing from $\actval{Obs}{c}$ those 
observations that do not help in discriminating fault situations. This has no effect on the 
expected cost of the te-set, since it does not affect the relation of indistinguishability. 

Then $\actval{Obs\_Update}{c}$ is obtained from $\actval{UsefulObs}{c}$ by removing those 
observations whose time label precedes the chosen one. The expected cost of the resulting te-set 
thus depends on the time label selected by function \funname{ChooseObs}. We have the following 
properties:
\begin{prp}\label{tdt:prp:safe:1}
Let $c, d$ denote two independent calls to \funname{BuildTemporalTree} with the same input 
arguments but with different implementations of \funname{ChooseObs}. If $\actval{tlabel}{c} \leq 
\actval{tlabel}{d}$ then $\overline{\mathcal X}_{\mathbb{E}_c^*,\mathbf A} \leq \overline{\mathcal 
X}_{\mathbb{E}_d^*, \mathbf A}$. 
\end{prp}

\begin{prp}\label{tdt:prp:safe:2}
Let $c$ be  a call to \funname{BuildTemporalTree}. If $\actval{tlabel}{c} = t_{\namestyle{min}_c} 
= \min\{t \mid \langle t,s \rangle \in \actval{ValidObs}{c} \}$ then $\overline{\mathcal 
X}_{\mathbb{E}_c^*,\mathbf A} \leq \overline{\mathcal X}_{\mathbb{E}_c, \mathbf A}$. 
\end{prp}

Now we define the notion of a {\em safe} time label: 
\begin{dfn}\label{tdt:dfn:safetime}
Let $c$ denote a call to \funname{BuildTemporalTree}. A time label $t$ is said to be {\em safe 
with respect to $c$} if $\actval{tlabel}{c} = t$ implies $\overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A} = \overline{\mathcal X}_{\mathbb{E}_c, \mathbf A}$.
\end{dfn}
An immediate consequence of propositions \ref{tdt:prp:safe:1} and \ref{tdt:prp:safe:2} is the 
following:
\begin{prp}\label{prp:3}
For any call $c$ to \funname{BuildTemporalTree} there exist a time label $t_{\namestyle{max}_c}$ 
such that the safe time labels are all and only those $t$ with $t_{\namestyle{min}_c} \leq t \leq 
t_{\namestyle{max}_c}$, where $t_{\namestyle{min}_c}$ is as in proposition \ref{tdt:prp:safe:2}.
\end{prp}


Figure \ref{tdt:algo:chooseobs} describes \funname{ID3ChooseSafeObs}, 
the implementation of \funname{Choose\-Obs} we propose. It exploits the properties we have proved in 
this and the previous section in order to achieve the desired task in an efficient way. Let us 
examine it in more detail.

\begin{figure}[t]
\begin{center}
\framebox{
\begin{minipage}{14cm}
\begin{myalgo}
    \alinenum \bfun \funname{ID3ChooseSafeObs} (set \varname{Obs}, te-set \varname{Examples}, 
            action model \varname{ActModel})
    \alinenum \brets an observation $\varname{o} = \langle \varname{sensor}, \varname{tlabel} \rangle$
    \alinenum\bbegin\blockstart
        \alinenum $\varname{SafeObs} \leftarrow \funname{FindSafeObs}(\varname{Obs}, 
        \varname{Examples}, \varname{ActModel})$; \label{tdt:algo:chooseobs:findsafe}
        \alinenum $\varname{o} \leftarrow \funname{ID3ChooseTest}(\varname{SafeObs}, 
            \varname{Examples})$; \label{tdt:algo:chooseobs:minent}
        \alinenum \bret \varname{o};
    \blockend\alinenum\bend.
    \alinenum \bfun \funname{FindSafeObs} (set \varname{Obs}, te-set \varname{Examples}, 
            action model \varname{ActModel})
    \alinenum \brets a set of observations $\varname{SafeObs}$
    \alinenum\bbegin
    \blockstart
        \alinenum $\varname{cost} \leftarrow \sum_{\varname{sit} \in \varname{Examples}} 
            \namestyle{Act}(\varname{sit})$;
        \alinenum $\varname{t\_up} \leftarrow \namestyle{Dl}(\varname{Examples})$;
        $\quad\varname{t\_low} \leftarrow \min\{\varname{t} \mid \langle \varname{s},
            \varname{t} \rangle \in \varname{Obs} \}$; \label{tdt:algo:findsafe:range}
        \alinenum $\varname{t\_max} \leftarrow \varname{t\_up}$;
            $\quad\varname{part} \leftarrow \{ \langle \varname{Examples}, \varname{t\_up} \rangle
            \}$;
        \alinenum \bfor every time label \varname{tx} starting from \varname{t\_up} down to 
            \varname{t\_low} \bdo \bbegin
        \blockstart
            \alinenum $\varname{part} \leftarrow \funname{QuotientSet}(\varname{part}, 
            \varname{Obs}, \varname{tx})$;
            \alinenum $\varname{newcost} \leftarrow \funname{ExpectedCost}(\varname{part})$;
            \alinenum \bif $\varname{newcost} < \varname{cost}$ \bthen \bbegin
            \blockstart
                \alinenum $\varname{cost} \leftarrow \varname{newcost}$;
                $\quad \varname{t\_max} \leftarrow \varname{tx}$;
            \blockend
            \alinenum\bend;
        \blockend
        \alinenum\bend;
        \alinenum $\varname{SafeObs} \leftarrow \{ \langle \varname{s}, \varname{t} \rangle \mid
            \varname{t} \leq \varname{t\_max}\}$; \label{tdt:algo:findsafe:set}
        \alinenum\bret \varname{SafeObs}; 
    \blockend
    \alinenum \bend .
    \alinenum \bfun \funname{QuotientSet} (partition \varname{Initial}, set \varname{Obs}, 
            time label \varname{tlabel})
    \alinenum \brets a refined partition $\varname{Final}$
    \alinenum\bbegin\blockstart
        \alinenum$\varname{part} \leftarrow \varname{Initial}$;
        \alinenum \bfor all $\langle \varname{s},\varname{t} \rangle$ with $\varname{t} = 
            \varname{tlabel}$ \bdo \bbegin \label{tdt:algo:quotient:startcurr}
        \blockstart
            \alinenum $\varname{part} \leftarrow \funname{ExtPartition}(\varname{part}, \langle 
                    \varname{s}, \varname{t} \rangle)$;
            \alinenum $\varname{ObsCurr} \leftarrow \varname{ObsCurr} \cup \{ \langle 
                    \varname{s}, \varname{t} \rangle\}$;
        \blockend
        \alinenum\bend; \label{tdt:algo:quotient:endcurr}
        \alinenum $\varname{Final} \leftarrow \varnothing$;
        \alinenum \bwhile $\varname{part} \neq \varnothing$ \bdo 
        \blockstart
            \alinenum $\varname{tmp\_part} \leftarrow \varnothing$;
            \alinenum \bfor \beach $\langle \varname{block}, \varname{ty} \rangle \in 
                    \varname{part}$ \bdo \bbegin
            \blockstart
                \alinenum $\varname{newdl} \leftarrow \namestyle{Dl}(\varname{block})$; 
                    \label{tdt:algo:quotient:startdl}
                \alinenum $\varname{single} \leftarrow \{ \langle \varname{block}, 
                            \varname{ty} \rangle \}$;
                \alinenum \bif $\varname{newdl} > \varname{ty}$ \bthen \bbegin 
                    \label{tdt:algo:quotient:enddl}
                \blockstart
                    \alinenum \bfor\beach $\langle \varname{s}, \varname{t} \rangle$ with
                                $\varname{ty} < \varname{t} \leq \varname{newdl}$ \bdo
                                \label{tdt:algo:quotient:startstore}
                    \blockstart
                        \alinenum$\varname{single} \leftarrow \funname{ExtPartition}
                                (\varname{single}, \langle \varname{s}, \varname{t} \rangle)$;
                    \blockend
                    \alinenum$\varname{tmp\_part} \leftarrow \varname{tmp\_part} \cup 
                                \varname{single}$; \label{tdt:algo:quotient:endstore}
                \blockend
                \alinenum\bend\ 
                \belse $\varname{Final} \leftarrow \varname{Final} \cup \varname{start}$;
                    \label{tdt:algo:quotient:final}
            \blockend
            \alinenum\bend;
            \alinenum $\varname{part} \leftarrow \varname{tmp\_part}$;
        \blockend
        \alinenum\bend;
        \alinenum\bret \varname{Final}; 
    \blockend
    \alinenum \bend .
\end{myalgo}
\end{minipage}
}
\end{center}
\caption{\funname{ID3ChooseSafeObs} is an implementation of \funname{ChooseObs} yielding a tree 
with minimum expected cost}\label{tdt:algo:chooseobs}
\end{figure}

\funname{ID3ChooseSafeObs} (Figure \ref{tdt:algo:chooseobs}) computes the set of safe observations 
(line \ref{tdt:algo:chooseobs:findsafe}) and then chooses among them one with minimum entropy 
(line \ref{tdt:algo:chooseobs:minent}). For what we have proved up to now, such an implementation 
yields a temporal decision tree with minimum expected cost, and at the same time exploits entropy 
in order to keep the tree small.

Let us now see how \funname{FindSafeObs} (also in Figure \ref{tdt:algo:chooseobs}) computes the 
set of safe observations. Proposition \ref{tdt:prp:safe:2} shows that the notion of safeness is 
tied to time labels rather than to individual observations. First of all \funname{FindSafeObs} 
determines the range of valid time labels for the current set of examples (line 
\ref{tdt:algo:findsafe:range}); the lower bound $t_{\namestyle{low}}$ is the lowest time label in 
\varname{Obs}, and is stored in variable \varname{t\_low}, while the upper bound 
$t_{\namestyle{up}}$ is given by the global deadline for \varname{Examples}, and is stored in 
variable \varname{t\_up}.

Then the idea is to find the maximum safe label $t_{\namestyle{max}}$ (variable \varname{t\_max}) 
which allows us to easily build the set of safe observations (line \ref{tdt:algo:findsafe:set}). 

In order to accomplish this task the following steps have to be performed:
\begin{compactitem}
    \item Given the initial te-set $\mathbb E$, defined by \varname{Examples}, \varname{Obs} and 
    \varname{ActModel}, compute $\overline{\mathcal X}_{\mathbb E, \mathbf A}$.
    \item For each time label $t$ in the range delimited by $t_{\namestyle{low}}$ and 
    $t_{\namestyle{up}}$, consider the te-set $\mathbb{E}_t$ defined by \varname{Examples} and by 
    those observations with time label equal or greater than $t$. Then compute $\overline{\mathcal 
    X}_{\mathbb{E}_t, \mathbf A}$.
    \item As soon as we find a time label $t$ with $\overline{\mathcal X}_{\mathbb{E}_t, \mathbf A}
    > \overline{\mathcal X}_{\mathbb{E}, \mathbf A}$, we know that $t_{\namestyle{max}}$ is the 
    time label immediately preceding $t$.
\end{compactitem}
Here the most critical operation (in terms of efficiency) is that of computing the expected cost 
of each $\mathbb{E}_t$, because this involves finding the quotient set $\mathbb{E}_t/\ordapprox$. 
In fact, in order to obtain the quotient set, we need to repeatedly partition the te-set with 
respect to {\em all} observations available for it.

\funname{QuotientSet} function (Figure \ref{tdt:algo:chooseobs}) performs precisely this task. It 
takes in input the current time label \varname{tlabel}, an initial partition (possibly made of a 
single block with the entire te-set) and the set of all observations, from which it will select 
valid ones.

First of all it partitions the input te-set with respect to observations with the current time 
label (lines \ref{tdt:algo:quotient:startcurr}--\ref{tdt:algo:quotient:endcurr}). Then it executes 
iteratively the following operations:
\begin{compactitem}
\item For each partition block it checks whether the deadline has moved further in time (lines 
\ref{tdt:algo:quotient:startdl}--\ref{tdt:algo:quotient:enddl}).
\item If so, it partitions again the block and stores the resulting sub-blocks for further 
examination (lines \ref{tdt:algo:quotient:startstore}--\ref{tdt:algo:quotient:endstore}).
\item If not, the block is part of the \varname{Final} partition that will be returned (line 
\ref{tdt:algo:quotient:final}).
\end{compactitem}
In order to simplify the task, we introduce as a data type the {\em extended partition}, where 
each partition block is stored together with the highest time label used in building it. In this 
way we can easily check if the deadline for the block allows us to exploit more observations or 
not. Using extended partitions instead of standard ones we need to define a new function, 
\funname{ExtPartition}, which works in the same way as the \funname{Partition} function used in 
Figure \ref{tdt:id3alg}, but also records with each block the highest time label used for it.

Notice that \funname{QuotientSet} needs the whole set of observations (and not only valid ones) to properly compute the result; therefore when \funname{BuildTemporalTree} calls \funname{ID3ChooseSafeObs} it must pass as first argument \varname{UsefulObs} instead of \funname{ValidObs}.

\funname{FindSafeObs} exploits \funname{QuotientSet} to find all quotient sets for all 
$\mathbb{E}_t$, but does so using an efficient approach which we call {\em backward strategy}.

First of all, we can notice that the order in which observations are considered does not matter 
while building a quotient set. Moreover, if $t < t'$, $\mathbb{E}_t/\ordapprox$ is a refinement of 
$\mathbb{E}_{t'}/\ordapprox$; in other words we can obtain it from $\mathbb{E}_{t'}/\ordapprox$ by 
simply refining the partition with additional observations. 

Thus, {\em we can compute all quotient sets at the same time as we compute 
$\mathbb{E}/\ordapprox$}.

\funname{FindSafeObs} does exactly so: it computes all quotient sets and their expected cost 
starting from the last time label $t_{\namestyle{up}}$. Each quotient set is not built from 
scratch, but as a refinement of the previous one. This is the reason why \funname{QuotientSet} 
(and \funname{ExtPartition} as well) takes as first argument not a single set, but a partition. In 
this way, all quotient sets are computed with the same operations\footnote{There is a slight 
overhead due to the need to find which observations should be used at each step.} needed to build 
$\mathbb{E}/\ordapprox$. The next section analyzes in further detail complexity issues.

\subsection{Complexity}
In this section we aim at showing that the additional computations needed in building temporal decision trees  do not lead to a higher asymptotical complexity than that we would get by using the standard \idthree\ algorithm on the same set of examples (we discussed in section \ref{sect:challenge} the circumstances that could make such an approach feasible).

Essentially the difference between the two cases lies in the presence of \funname{Find\-Safe\-Obs} function. Wherever \funname{Build\-Tree} calls \funname{ID3ChooseTest}, \funname{Build\-Temporal\-Tree} calls \funname{ID3Choose\-Safe\-Obs}, which in turn calls both \funname{Find\-Safe\-Obs} and \funname{ID3Choose\-Test}. 


Let us compare \funname{FindSafeObs} and \funname{ID3ChooseTest}, which are similar in many ways. The former repeatedly partitions the input te-set with respect to every available observation; then it computes entropy for each partition built in such a way. \funname{FindSafeObs} builds just one partition by exploiting {\em all} available observations; in other words instead of using each observation to partition the initial te-set, it exploits it in order to refine an existing partition of the same te-set. Moreover, at each time label it computes the expected cost of the partition built so far. Essentially, if we denote by $N_S$ the number of sensors and with $N_T$ the number of time labels in the initial partition, we have roughly the following comparison:
\begin{compactitem}
\item $N_S \times N_T$ (number of observations) entropy computations for \funname{ID3ChooseTest} vs. $N_T$ expected cost computations for \funname{FindSafeObs}.
\item $N_S \times N_T$ partitions of the initial te-set for \funname{ID3ChooseTest} vs. $N_S \times N_T$ refinements of existing partitions of the initial te-set for \funname{FindSafeObs}.
\end{compactitem}
Entropy and expected cost can be computed with roughly the same effort: both require retrieving some information for each element of each partition block, and to combine this information in some quite straightforward way. The complexity of this task depends only on the overall number of elements, and not on how they are distributed between different block of the partition. So even if expected cost is computed most of the times on finer partitions than entropy, the only thing that matters is that both are partitions of the same set, thus involving the same elements.

Now let us examine the problem of creating a partition. This involves retrieving a value for each element of each block of the initial partition (which again depends only on the number of elements, and not on the number of blocks of the initial partition) and to properly assign the element to a new partition block depending on the original block and on the new value. The main difference in this case between starting with the whole te-set (creation) or with an initial partition (refinement), is the size of the new blocks that are being created, which are smaller in the second case. Dependent on how we implement the partition data type, this may make no difference, or may take less time for the refinement case. However, it never happens that refinement (corresponding to \funname{Find\-Safe\-Obs} function) requires more time than the creation (corresponding to \funname{ID3Choose\-Test} function) of a partition. 

Therefore we can claim that \funname{Find\-Safe\-Obs} function has the same asymptotic complexity as function \funname{ID3Choose\-Test}. Thus also \funname{ID3Choose\-Safe\-Obs} has the same asymptotic complexity as \funname{ID3Choose\-Test}, and we can conclude that \funname{Build\-Tree} has the same asymptotic complexity as \funname{Build\-Temporal\-Tree}.

\subsection{An Example}
In this section we shall show how our algorithm operates on the te-set in Figure \ref{tdt:example:teset} with respect to the action model in Figure \ref{tdt:example:actmodel}.
 
Let us summarize the information the algorithm receives. Eight fault situations are involved; moreover we can exploit three sensors, each of which can show five different qualitative values: \namestyle{h} - high, \namestyle{n} - normal, \namestyle{l} - low, \namestyle{v} - very low, \namestyle{z} - zero. Time labels correspond to natural numbers ranging from $0$ to $7$, and we assume they correspond to times measured by an internal clock which is started at the time of fault detection.  There are four basic recovery actions $a, b, c, d$, such that $d \prec b \prec a$ and $d \prec c \prec a$. The set of compound recovery actions is thus $\mathbb A = \{ \{a\} , \{b\}, \{c\} , \{b,c\} , \{d\} \}$; the ordering relation is pictured in \ref{tdt:example:actmodel}, together with action costs. 

\funname{BuildTemporalTree} is first called on the whole te-set. None of the two terminating conditions is met (notice however that there are two observations that are not useful, since they do not discriminate: $\langle s_3, 0 \rangle$ and $\langle s_3, 1 \rangle$). Then the main function calls \funname{ID3ChooseSafeObs} and consequently \funname{FindSafeObs}. Since the global deadline is $2$ we must check time labels $0, 1$ and $2$, starting from the last one. 

Exploiting only observations with time label $2$ we obtain the following partition:
$$ \{ \{\namestyle{sit}_1, \namestyle{sit}_6\}, \{ \namestyle{sit}_2, \namestyle{sit}_5, \namestyle{sit}_7, \namestyle{sit}_8 \}, \{\namestyle{sit}_3\}, \{\namestyle{sit}_4\}\}$$
However in order to find the expected cost we still have to check if for some partition block the deadline has changed; this happens for $\{\namestyle{sit}_1, \namestyle{sit}_6\}$ as well as for $\{ \namestyle{sit}_3 \}$ and $\{\namestyle{sit}_4\}$. For the last two blocks it does not change anything - they already contain only one element. As to the first block, the deadline is now $5$ and thus it is possible to further split the partition. Therefore we obtain that the partition for time label $2$ is:

$$ \mathbb{P}_{t=2} = \{ \{\namestyle{sit}_1\}, \{\namestyle{sit}_6\}, \{ \namestyle{sit}_2, \namestyle{sit}_5, \namestyle{sit}_7, \namestyle{sit}_8 \}, \{\namestyle{sit}_3\}, \{\namestyle{sit}_4\}\}$$

After finding the partition, the algorithm computes the expected cost, which turns out to be:
\begin{eqnarray*}
\mathbb{X}_{\mathbb{E},t=2} & = & \chi(\namestyle{Act}(\namestyle{sit}_1)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\namestyle{sit}_6)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\{ \namestyle{sit}_2, \namestyle{sit}_5, \namestyle{sit}_7, \namestyle{sit}_8 \})) \cdot \frac{1}{2} \\
& + &\chi(\namestyle{Act}(\namestyle{sit}_3)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\namestyle{sit}_4)) \cdot \frac{1}{8}\\
& = & 100 \cdot \frac{1}{8} + 10 \cdot \frac{1}{8} + 70 \cdot \frac{1}{2} + 20 \cdot \frac{1}{8} + 50 \cdot \frac{1}{8} \\
& = & 57.5
\end{eqnarray*}

Then the algorithm moves to time label $1$; starting from $\mathbb{P}_{t=2}$ it adds observations with time label $1$, obtaining a new partition:
$$ \mathbb{P}_{t=1} = \{ \{\namestyle{sit}_1\}, \{\namestyle{sit}_6\}, \{ \namestyle{sit}_2, \namestyle{sit}_5\}, \{\namestyle{sit}_7\}, \{\namestyle{sit}_8 \}, \{\namestyle{sit}_3\}, \{\namestyle{sit}_4\}\}$$
Deadlines move for $\{ \namestyle{sit}_7 \}$ and $\{ \namestyle{sit}_8\}$, but since these are singletons the new observations cannot further split the partition.
The expected cost is now:
\begin{eqnarray*}
\mathbb{X}_{\mathbb{E},t=1} & = & \chi(\namestyle{Act}(\namestyle{sit}_1)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\namestyle{sit}_6)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\{ \namestyle{sit}_2, \namestyle{sit}_5 \})) \cdot \frac{1}{4} 
+ \chi(\namestyle{Act}(\namestyle{sit}_7)) \cdot \frac{1}{8}  \\
& + & \chi(\namestyle{Act}(\namestyle{sit}_8)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\namestyle{sit}_3)) \cdot \frac{1}{8} 
+ \chi(\namestyle{Act}(\namestyle{sit}_4)) \cdot \frac{1}{8}\\
& = & 100 \cdot \frac{1}{8} + 10 \cdot \frac{1}{8} + 70 \cdot \frac{1}{4}  + 20 \cdot \frac{1}{8} + + 50 \cdot \frac{1}{8} + 20 \cdot \frac{1}{8} + 50 \cdot \frac{1}{8} \\
& = & 48.75
\end{eqnarray*}
Since $\mathbb{X}_{\mathbb{E},t=1} < \mathbb{X}_{\mathbb{E},t=2}$ we can conclude that observations with time label $2$ are not safe. We now move to time label $0$, and we immediately realize that the new observations do not change the partition. Thus $\mathbb{X}_{\mathbb{E},t=0} = \mathbb{X}_{\mathbb{E},t=1}$, and safe observations are those with time label equal either to $0$ or to $1$.

The algorithm now calls function \funname{ID3ChooseTest} which selects the observation with minimum entropy. Figure \ref{tdt:example:entro:1} shows the entropies of the different observations at this stage, from which we deduce that the best choice is $\langle s_2, 1 \rangle$.

\begin{figure}[h]
\begin{center}{\footnotesize\setlength{\tabcolsep}{0.8ex}
\begin{tabular}{|c|p{2.5cm}||c|p{2.5cm}|} \hline
\multicolumn{4}{|c|}{\bfseries Entropies for $\{\namestyle{sit}_1, \namestyle{sit}_2, \namestyle{sit}_3, \namestyle{sit}_4, \namestyle{sit}_5, \namestyle{sit}_6, \namestyle{sit}_7, \namestyle{sit}_8\}$}\\ \hline\hline
$\langle s_1,0 \rangle$ & 1.5 & $\langle s_1,1 \rangle $  &  1.5 \\ \hline
$\langle s_2,0 \rangle$ & 1.451 & $\langle s_2,1 \rangle $ & 0.844 \\ \hline
\end{tabular}
}
\end{center}
\caption{Entropies for safe observations at the initial call}\label{tdt:example:entro:1}
\end{figure}

Figure \ref{tdt:example:tree}.(a) shows the tree at this point; function \funname{BuildTemporalTree} recursively invokes itself four times, yielding: 
\begin{compactitem}
\item a call $c_1$ on $\mathbb{E}_{\namestyle{v}} = \{ \namestyle{sit}_1 , \namestyle{sit}_6 \}$;
\item a call $c_2$ on $\mathbb{E}_{\namestyle{n}} = \{ \namestyle{sit}_2, \namestyle{sit}_5 \}$;
\item a call $c_3$ on $\mathbb{E}_{\namestyle{l}} = \{ \namestyle{sit}_3, \namestyle{sit}_4, \namestyle{sit}_7\}$;
\item a call $c_4$ on $\mathbb{E}_{\namestyle{h}} = \{ \namestyle{sit}_8\}$.
\end{compactitem}
Let us focus on call $c_1$: again, none of the terminating conditions is met, therefore the algorithm invokes \funname{ID3ChooseSafeObs} and thus \funname{FindSafeObs}. Notice however that on this subset only a few observations are in \varname{UsefulObs}: $\langle s_1, 3 \rangle$, $\langle s_2, 3 \rangle$, $\langle s_2, 4 \rangle$, $\langle s_2, 5 \rangle$ and $\langle s_3, 5 \rangle$. The global deadline is $5$. 

First we find the partition (and the expected cost) for time label $5$:
\begin{eqnarray*}
	\mathbb{P}_{t=5} & = & \{ \{ \namestyle{sit}_1\}, \{\namestyle{sit}_6 \}\}\\
	\mathbb{X}_{\mathbb{E}_{\namestyle{v}}, t=5} & = & \chi(\namestyle{Act}(\namestyle{sit}_1)) \cdot \frac{1}{2} + 
	\chi(\namestyle{Act}(\namestyle{sit}_6)) \cdot \frac{1}{2} = 100 \cdot \frac{1}{2}+ 10 \cdot \frac{1}{2} = 55
\end{eqnarray*}
No additional observations can split further this partition and lower the cost; therefore we find that all valid observations are also safe. It is moreover obvious that all these observations have the same entropy, which is $0$. Therefore the algorithm can non-deterministically select one of them; a reasonable criterion would be to select any of the earliest ones, for example $\langle s_1, 3 \rangle$. 

Since the initial te-set for call $c_1$ is now split in two, there are two more recursive calls. However we can notice that if \funname{BuildTemporalTree} is called on a te-set with a single element, the first terminating condition is trivially met (all the fault situations have the same recovery action). The function simply returns a tree leaf with the name of the proper recovery action. Figure \ref{tdt:example:tree}.(b) shows the tree after $c_1$ has been completed.

Now let us examine $c_2$: the algorithm eliminates non-discriminating observations, and finds out that the set of useful observations is empty. Thus it builds a leaf with recovery action $\{b,c\}$.
\begin{figure}[h]
\begin{center}{\footnotesize\setlength{\tabcolsep}{0.8ex}
\begin{tabular}{|c|c||c|c||c|c|} \hline
\multicolumn{6}{|c|}{\bfseries Entropies for $\{\namestyle{sit}_3, \namestyle{sit}_4, \namestyle{sit}_7\}$}\\ \hline\hline
$\langle s_1,1 \rangle$ & 0.667 & $\langle s_1,2 \rangle $  & 0.667  & $\langle s_1, 3 \rangle$ & 0.667 \\ \hline
$\langle s_2,2 \rangle$ & 0.667 & $\langle s_2,3 \rangle $ & 0.667 & $\langle s_2, 4 \rangle$ & 0.667 \\ \hline
$\langle s_2,5 \rangle$ & 0 & $\langle s_3,1 \rangle $ & 0 & $\langle s_3, 2 \rangle$ & 0 \\ \hline
$\langle s_3,3 \rangle$ & 0 & $\langle s_3,4 \rangle $ & 0 & & \\ \hline
\end{tabular}
}
\end{center}
\caption{Entropies for safe observations at call $c_3$}\label{tdt:example:entro:2}
\end{figure}
Let us pass to call $c_3$. In this case none of the terminating conditions is met: the algorithm must then look for safe observations. The global deadline is $5$, so we start examining time label $5$, and we find:
\begin{eqnarray*}
	\mathbb{P}_{t=5} & = & \{ \{ \namestyle{sit}_3\}, \{\namestyle{sit}_4 \}, \{\namestyle{sit}_7\}\}\\
	\mathbb{X}_{\mathbb{E}_{\namestyle{l}}, t=5} & = & \chi(\namestyle{Act}(\namestyle{sit}_3)) \cdot \frac{1}{3} + 
	\chi(\namestyle{Act}(\namestyle{sit}_4)) \cdot \frac{1}{3} 
	+ \chi(\namestyle{Act}(\namestyle{sit}_7)) \cdot \frac{1}{3} \\
	& = & 20 \cdot \frac{1}{3}+ 50 \cdot \frac{1}{3} + 20 \cdot \frac{1}{3} = 30
\end{eqnarray*}
Much as happened for $c_1$, no additional observation can further split the partition, so we can conclude that all valid observations are also safe. 
Figure \ref{tdt:example:entro:2} shows entropy for all valid observations; the earliest one with minimum entropy is $\langle s_3, 2\rangle$ and this the algorithm selects.
The two recursive sub-calls that are generated immediately terminate: $\{ \namestyle{sit}_4\}$ is a singleton, and in $\{ \namestyle{sit}_3, \namestyle{sit}_7 \}$ both fault situations correspond to the same recovery action.

The last recursive call, $c_4$, has in input a singleton and thus immediately terminates. The final decision tree $\mathbf T$ is pictured in Figure \ref{tdt:example:tree}.(c).
\begin{figure}[h]
\begin{center}
\footnotesize
\setlength{\unitlength}{1mm}
\begin{tabular}{c@{\hspace*{1cm}}c}
\includegraphics[scale=0.7, viewport= 2cm 9.5cm 10cm 15.5cm, clip=true]{Figures/tdt_example_tree_a.eps}
&
\includegraphics[scale=0.7, viewport= 3.3cm 9.5cm 13.5cm 15.5cm, clip=true]{Figures/tdt_example_tree_b.eps}
\\
\namestyle{(a)} & \namestyle{(b)} \\
\multicolumn{2}{c}{ 
\includegraphics[scale=0.7, viewport= 2.5cm 9.5cm 14cm 17cm, clip=true]{Figures/tdt_example_tree_c.eps}
}\\
\multicolumn{2}{c}{\namestyle{(c)}}
\end{tabular}
\end{center}
\caption{The output tree at different stages. \namestyle{(c)} shows the final tree.} \label{tdt:example:tree}
\end{figure}

Let us check if the expected cost of $\mathbf T$ is really equal to the expected cost for $\mathbb E$. Figure \ref{tdt:example:leafcost} shows for each tree leaf $l$ the corresponding set of fault situations $\namestyle{examples}(l)$, its probability $P(\namestyle{examples}(l); \mathbb E)$ and its cost $\chi(\mathcal L(l))$. Leaves are numbered from 1 to 6 going left to right in Figure \ref{tdt:example:tree}.(c). 

\begin{figure}[h]
\begin{center}{\footnotesize\setlength{\tabcolsep}{0.8mm}
\begin{tabular}{|c|l|c|c|} \hline
leaf & \namestyle{examples} & P & $\chi$ \\ \hline\hline
$l_1$ & $\namestyle{sit}_1$ & $1/8$ & $100$ \\ \hline
$l_2$ & $\namestyle{sit}_6$ & $1/8$ & $10$ \\ \hline
$l_3$ & $\namestyle{sit}_2$, $\namestyle{sit}_5$ & $1/4$ & $70$ \\ \hline
$l_4$ & $\namestyle{sit}_8$ & $1/8$ & $50$ \\ \hline
$l_5$ & $\namestyle{sit}_3$, $\namestyle{sit}_7$ & $1/4$ & $20$ \\ \hline
$l_6$ & $\namestyle{sit}_4$ & $1/8$ & $50$ \\ \hline
\end{tabular}}
\end{center}
\caption{Fault situations, probabilities and costs for the leaves of the tree in Figure \ref{tdt:example:tree}.(c)}\label{tdt:example:leafcost}
\end{figure}
Thus the expected cost of the tree is:
\begin{eqnarray*}
\mathbb{X}_{\mathbb{E},\mathbf{A}}(\mathbf T) & = & \sum_{i=1}^6 \chi(\mathcal L(l_i)) \cdot P(\namestyle{examples}(l);\mathbb E)\\
& = & \frac{1}{8} \cdot 100 + \frac{1}{8} \cdot 10 + \frac{1}{4} \cdot 70 + \frac{1}{8} \cdot 50 + \frac{1}{4} \cdot 20 + \frac{1}{8} \cdot 50 \\
& = & 48.75
\end{eqnarray*}

If we look back at example \ref{example:minxcost} we see that $\overline{\mathbb X}_{\mathbb E, \mathbf A} = 48.75$, thus $\mathbf{T}$ has the minimum possible expected cost. Moreover, we can compare $\mathbf{T}$ with the tree $\mathbf{T}_1$ of example \ref{example:examples}. Also $\mathbf{T}_1$ has the minimum possible expected cost, but $\mathbf{T}$ is more compact.

\section{Conclusions}
\label{conclusions}

In this paper we introduced a new notion
of diagnostic decision tree that takes into account temporal
information on the observations and temporal
constraints on the recovery actions to be performed.
In this way we can take advantage of the discriminatory power
that is available in the model of a dynamic system.
We presented an algorithm that generates temporal diagnostic decision
trees from a set of examples, discussing also how an
optimal tree can be generated.

The automatic compilation of decision trees seems to be a promising
approach for reconciling the advantages of model-based reasoning
and the constraints imposed by the on-board hardware and software
environment.
It is worth noting that this is not only true in the automotive
domain and indeed the idea of compiling diagnostic rules
from a model has been investigated also
in other approaches (see \citeR<e.g.,>{Darwiche:99,Dvorak:89}).
Darwiche \citeyear{Darwiche:99}, in particular, discusses how rules can be
generated
for those platforms where constrained resources do not
allow a direct use of a model-based diagnostic system.

What is new in our approach is the possibility of compiling 
also information concerning
the system temporal behaviour, obtaining in this way more
accurate decision procedures.

To the best of our knowledge, temporal decision trees are a new notion in the diagnostic literature. However, there are works in other fields that have some relation to ours, since they are aimed at learnig rules or associations that take into account time.

Geurts and Whenkel \citeyear{Geurts:98} propose a notion of temporal tree to be used for early prediction of faults. This topic is closely related to diagnosis, albeit different in some ways: the idea is that the device under examination has not failed yet, but by observing its behaviour it is possible to predict that a fault is about to occur. \citeauthor{Geurts:98} propose to learn the relation between observed behavioural patterns and consequent failures by inducing a {\em temporal tree}.

The notion of temporal tree introduced by \citeauthor{Geurts:98} is different than our temporal decision trees, reflecting the different purpose it has been introduced for. Rather than sensor readings, it consider a more general notion of test, and the tree does not specifies the time to wait before performing the tests, but rather the agent running the tree is supposed to wait until one of the tests associated to a tree node becomes true.

Also the notion of optimality is quite different: in the situation described by \citeauthor{Geurts:98} the size of the resulting tree is not a concern. The tree-building algorithms aims then at minimizing the time at which the final decision is taken. In our algorithm, size is the primary concern, while from the point of view of time it suffices that diagnosis is carried out within certain deadlines. From the point of view of time alone, the apporach by \citeauthor{Geurts:98} is probably more general than ours; the problem of considering the trade-off between diagnostic capability and time needed for diagnosis is one of the major extensions we are considering for future work on this topic (see below).

Finally, the algorithm proposed by \citeauthor{Geurts:98} works in a quite different way than ours: it first builds the tree greedily, using an evaluation function that weighs discriminability power agains time needed to reach a result, and selecting at each step the texts that optimizes such function. Then it prunes the tree in order to avoid overfitting. On the other hand, our approach aim at optimizing the tree from the point of view of cost, and at the same time tries to keep the tree small with the entropy heuristic. We think that, since optimization can be carried out at no additional cost\footnote{From the point of view of asymptotical complexity.} with respect to the minimization of entropy, our approach can obtain better results, at least in those cases where one can define a notion of deadline.

The process of learning association rules involving time has also been studied in other areas, such as machine learning (see for example \citeR{Bischof:01}, where the authors propose a technique to learn movements) and data mining. While the specific diagnostic tailoring of our approach makes it difficult to compare it with more generic learning algorithms, the connections with data mining may be stronger.
Our proposal in fact aims essentially at extracting from series of observations those patterns in time that allow to correctly diagnose a fault: this process can be regarded as a form of temporal classification.
A preliminary investigation of papers in this area (see \citeR{antunes:01} for an overview) seems to suggest that, whereas the analysis of temporal sequences of data has received much interest in the last years, not much work has been done in the direction of data classification, where temporal decision trees could be exploited.

This suggests an interesting development for our work, in particular as concerns its applicability in other areas. However, we believe that the algorithm we presented needs to be extended in order to be exploited in other contexts.
In particular we are investigating the following extensions:
\begin{compactitem}
\item Deadlines could be turned from {\em hard} to {\em soft}. Soft deadlines do not have to be met, but rather define a cost associated to not meeting them. Thus not meeting a deadline becomes an option that can be taken into account when it is less expensive than performing a recovery action when the diagnosis is not complete. One could even define a cost that increases as the time passes from the expiration of the deadline. Such an extension would allow to model also the trade-off between discriminability power and time needed by the decision process, which we believe is the key to making our work applicable in other areas.
\item Actions could be assumed to have a different cost depending on the fault situation; for example the action associated to a fault could become dangerous and thus extremely expensive if performed in presence of another fault.
\end{compactitem}

On the long term, future work on this topic will be aimed at widening its areas of applicability, and investigating in deeper details its connections with other fields, such as fault prevention and data mining.

\section{Acknowledgements}
This work was partially supported by the EU under the
grant GRD-1999-0058, project IDD (Integrated Diagnosis and Design), whose
partners are: Centro Ricerche
Fiat, Daimler-Chrysler, Magneti Marelli, OCC'M, PSA, Renault, Technische
Universit\"at M\"unchen,
Universit\'e Paris XIII, Universit\`a di Torino.


\appendix
\section{Proofs}
This section contains the proofs of all propositions, lemmas and theorems in the paper.

\sepproof{Proposition \ref{prp:1}.}
{\em Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T\rangle$ be a temporal decision tree compatible with a te-set $\mathbb E$. Let $l_1, \ldots, l_f \in N$ denote the leaves of $T$. Then 
$\namestyle{examples}(l_1), \ldots, \namestyle{examples}(l_f)$ is a partition of $\mathbb E$.}

\begin{proof} Follows immediately by the definition of \namestyle{examples} (\ref{tdt:dfn:examples}), by noticing that if $n_1, \ldots, n_k$ are the children of $p$ then $\{ \namestyle{examples}(n_1), \ldots, \namestyle{examples}(n_k)\}$ is a partition of $\namestyle{examples}(p)$. \end{proof}

\sepproof{Proposition \ref{prp:2}}
{\em Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T \rangle$ denote a temporal decision tree, and let $l_1, \ldots, l_u$ be its leaves. Then
\begin{equation*}
\mathcal X_{\mathbb E,\mathbf A}(\mathbf T) = \sum_{i=1}^u  \chi(\mathcal L(l_i)) \cdot 
P(\namestyle{examples}(l); \mathbb E)
\end{equation*}}

\begin{proof}
By induction on the depth of $\mathbf T$. If $\mathbf T$ has depth $0$ then it consists of a 
single leaf $l$ and \ref{tdt:eq:expcost1} holds trivially since $\namestyle{examples}(l)$ must be 
equal to $\mathbb E$ and $P(\mathbb E; \mathbb E) = 1$.

If $\mathbf T$ has depth $> 0$ then let $\mathbf{T}_1, \ldots, \mathbf{T}_k$ denote its direct 
subtrees and $c_1, \ldots, c_k$ denote their roots. We can regard each $\mathbf{T}_i$ as an 
autonomous temporal decision tree compatible with te-set $\mathbb{E}_i = \namestyle{examples}(c_i)$. By 
induction hypothesis we have that:
\begin{equation}\label{tdt:eq:expcostcomp:1}
\mathcal{X}_{\mathbb{E}_i,\mathbf A}(\mathbf{T}_i) = \sum_{\textrm{$l$ leaf of $\mathbf{T}_i$}} 
\chi(\mathcal L(l)) \cdot P(\namestyle{examples}(l); \mathbb{E}_i) = \sum_{\textrm{$l$ leaf of 
$\mathbf{T}_i$}} \chi(\mathcal L(l)) \cdot \frac{P(\namestyle{examples}(l); \mathbb{E})}%
{P(\mathbb{E}_i; \mathbb E)}.
\end{equation}
Moreover by definition of expected cost: 
%%{\small\begin{eqnarray*}
\begin{multline}\label{tdt:eq:expcostcomp:2}
\mathcal{X}_{\mathbb E,\mathbf A} (\mathbf T)  =  \sum_{i=1}^k P(\mathcal L(r) \rightarrow \mathcal  L((r,c_i))) \cdot \mathcal{X}_{\mathbb{E}_i,\mathbf A} (\mathbf{T}_i) \quad \textrm{with} \\
P(\mathcal L(r) \rightarrow \mathcal  L((r,c_i))) = P(\namestyle{examples}(c_i); \namestyle{examples}(r)) = P(\mathbb{E}_i ; \mathbb E).
\end{multline}
From \eqref{tdt:eq:expcostcomp:1} and  \eqref{tdt:eq:expcostcomp:2} we thus obtain:
\begin{multline}\label{tdt:eq:expcostcomp:3}
\mathcal{X}_{\mathbb E,\mathbf A} (\mathbf T) = \sum_{i=1}^k  \sum_{\textrm{$l$ leaf of $\mathbf{T}_i$}} P(\mathbb{E}_i ; \mathbb E) \cdot \chi(\mathcal L(l)) \cdot \frac{P(\namestyle{examples}(l); \mathbb{E})} {P(\mathbb{E}_i; \mathbb E)}\\
= \sum_{i=1}^k \sum_{\textrm{$l$ leaf of $\mathbf{T}_i$}} \chi(\mathcal L(l)) \cdot 
P(\namestyle{examples}(l); \mathbb E) 
\end{multline}
Since the leaves of $\mathbf{T}$ are all and only the leaves of $\mathbf{T}_1, \ldots, \mathbf{T}_k$, 
\eqref{tdt:eq:expcostcomp:3} is equivalent to the thesis.
\end{proof}

\sepproof{Proposition \ref{tdt:prp:xpcost:2}}
{\em Let $\mathbf T = \langle r_{\mathbf T}, N_{\mathbf T}, E_{\mathbf T}, \mathcal{L}_{\mathbf T}, 
\mathcal{T}_{\mathbf T} \rangle$, $\mathbf U = \langle r_{\mathbf U}, N_{\mathbf U}, E_{\mathbf 
U}, \mathcal{L}_{\mathbf U}, \mathcal{T}_{\mathbf U} \rangle $ be two temporal decision trees 
compatible with the same te-set $\mathbb E$ and the same actions model $\mathbf A$. If $\mathbf T$ is more discriminating than $\mathbf U$ then $\mathcal{X}_{\mathbb E, \mathbf A}(\mathbf T) < 
\mathcal{X}_{\mathbb E,\mathbf A}(\mathbf U)$.}

\begin{proof} Rewriting equation \eqref{tdt:eq:expcost1} we obtain:
\begin{eqnarray}
\mathcal{X}_{\mathbb E,\mathbf A}(\mathbf T) & = & \sum_{i=1}^r  \chi(\mathcal{L}_{\mathbf 
T}(l_i)) 
\cdot P(\namestyle{examples}(l); \mathbb E) 
= \sum_{\namestyle{sit} \in \mathbb E} \chi(\mathcal{L}_{\mathbf T}
(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))) P(\namestyle{sit}; \mathbb E) \label{tdt:eq:discosts:t}\\
\mathcal{X}_{\mathbb E, \mathbf A}(\mathbf U) & = & \sum_{\namestyle{sit} \in \mathbb E} 
\chi(\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit}))) P(\namestyle{sit}; 
\mathbb E).\label{tdt:eq:discosts:u}
\end{eqnarray}
Since $\mathbf T$ is more discriminating than $\mathbf U$, we have that for all $\namestyle{sit} \in \mathbb E$:
$$ \mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit})) \prec 
\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit})) \quad\textrm{or}\quad 
\mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit})) =
\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit}))
$$ 
with at least one $\namestyle{sit}$ satisfying the first relation.
By definition of  $\chi$ it follows that for all $\namestyle{sit}$:
$$ \chi(\mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))) \leq
\chi(\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit})))$$ and for at least one \namestyle{sit}:
$$ \chi(\mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))) =
\chi(\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit})))$$
Therefore if we compare the individual elements of the two sums in \eqref{tdt:eq:discosts:t} and \eqref{tdt:eq:discosts:u} we observe there exists at least one $\namestyle{sit}$ for which:
$$ \chi(\mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))) P(\namestyle{sit}; \mathbb E) <
\chi(\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit}))) P(\namestyle{sit}; 
\mathbb E)$$ and for all other \namestyle{sit} 
$$ \chi(\mathcal{L}_{\mathbf T}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))) P(\namestyle{sit}; \mathbb E) \leq
\chi(\mathcal{L}_{\mathbf U}(\namestyle{leaf}_{\mathbf U}(\namestyle{sit}))) P(\namestyle{sit}; 
\mathbb E)$$
which concludes the proof.
\end{proof}

\sepproof{Theorem \ref{tdt:thr:lowxpcost}}
{\em Let $\mathbb E$ be a te-set with actions model $\mathbf A$. We have that:
\begin{romanenum}
\item There exists a decision tree $\overline{\mathbf{T}}$ compatible with $\mathbb E$ such that 
$\mathcal{X}_{\mathbb E, \mathbf A} (\overline{\mathbf T}) = \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$.
\item For every temporal decision tree $\mathbf T$ compatible with $\mathbb E$, $\overline{\mathcal 
X}_{\mathbb E, \mathbf A} \leq \mathcal{X}_{\mathbb E, \mathbf A}(\mathbf T)$. \theoend
\end{romanenum}}
In order to prove this theorem we introduce some lemmas.

\begin{lmm}\label{tdt:lmm:lowxpcost:1}
Let $\mathbf T$ be a temporal decision tree compatible with a te-set $\mathbb E$. Then 
$\namestyle{sit}_i \approx \namestyle{sit}_j$ implies $\namestyle{leaf}_{\mathbf T} ( 
\namestyle{sit}_i) = \namestyle{leaf}_{\mathbf T} (\namestyle{sit}_j)$.
\end{lmm}

\begin{proof}
We prove that $\namestyle{sit}_i \thicksim \namestyle{sit}_j$ implies 
$\namestyle{leaf}_{\mathbf T} ( \namestyle{sit}_i) = \namestyle{leaf}_{\mathbf T} 
(\namestyle{sit}_j)$, from which the lemma easily follows. Let us suppose that $\namestyle{leaf}_{\mathbf T} ( \namestyle{sit}_i) \neq \namestyle{leaf}_{\mathbf T} (\namestyle{sit}_j)$. This means that 
there is a common ancestor $n$ of the two leaves such that $\namestyle{sit}_i, \namestyle{sit}_j 
\in \namestyle{examples}(n)$ and $\namestyle{Val}(\namestyle{sit}_i, \langle \mathcal 
L(n),\mathcal T(n) \rangle) \neq \namestyle{Val}(\namestyle{sit}_j, \langle \mathcal L(n),\mathcal 
T(n) \rangle)$. Since $\namestyle{sit}_i \thicksim \namestyle{sit}_j$ this is possible only if 
$\mathcal T(n) > \min \{ \namestyle{Dl}(\namestyle{sit}_i), \namestyle{Dl}(\namestyle{sit}_j)\}$. 
But since $\mathbf T$ is compatible with $\mathbb E$ it must hold that $\mathcal T(n) \leq 
\namestyle{Dl}(\namestyle{examples}(n)) \leq \min \{ \namestyle{Dl}(\namestyle{sit}_i), 
\namestyle{Dl}(\namestyle{sit}_j)\}$, which contradicts the previous statement.
\end{proof}

\begin{lmm}\label{tdt:lmm:lowxpcost:2}
Let $\mathbb E$ be a te-set with sensors $s_1, \ldots, s_m$, time labels $t_1, \ldots, 
t_{\namestyle{last}}$ and actions model $\mathbf A$. There exists a temporal decision tree 
$\overline{\mathbf T} = \langle \overline{r}, \overline{N}, \overline{E}, \overline{\mathcal L}, 
\overline{\mathcal T} \rangle$ such that $\mathcal{X}_{\mathbb E, \mathbf A} (\overline{\mathbf T}) = 
\overline{\mathcal X}_{\mathbb E, \mathbf A}$.
\end{lmm}

\begin{proof}
In order to prove the thesis we construct a tree $\overline{\mathbf T}$ with the same expected cost as the te-set.

Let us define a total order on observations in $\mathbb E$ as follows: $\langle s,t \rangle < 
\langle s',t' \rangle$ if either $t < t'$ or $t = t'$ and $s$ precedes $s'$ in a lexicographic 
ordering. Let us denote by $o_1, \ldots, o_{\namestyle{max}}$ the ordered sequence of observations 
thus obtained. We shall define $\overline{\mathbf T}$ level by level (starting from the root, at 
level $1$) giving the value of $\mathcal L$ and $\mathcal T$ for nodes at level $h$.
%%Notice that 
%%once that these two functions have been defined for level $h$, nodes at level $h+1$ as well as 
%%their connections with their parents at level $h$ are completely specified. Moreover, once 
%%$\mathcal L$ and $\mathcal T$ have been defined for level $h$, also the \namestyle{examples} 
%%function is defined for nodes at level $h+1$ (in the particular case of the root, we already know 
%%that $\namestyle{examples}(r) = \mathbb E$).

$\overline{\mathbf T}$ has a maximum of $\namestyle{max}+1$ levels, where \namestyle{max} is the number of 
observations. New levels are added until all nodes in a level are leaves (which as we shall see 
happens at most at level $\namestyle{max}+1$). Let thus $n$ be a node at level $h$ , and let 
$\langle s_{i_h}, t_{i_h} \rangle = o_h$ if $h \leq \namestyle{max}$. We have:
\begin{eqnarray*}
n & \textrm{is} & \begin{cases}
                    \textrm{a {\em leaf}} & \textrm{if $h = \namestyle{max}+1$, or 
                    $\namestyle{Dl}(\namestyle{examples} (n)) < t_{i_h}$;}\\
                    \textrm{an {\em internal node}} & \textrm{otherwise.}
                    \end{cases}\\
\mathcal L (n) & = & \begin{cases}
                    \namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit} \mid \namestyle{sit} \in 
                    \namestyle{examples} (n) \}) & \textrm{if $n$ is a leaf;}\\
                    s_{i_h} & \textrm{if $n$ is an internal node.}
                    \end{cases}\\
\mathcal T(n) & = & t_{i_h} \quad \textrm{if $n$ is an internal node.}
\end{eqnarray*}
A decision-making agent running such a tree would essentially take into account {\em all} sensor 
measurement at {\em all} time labels until either there are no more available observations or it 
must perform a recovery action because a deadline is about to expire.

Now we need to show that $\mathcal{X}_{\mathbb E, \mathbf A}(\overline{\mathbf T}) = 
\overline{\mathcal X}_{\mathbb E, \mathbf A}$. 

Let $l_1, \ldots, l_u$ denote the leaves of $\overline{\mathbf T}$. We shall first of all prove 
that $\namestyle{sit}_i \approx \namestyle{sit}_j$ if and only if $\namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit}_i)= \namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit}_j)$, or equivalently that
$$\{ \namestyle{examples}(l_1), \ldots, \namestyle{examples}(l_u) \} = \mathbb E/\ordapprox.$$
This, together with equations \eqref{tdt:eq:expcost1} and \eqref{tdt:eq:lowxpcost} yields the thesis.

We already know from lemma \ref{tdt:lmm:lowxpcost:1} that $\namestyle{sit}_i \approx 
\namestyle{sit}_j$ implies $\namestyle{leaf}_{\overline{\mathbf T}} (\namestyle{sit}_i) = 
\namestyle{leaf}_{\overline{\mathbf T}} (\namestyle{sit}_j)$; we need to show that the opposite is 
also true. Let us thus assume that $\namestyle{sit}_i, \namestyle{sit}_j \in 
\namestyle{examples}(l)$ for some $l \in \{l_1, \ldots, l_u \}$. Let $r=n_1, n_2, \ldots, n_H, 
n_{H+1}=l$ be the path from the root to $l$. We know from the definition of $\overline{\mathbf T}$ 
that for all $h \leq H$, $\langle \mathcal L(n_h), \mathcal T(n_h) \rangle = o_h$, and that $o_1, 
\ldots, o_H$ are {\em all} observations $\langle s,t \rangle $ of $\mathbb E$ such that $t \leq 
\namestyle{Dl}(\namestyle{examples}(l))$. Moreover since $\namestyle{sit}_i , \namestyle{sit}_j 
\in \namestyle{examples}(l)$ we have that for all $h = 1, \ldots, H$, 
$\namestyle{Val}(\namestyle{sit}_i, o_h) = \namestyle{Val}(\namestyle{sit}_j, o_h)$. 

Now there are two possibilities: either $\namestyle{Dl}(\namestyle{examples}(l)) = \min \{ 
\namestyle{Dl}(\namestyle{sit}_i), \namestyle{Dl}(\namestyle{sit}_j) \}$, or 
$\namestyle{Dl}(\namestyle{examples}(l)) < \min \{ \namestyle{Dl}(\namestyle{sit}_i), 
\namestyle{Dl}(\namestyle{sit}_j) \}$. 

In the first case we immediately obtain that $\namestyle{sit}_i \thicksim \namestyle{sit}_j$ and 
thus $\namestyle{sit}_i \approx \namestyle{sit}_j$. 

In the second case, there must be $\namestyle{sit}_k \in \namestyle{examples}(l)$ such that 
$\namestyle{Dl}(\namestyle{examples}(l)) = \namestyle{Dl}(\namestyle{sit}_k)$. Moreover, 
$\namestyle{Dl}(\namestyle{sit}_k) = \min\{ \namestyle{Dl}(\namestyle{sit}_i), 
\namestyle{Dl}(\namestyle{sit}_k) \} = \min\{ \namestyle{Dl}(\namestyle{sit}_j), \namestyle{Dl}( 
\namestyle{sit}_k) \}$. Since all considerations above apply also to $\namestyle{sit}_k$ we thus 
have that $\namestyle{sit}_i \approx \namestyle{sit}_k$ and $\namestyle{sit}_k \approx 
\namestyle{sit}_j$; therefore by transitivity $\namestyle{sit}_i \approx \namestyle{sit}_j$.
\end{proof}

\begin{lmm}\label{tdt:lmm:lowxpcost:3}
Let $\mathbf T = \langle r, N, E, \mathcal L, \mathcal T \rangle$ be a decision tree compatible with a 
te-set $\mathbb E$ with actions model $\mathbf A$. Then $\overline{\mathcal X}_{\mathbb E, \mathbf 
A} \leq \mathcal{X}_{\mathbb E, \mathbf A} (T)$.
\end{lmm}

\begin{proof}
Let $\overline{\mathbf T}$ be as defined in the proof of lemma \ref{tdt:lmm:lowxpcost:2}. In order 
to prove the thesis it suffices to show that $\overline{\mathbf T}$ is either equally\footnote{Rather intuitively, two trees are equally discriminating if they associate to each fault situation the same recovery action.} or more discriminating than 
$\mathbf T$ (see proposition \ref{tdt:prp:xpcost:2}). Actually we shall show that given $\namestyle{sit} \in \mathbb E$ either $\overline{\mathcal 
L}(\namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit})) \prec \mathcal 
L(\namestyle{leaf}_{\mathbf T} (\namestyle{sit}))$ or $\overline{\mathcal 
L}(\namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit})) = \mathcal 
L(\namestyle{leaf}_{\mathbf T} (\namestyle{sit}))$. 

We know that $\namestyle{examples}(\namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit})) 
\subseteq \namestyle{examples}(\namestyle{leaf}_{\mathbf T}(\namestyle{sit}))$. In fact, let 
$\namestyle{sit}'$ be an element of $\namestyle{examples}(\namestyle{leaf}_{\overline{\mathbf 
T}}(\namestyle{sit}))$ different from \namestyle{sit} itself: by construction of $\overline{\mathbf T}$ we have that 
$\namestyle{sit} \approx \namestyle{sit}'$, and by lemma \ref{tdt:lmm:lowxpcost:1} it follows that
$\namestyle{leaf}_{\mathbf T}(\namestyle{sit}) = \namestyle{leaf}_{\mathbf T}(\namestyle{sit}')$.

Let:
%%\begin{eqnarray*}
$$\overline{A} =  \{ \namestyle{Act}(s) \mid s \in \namestyle{examples} 
(\namestyle{leaf}_{\overline{\mathbf T}} (\namestyle{sit})) \},%%\\
A  = \{ \namestyle{Act}(s) \mid s \in \namestyle{examples}(\namestyle{leaf}_{\mathbf T} 
(\namestyle{sit})) \}.
$$%%\end{eqnarray*}
Since $\overline{A} \subseteq A$, by definition of \namestyle{merge}:
$$ \namestyle{merge}(\overline{A}) \prec \namestyle{merge}(A) \quad\textrm{or}\quad \namestyle{merge}(\overline{A}) = \namestyle{merge}(A)$$
Thus having $\mathcal L (\namestyle{leaf}_{\overline{\mathbf T}}(\namestyle{sit})) = \namestyle{merge} 
(\overline{A})$ and $\mathcal L (\namestyle{leaf}_{{\mathbf T}}(\namestyle{sit})) = \namestyle{merge} 
({A})$ we obtain that either the action selected by $\overline{\mathbf T}$ is weaker than that selected by $\mathbf T$, or it is the same.
\end{proof}

Now we can prove theorem \ref{tdt:thr:lowxpcost}.

\begin{proof} Point {\em (i)} is proved by lemma \ref{tdt:lmm:lowxpcost:2}, while point {\em (ii)} corresponds to lemma \ref{tdt:lmm:lowxpcost:3}.
\end{proof}

\sepproof{Proposition \ref{tdt:prp:fundprop}}
{\em Let us consider an execution of \funname{BuildTemporalTree} starting with a main call $c_0$. The 
initial te-set, which we want to build a tree over, is $\mathbb E = \mathbb{E}_{c_0}$ with 
$\mathbf A = \doublel \varname{ActModel} \doubler_{c_0}$. For any recursive call $c$, let us 
denote by $\mathbb{E}_c^*$ the te-set determined by $\doublel \varname{Examples} \doubler_c$ and 
$\doublel \varname{Obs\_Update} \doubler_{c}$. Then: 
\begin{myenum} 
\item $\mathcal{X}_{\mathbb E, \mathbf A} (\actval{T}{c_0}) \geq \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$
\item $\mathcal{X}_{\mathbb E, \mathbf A} (\actval{T}{c_0}) = \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$ if and only if for every non terminal\footnote{We exclude terminal calls because 
they do not even compute \varname{Obs\_Update}.} recursive call $c$ generated by $c_0$ it holds 
that $\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} = \overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A}$
\end{myenum}}

\begin{proof}
We shall prove \namestyle{(1)} and \namestyle{(2)} for every recursive call $c$ (rather than only for $c_0$). The 
proof is by induction on the depth of the recursion starting from $c$.
\begin{description}
\item[\bfseries depth $= 0$.] Then $c$ is terminal, and we only have to prove that $\mathcal{X}_{\mathbb E, \mathbf A} (\actval{T}{c}) = \overline{\mathcal X}_{\mathbb E, 
\mathbf A}$. There are two reasons why $c$ may be terminal: either {\em (i)} all fault situations 
in $\actval{Examples}{c}$ are associated with the same recovery action $A$, or {\em (ii)} 
$\actval{ValidObs}{c} = \varnothing$. 
\begin{romanenum}

\item From definition \ref{tdt:dfn:lowxpcost} we have:
\begin{eqnarray*}
\overline{\mathcal X}_{\mathbb E, \mathbf A} & = & \sum_{\eta \in \mathbb{E}_c/\ordapprox} 
    \chi(\namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit}) \mid \namestyle{sit} \in \eta \})) 
    \cdot P(\eta ; \mathbb{E}_c)\\
    & = & \sum_{\eta \in \mathbb{E}_c/\ordapprox} \chi(A) \cdot P(\eta ; 
    \mathbb{E}_c)\\
    & = & \chi(A) \sum_{\eta \in \mathbb{E}_c/\ordapprox} P(\eta ; \mathbb{E}_c) = 
    \chi(A).
\end{eqnarray*}
Since $\actval{T}{c}$ is made of a single leaf $l$ with $\mathcal L(l) = A$ we also have that 
$\mathcal{X}_{\mathbb{E}_c,\mathbf A}(\actval{T}{c}) = \chi(A)$, which proves the thesis.
\item If $\actval{ValidObs}{c} = \varnothing$ then for all $\langle s,t 
\rangle \in \actval{Examples}{c}$, $t > \namestyle{Dl}(\actval{Examples}{c})$. Let 
$\namestyle{sit} \in \mathbb{E}_c$ be such that $\namestyle{Dl}(\namestyle{sit}) = 
\namestyle{Dl}(\actval{Examples}{c})$. Then by definition of indistinguishability for any 
$\namestyle{sit}' \in \mathbb{E}_c$ we have that $\namestyle{sit} \thicksim \namestyle{sit}'$. 
This proves that $\mathbb{E}_c/\ordapprox$ is made of a single equivalence class which coincides 
with $\mathbb{E}_c$ itself. Thus $\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} =  \chi 
(\namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit}) \mid \namestyle{sit} \in \mathbb{E}_c 
\}))$. Since $\actval{T}{c}$ is made of a single leaf $l$ with $\mathcal L(l) = 
\namestyle{merge}(\{ \namestyle{Act}(\namestyle{sit}) \mid \namestyle{sit} \in \mathbb{E}_c \})$, 
it follows that $\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) = \overline{\mathcal 
X}_{\mathbb{E}_c, \mathbf A}$.
\end{romanenum}
\item[depth $> 0$.] Then $c$ is not terminal and \funname{ChooseObs} selects an observation $o = 
\langle s,t \rangle$. Let $v_1, \ldots, v_k$ be the possible values for $o$: then $c$ has $k$ 
inner recursive calls to \funname{BuildTemporalTree}, which we shall denote respectively by $c_1, 
\ldots, c_k$. We have that $\{\mathbb{E}_{c_1}, \ldots, \mathbb{E}_{c_k}\}$ is a partition of 
$\mathbb{E}_c^*$. 

By definition of expected cost (\ref{tdt:dfn:expcost}) we have that:
$$ \mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) = \sum_{i=1}^k P(\restr{\mathbb{E}_{c}}{o 
\rightarrow v_i} ; \mathbb{E}_c) \cdot \mathcal{X}_{\restr{\mathbb{E}_{c}}{o \rightarrow v_i}, 
\mathbf A} (\actval{T}{c_i})
$$
$\restr{\mathbb{E}_{c}}{o \rightarrow v_i}$ and $\mathbb E_{c_i}$ differ only in the set of 
observations, which is $\actval{Obs}{c}$ for the former and $\actval{Obs\_Update}{c}$ for the 
latter. However we have that:
\begin{compactitem}
\item $P(\restr{\mathbb{E}_{c}}{o \rightarrow v_i} ; \mathbb{E}_c) = P(\mathbb{E}_{c_i} ; 
\mathbb{E}_c)$ since probabilities depend only on the fault situations in a te-set, and not on the 
observations.
\item $\mathcal{X}_{\restr{\mathbb{E}_{c}}{o \rightarrow v_i}, \mathbf A} (\actval{T}{c_i}) = 
\mathcal{X}_{\mathbb{E}_{c_i}, \mathbf A} (\actval{T}{c_i})$: expected cost depends also on the 
observations, but $\actval{T}{c_i}$ by construction can contain as labels only those observations 
in $\mathbb{E}_{c_i}$.
\end{compactitem}
Moreover, since also $\mathbb{E}_c$ and $\mathbb{E}_c^*$ differ only in the observations 
$P(\mathbb{E}_{c_i} ; \mathbb{E}_c) = P(\mathbb{E}_{c_i} ; \mathbb{E}_c^*)$. Therefore we can 
write: 
$$\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c})  =  \sum_{i=1}^k 
P(\mathbb{E}_{c_i} ; \mathbb{E}_{c}^* ) \cdot \mathcal{X}_{\mathbb{E}_{c_i}, \mathbf A} 
(\actval{T}{c_i})$$ In order to prove \namestyle{(1)}, we can apply the induction hypothesis 
$\mathcal{X}_{\mathbb{E}_{c_i}, \mathbf A} (\actval{T}{c_i}) \geq \overline{\mathcal 
X}_{\mathbb{E}_{c_i}, \mathbf A}$) and obtain: 

\begin{equation}\label{tdt:eq:fundprop:1}
\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) \geq \sum_{i=1}^k P(\mathbb{E}_{c_i} ; 
\mathbb{E}_{c}^*) \cdot \overline{\mathcal X}_{\mathbb{E}_{c_i}, \mathbf A}
\end{equation}
Now let us work on the right-hand side expression in \ref{tdt:eq:fundprop:1}:
\begin{eqnarray*}
\sum_{i=1}^k P(\mathbb{E}_{c_i} ; \mathbb{E}_{c}^*) \cdot \overline{\mathcal X}_{\mathbb{E}_{c_i}, 
\mathbf A} & = & \sum_{i=1}^k P(\mathbb{E}_{c_i} ; \mathbb{E}_{c}^*) \sum_{\eta \in 
\mathbb{E}_{c_i}/\ordapprox} \chi ( \namestyle{Act} (\eta)) \cdot P(\eta; \mathbb{E}_{c_i})\\
& = & \sum_{i=1}^k \sum_{\eta \in \mathbb{E}_{c_i}/\ordapprox} \chi(\namestyle{Act}(\eta)) \cdot 
P(\eta ; \mathbb{E}_{c_i}) \cdot P(\mathbb{E}_{c_i} ; \mathbb{E}_{c}^*) \\
& = & \sum_{i=1}^k \sum_{\eta \in \mathbb{E}_{c_i}/\ordapprox} \chi(\namestyle{Act}(\eta)) \cdot 
P(\eta ; \mathbb{E}_c^*)
\end{eqnarray*}
Notice however that $\{ \mathbb{E}_{c_i}/\ordapprox \}$ is a partition of 
$\mathbb{E}^*_c/\ordapprox$; in other words each $\eta \in \mathbb{E}^*_c/\ordapprox$ belongs to 
exactly one set $\mathbb{E}_{c_i}/\ordapprox$.  In fact, splitting examples according to the value of one observation cannot split a class of undistinguishable observations. Thus the above equality becomes: 
$$
\sum_{i=1}^k P(\mathbb{E}_{c_i} ; \mathbb{E}_{c}^*) \cdot \overline{\mathcal X}_{\mathbb{E}_{c_i}, 
\mathbf A} =  \sum_{\eta \in \mathbb{E}^*_c/\ordapprox} \chi(\namestyle{Act}(\eta)) \cdot P(\eta; 
\mathbb{E}^*_c) = \overline{\mathcal X}_{\mathbb{E}_c^*, \mathbf A}
$$ 
This, together with \ref{tdt:eq:fundprop:1}, yields:
\begin{equation}\label{tdt:eq:fundprop:2}
\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) \geq \overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A}
\end{equation}
As mentioned above, the only difference between $\mathbb{E}_c^*$ and $\mathbb{E}_c$ is that the 
former has fewer observations. This implies that, if $\namestyle{sit} \approx \namestyle{sit}'$ in 
$\mathbb{E}_c$, then $\namestyle{sit} \approx \namestyle{sit}'$ in $\mathbb{E}_c^*$ as well. This 
means that $\mathbb{E}_c/\ordapprox$ is a {\em sub-partition}\footnote{$\mathbb{E}_c/\ordapprox$ 
is not a sub-partition of $\mathbb{E}_c^*/\ordapprox$ in the ordinary sense because they do not 
have the same set of observations.} of $\mathbb{E}_c^*/\ordapprox$ in the following sense: we can 
partition every $\theta \in \mathbb{E}_c^*/\ordapprox$ in $\eta(\theta) = \{\eta'_1, \ldots, 
\eta'_{k_\theta}\}$ such that for each $\eta'_j$ there exists exactly one $\eta_j \in 
\mathbb{E}_c/\ordapprox$ containing exactly the same fault situations as $\eta'_j$. This yields: 
$$
\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} = \sum_{\eta \in \mathbb{E}_c/\ordapprox} 
\chi(\namestyle{Act}(\eta)) \cdot P(\eta ; \mathbb{E}_c) 
$$
Since each $\eta'_j$ has the same fault situations as the corresponding $\eta_j$, and necessarily 
for each $\eta_j$ there is a $\theta$ containing it, we have: 
$$
\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} =  \sum_{\theta \in \mathbb{E}_c^*/\ordapprox} 
\sum_{\eta' \in \eta(\theta)} \chi(\namestyle{Act}(\eta')) \cdot P(\eta ; \mathbb{E}_c^*) 
$$
If $\eta' \in \eta(\theta)$ the fault situations in $\eta'$ are a subset of those in $\theta$; 
thus $\chi(\namestyle{Act}(\eta')) \leq \chi(\namestyle{Act}(\theta))$. Then we obtain: 
\begin{eqnarray*} 
    \overline{\mathcal X}_{\mathbb{E}_c, \mathbf A} 
    & \leq & \sum_{\theta \in \mathbb{E}_c^*/\ordapprox} \sum_{\eta' \in \eta(\theta)} 
    \chi(\namestyle{Act}(\theta)) \cdot P(\eta';\mathbb{E}_c^*) \\
    & = & \sum_{\theta \in \mathbb{E}_c^*/\ordapprox} \chi(\namestyle{Act}(\theta)) \cdot 
    \sum_{\eta' \in \eta(\theta)} P(\eta' ; \mathbb{E}_c^*) \\
    & = & \sum_{\theta \in \mathbb{E}_c^*/\ordapprox} \chi(\namestyle{Act}(\theta)) \cdot 
    P(\theta ; \mathbb{E}_c^*) = \overline{\mathcal X}_{\mathbb{E}_c^*, \mathbf A}
\end{eqnarray*}
Together with equation \ref{tdt:eq:fundprop:2}, this proves \namestyle{(1)}:
$$ 
\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) \geq 
\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A}
$$
Now let us prove \namestyle{(2)}. The induction hypothesis changes \ref{tdt:eq:fundprop:1}, and thus
\ref{tdt:eq:fundprop:2}, into equalities, thus yielding:
\begin{equation}\label{tdt:eq:fundprop:3}
\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) = \overline{\mathcal X}_{\mathbb{E}_c^*, 
\mathbf A}
\end{equation}
Since by hypothesis in (2) we have that $\overline{\mathcal X}_{\mathbb{E}_c^*, \mathbf A} = 
\overline{\mathcal X}_{\mathbb{E}_c, \mathbf A}$, we immediately obtain:
$$
\mathcal{X}_{\mathbb{E}_c, \mathbf A} (\actval{T}{c}) = \overline{\mathcal X}_{\mathbb{E}_c, 
\mathbf A}
$$
\end{description}
which concludes the proof. 
\end{proof}

\sepproof{Proposition \ref{tdt:prp:safe:1}}
{\em Let $c, d$ denote two independent calls to \funname{BuildTemporalTree} with the same input 
arguments but with different implementations of \funname{ChooseObs}. If $\actval{tlabel}{c} \leq 
\actval{tlabel}{d}$ then $\overline{\mathcal X}_{\mathbb{E}_c^*,\mathbf A} \leq \overline{\mathcal 
X}_{\mathbb{E}_d^*, \mathbf A}$.}

\begin{proof} Follows immediately from $\actval{Obs\_Update}{c} \subseteq 
\actval{Obs\_Update}{d}$. 
\end{proof}

\sepproof{Proposition \ref{tdt:prp:safe:2}}
{\em Let $c$ be  a call to \funname{BuildTemporalTree}. If $\actval{tlabel}{c} = t_{\namestyle{min}_c} 
= \min\{t \mid \langle t,s \rangle \in \actval{ValidObs}{c} \}$ then $\overline{\mathcal 
X}_{\mathbb{E}_c^*,\mathbf A} \leq \overline{\mathcal X}_{\mathbb{E}_c, \mathbf A}$.}

\begin{proof} In this case $\actval{Obs\_Update}{c} = \actval{UsefulObs}{c}$, thus the only removed 
observations are non discriminating ones.
\end{proof}

\sepproof{Proposition \ref{prp:3}}
{\em For any call $c$ to \funname{BuildTemporalTree} there exist a time label $t_{\namestyle{max}_c}$ 
such that the safe time labels are all and only those $t$ with $t_{\namestyle{min}_c} \leq t \leq 
t_{\namestyle{max}_c}$, where $t_{\namestyle{min}_c}$ is as in proposition \ref{tdt:prp:safe:2}.}

\begin{proof} Straightforward. \end{proof}
\bibliographystyle{theapa}
\bibliography{Biblio/diagn,Biblio/learning,Biblio/torino}

\end{document}
