text:
% This file contains the content for a main section
\regularsectionformat
%% Modify below this line %%
\chapter{XML Elements}
\label{sec:XMLelements}

\section{\texttt{ProcessList}}
This is the root element for any LUT XML file and is required even if only one \texttt{ProcessNode} will be present. A \texttt{ProcessList} is composed of one or more \texttt{ProcessNode}s.

Attributes:
\begin{xmlfields}
	\xmlitem[id][required] Unique identifier of the \texttt{ProcessList}.
	\xmlitem[name][optional] Text name of the \texttt{ProcessList} for display or selection from an application's user interface.
	\xmlitem[compCLFversion][required] Minimum compatible CLF spec version needed to read this file.
	\xmlitem[inverseOf][optional] Optional field for linking to another \texttt{ProcessList id} (unique) which is the inverse of this one.
\end{xmlfields}

Elements:
\begin{xmlfields}
    \xmlitem[Description][required] Comment field for an arbitrary string describing the function, usage, or notes about the \texttt{ProcessList}. A \texttt{ProcessList} can have one or more \texttt{Description}s.
    \xmlitem[Info][optional] optional element for addition of custom metadata not needed to interpret the transforms. Includes:
    	\begin{xmlfields}
			\xmlitem[AppRelease][optional] application software release level
			\xmlitem[CalibrationInfo][optional] calibration metadata used when making the LUT for a device
			\begin{list}{}{\setlength{\itemsep}{4pt}}
				\item \texttt{\textless DisplayDeviceSerialNum\textgreater}
				\item \texttt{\textless DisplayDeviceHostName\textgreater}
				\item \texttt{\textless OperatorName\textgreater}
				\item \texttt{\textless CalibrationDateTime\textgreater}
				\item \texttt{\textless MeasurementProbe\textgreater}
				\item \texttt{\textless CalibrationSoftwareName\textgreater}
				\item \texttt{\textless CalibrationSoftwareVersion\textgreater}
			\end{list}
    	\end{xmlfields}
    \xmlitem[InputDescriptor][optional] Comment field describing the intended source code values of the \texttt{ProcessList}.
    \xmlitem[OutputDescriptor][optional] Comment field describing the intended output target of the \texttt{ProcessList} (e.g., target display).
    \xmlitem[ProcessNode][required] At least one \texttt{ProcessNode} must be in the list. The \texttt{ProcessNode} is described in \autoref{sec:ProcessNode}.
\end{xmlfields}

\section{\texttt{ProcessNode}}
\label{sec:ProcessNode}
This element represents a process node; it is the primary color transformation element for LUT interchange. Different types of processing are expressed by substitution from this basic element including \texttt{LUT1D}, \texttt{LUT3D}, \texttt{Range} and \texttt{Matrix}. In the future, other kinds of \texttt{ProcessNode}s can be defined as part of the standard to handle alternate forms of processing. All \texttt{ProcessNode} substitutes inherit the attributes and elements below.

Attributes:
\begin{xmlfields}
	\xmlitem[id][optional]  Unique identifier of the \texttt{ProcessNode}.
	\xmlitem[name][optional] Text name of the \texttt{ProcessNode} for display or selection from an application's user interface.
	\xmlitem[inBitDepth][required] Number of bits and type of the input values to which the \texttt{ProcessNode} is applied. The input values can be either integers or floats. Supported values are ``\texttt{8i}'', ``\texttt{10i}'', ``\texttt{12i}'', ``\texttt{16i}'', ``\texttt{16f}'' or ``\texttt{32f}''.
	\xmlitem[outBitDepth][required] Number of bits and type of the output values which the \texttt{ProcessNode} generates. The output values can be either integers or floats, independent of the input values. Supported values are ``\texttt{8i}'', ``\texttt{10i}'', ``\texttt{12i}'', ``\texttt{16i}'', ``\texttt{16f}'' or ``\texttt{32f}''.
\end{xmlfields}

Elements:
\begin{xmlfields}
	\xmlitem[Description][optional] Comment field for an arbitrary string describing the function, usage, or notes about the \texttt{ProcessNode}. A \texttt{ProcessNode} can have one or more \texttt{Description}s.
\end{xmlfields}

\subsection{\texttt{LUT1D} (substitute for \texttt{ProcessNode})}
This element specifies a 1D LUT or a 3by1D LUT.  A 1D LUT transform uses an input pixel value, finds the two nearest index positions in the LUT, and then interpolates the output value using the entries associated with those positions. If the input to a \texttt{LUT1D} is an RGB value, the same LUT will be applied to all three color components. If a 3by1D LUT is supplied, each color component is looked up in a separate \texttt{LUT1D} of the same length. In both cases, the ordered entries of the LUT are provided in \texttt{Array}.  In a 3by1D LUT, by convention, the \texttt{LUT1D} for the first component goes in the first column of \texttt{Array},  etc.).  The lookup operation may be altered by redefining the mapping of the input values to index positions of the LUT using an \texttt{IndexMap}.

Attributes:
\begin{xmlfields}
	\xmlitem[interpolation][optional] Name or description of the preferred calculation used to interpolate values from the \texttt{LUT1D}. This attribute is optional with a default of ``\texttt{linear}'' if the attribute is not present. Systems that utilize LUTs may use different types of interpolation; therefore, this attribute is intended as a guide to an application if it wants to attempt recreating the exact outputs of the originating application. Typical values for this attribute would be ``\texttt{linear}'' or ``\texttt{cubic}''.
	\xmlitem[rawHalfs][optional] If this attribute is present, its value must be ``\texttt{true}''. In this case, the output array values in the form of unsigned 16-bit integers are interpreted as the equivalent bit pattern, half floating-point values. (e.g.  to represent the value 1.0, enter the integer 15360 in the \texttt{Array} element because it has the same bit-pattern. This allows specification of exact half-float values without relying on conversion from decimal text strings.)
	\xmlitem[halfDomain][optional] If this attribute is present, its value must be ``\texttt{true}''. In this case, the input domain to the node is all possible 16-bit floating-point values, and there must be exactly 65536 entries in the LUT1D \texttt{Array} element (e.g. the unsigned integer 15360 has the same bit-pattern (0011110000000000) as the half-float value 1.0, so the 15360th, zero-indexed, entry in the \texttt{Array} element is the output value corresponding to an input value of 1.0). The \texttt{IndexMap} may not be used in this case.
\end{xmlfields}

Elements:
\begin{xmlfields}
	\xmlitem[IndexMap][optional] Table that maps input values to index positions of the \texttt{LUT1D}'s \texttt{Array}.\par
		In its simplest form, with a dim=2, this element can be used to define the input floating-point range that will be used by the LUT.\par
		An extension to the LUT format described in Appendix \ref{appendixC}.
	\xmlitem[Array][required] Table that provides the entries of the \texttt{LUT1D} from the minimum to the maximum input values. In a 3by1D LUT, each column in \texttt{Array} provides the 1D LUT for a color component; for RGB, the 1st column corresponds to R’s 1D LUT, the 2nd column corresponds to G’s 1D LUT, etc.
\end{xmlfields}

\subsection{\texttt{LUT3D} (substitute for \texttt{ProcessNode})}
This element specifies a 3D LUT. In a \texttt{LUT3D} element, the 3 color components of the input value are used to find the nearest indexed values along each axis of the 3D cube. The 3-component output value is calculated by interpolating within the volume defined by the nearest corresponding positions in the LUT. The lookup operation may be altered by redefining the mapping of the input values to index positions into the LUT (see \texttt{IndexMap}). An interpolation comment field is provided to indicate the preferred interpolation calculation to perform within the volume.

Attributes:
\begin{xmlfields}
	\xmlitem[interpolation][optional] Name or description of the preferred calculation used to interpolate values in the \texttt{3DLUT}. This attribute is optional with a default of ``\texttt{trilinear}'' if the attribute is not present. Systems that utilize LUTs may use different types of interpolation; therefore, this attribute is  intended as a guide to an application if it wants to attempt recreating the exact outputs of the originating application. Typical values for this attribute would be ``\texttt{trilinear}'' or ``\texttt{tetrahedral}''.
\end{xmlfields}

Elements:
\begin{xmlfields}
	\xmlitem[IndexMap][optional] Table that maps input values to index positions of the \texttt{LUT3D}'s \texttt{Array}.
		In its simplest form, with a dim=2, this element can be used to define the input floating-point range that will be used by the LUT.\par
		An extension to the LUT format described in Appendix \ref{appendixC}.
	\xmlitem[Array][required] Table comprised of the entries for the \texttt{LUT3D} from the minimum to the maximum input values, the third component index changing fastest.

		Ex:   order of entries for a 2x2x2 cube by index $[0 \ldots 1]$

		\begin{center}
			\begin{tabularx}{1in}{XXX}
				0 & 0 & 0 \\
				0 & 0 & 1 \\
				0 & 1 & 0 \\
				0 & 1 & 1 \\
				1 & 0 & 0 \\
				1 & 0 & 1 \\
				1 & 1 & 0 \\
				1 & 1 & 1 \\
			\end{tabularx}
		\end{center}
\end{xmlfields}

\subsection{\texttt{Matrix} (substitute for \texttt{ProcessNode})}
This element specifies a matrix transformation to be applied to the input values. The input and output of a \texttt{Matrix} are always 3-component values. All matrix calculations should be performed in floating point, and input bit depths of integer type should be treated as scaled floats. If the input bit depth and output bit depth do not match, the coefficients in the matrix must incorporate the results of the `scale' factor that will convert the input bit depth to the output bit depth (e.g. input of \texttt{10i} with an output of \texttt{12i} requires the matrix coefficients already have a factor of 4095/1023 applied). Changing the input or output bit depth requires creation of a new set of coefficients for the LUT.

The output values are calculated using the row-order convention:

\begin{equation}
    \begin{bmatrix*}
        a_{11} & a_{12} & a_{13} \\
        a_{21} & a_{22} & a_{23} \\
        a_{31} & a_{32} & a_{33} \\
    \end{bmatrix*} \\
    \begin{bmatrix}
        r\\
        g\\
        b
    \end{bmatrix}
    =
    \begin{bmatrix}
        R\\
        G\\
        B
    \end{bmatrix}
\end{equation}
\begin{align*}
	R = (r \cdot a_{11}) + (g \cdot a_{12}) + (b \cdot a_{13}) \\
	G = (r \cdot a_{21}) + (g \cdot a_{22}) + (b \cdot a_{23}) \\
	B = (r \cdot a_{31}) + (g \cdot a_{32}) + (b \cdot a_{33})
\end{align*}

An offset matrix may be defined as a 3x4 array in which the input value is typically defined as ($r$, $g$, $b$, 1.0).  The 4th column of the matrix may then be used to add an offset term to the conversion of the matrix. The output of the 3x4 matrix is ($R$, $G$, $B$). Matrices using an offset calculation will have one more column than rows.

\begin{equation}
    \begin{bmatrix*}
        a_{11} & a_{12} & a_{13} & off1\\
        a_{21} & a_{22} & a_{23} & off2\\
        a_{31} & a_{32} & a_{33} & off3\\
    \end{bmatrix*} \\
    \begin{bmatrix}
        r\\
        g\\
        b\\
        1.0
    \end{bmatrix}
    =
    \begin{bmatrix}
        R\\
        G\\
        B
    \end{bmatrix}
\end{equation}

Elements:
\begin{xmlfields}
	\xmlitem[Array][required] Table that provides the coefficients of the transformation matrix. The matrix dimensions are either 3x3 or 3x4. The matrix is serialized row by row from top to bottom and from left to right, i.e., ``$a_{11}\ a_{12}\ a_{13}\ a_{21}\ a_{22}\ a_{23}\ \ldots$'' for a 3x3 matrix.
		\begin{equation}
		    \begin{bmatrix*}
		        a_{11} & a_{12} & a_{13} \\
		        a_{21} & a_{22} & a_{23} \\
		        a_{31} & a_{32} & a_{33} \\
		    \end{bmatrix*} \\
		\end{equation}

\end{xmlfields}

\subsection{\texttt{Range} (substitute for \texttt{ProcessNode})}
The \texttt{Range} element maps the input domain to the output range by scaling and offsetting values and must be calculated in floating point. The \texttt{Range} element is also used to clamp values.

If a \texttt{minInValue} is present, then \texttt{minOutValue} must also be present and the result is clamped at the low end. Similarly, if \texttt{maxInValue} is present, then \texttt{maxOutValue} must also be present and the result is clamped at the high end. If none of \texttt{minInValue}, \texttt{minOutValue}, \texttt{maxInValue}, or \texttt{maxOutValue} are present, then the \texttt{Range} operator performs only scaling.

The scaling of \texttt{minInValue} and \texttt{maxInValue} depends on the input bit depth, and the scaling of \texttt{minOutValue} and \texttt{maxOutValue} depends on the output bit depth.

Elements:
\begin{xmlfields}
	\xmlitemopt[minInValue][optional]
	\xmlitemopt[maxInValue][optional]
	\xmlitemopt[minOutValue][optional]
	\xmlitemopt[maxOutValue][optional]
\end{xmlfields}

Attributes:
\begin{xmlfields}
	\xmlitem[style][optional]
		Description of the preferred handling of the scaling calculation of the \texttt{Range} node. If the style attribute is not present, clamping is performed.
		\begin{xmlfields}
			\xmlitemd[``noClamp''] If present, do not apply the clamping in the equations below (i.e. floating point values above \texttt{maxOutValue} are allowed).
			\xmlitemd[``Clamp''] If present, clamping is applied according to:
				\begin{equation}
					\mathrm{MIN}(\texttt{maxOutValue}, \mathrm{MAX}( \texttt{minOutValue}, RGB_{out} ))
				\end{equation}
		\end{xmlfields}
\end{xmlfields}

The range between \texttt{minInValue} and \texttt{maxInValue} is scaled to the \texttt{minOutValue} and \texttt{maxOutValue} range using the following equation:
\begin{align*}
	scale &= \dfrac{(\texttt{maxOutValue} - \texttt{minOutValue})}{(\texttt{maxInValue} - \texttt{minInValue})} \\
	RGB_{out} &= RGB_{in} \times scale + \texttt{minOutValue} - \texttt{minInValue} \times scale \\
	RGB_{out_{clamped}} &= \mathrm{MIN}(\texttt{maxOutValue}, \mathrm{MAX}( \texttt{minOutValue}, RGB_{out}))
\end{align*}

If the input and output bit depths are not the same, a conversion should take place using the range elements. If the elements defining an \texttt{InValue} range or \texttt{OutValue} range are not provided, then the default behavior is to use the full range available with the \texttt{inBitDepth} or \texttt{outBitDepth} attribute used in place of the missing input range or missing output range, respectively, as calculated with these equations:

In the formulae below, if the bit depth is integral, then rangescalar() is defined as:
	\begin{equation}
	 	\mathrm{rangescalar}( bitDepthInteger ) = 2^{bitDepth} - 1
	\end{equation}
If the bit depth is specified as floating point, then:
	\begin{equation}
		\mathrm{rangescalar}( float ) = 1.0
	\end{equation}

If only minimum values are specified, the formula is:
	\begin{align*}
		scale &= \dfrac{\mathrm{rangescalar}(outBitDepth)}{\mathrm{rangescalar}(inBitDepth)} \\
		RGB_{out} &= \mathrm{MAX}( \texttt{minOutValue}, RGB_{in} \times scale + \texttt{minOutValue} - \texttt{minInValue} \times scale)
	\end{align*}

If only maximum values are specified, the formula is:
	\begin{align*}
		scale &= \dfrac{\mathrm{rangescalar}(outBitDepth)}{\mathrm{rangescalar}(inBitDepth)} \\
		RGB_{out} &= \mathrm{MIN}( \texttt{maxOutValue}, RGB_{in} \times scale + \texttt{maxOutValue} - \texttt{maxInValue} \times scale)
	\end{align*}

\subsection{\texttt{ASC\_CDL} (substitute for \texttt{ProcessNode})}
This node contains the parameters for processing pixels using the ASC CDL color correction equations. The ASC CDL equations are designed to work on an input domain of floating-point values of [0 to 1.0] although values greater than 1.0 can be present. The output data may or may not be clamped depending on the processing configuration below.

Attributes:
\begin{xmlfields}
	\xmlitem[id][optional] This should match the id attribute of the ColorCorrection element in the ASC CDL XML format.
	\xmlitem[style][optional] Determines the formula applied by the operator. The valid options are:
		\begin{xmlfields}
			\xmlitemd["Fwd"] implementation of v1.2 ASC CDL equation
			\xmlitemd["Rev"] inverse equation
			\xmlitemd["FwdNoClamp"] similar to the \texttt{Fwd} equation, but without clamping
			\xmlitemd["RevNoClamp"] inverse equation
		\end{xmlfields}
		The first two implement the math provided in version 1.2 of the ASC CDL specification.  The second two omit the clamping step and are intended to provide compatibility with the many applications that take that alternative approach.
\end{xmlfields}

Elements:
\begin{xmlfields}
	\xmlitem[SOPNode][optional] The \texttt{SOPNode} is optional, but if present, must contain one each of the following sub-elements:
	\begin{xmlfields}
		\xmlitemd[Slope] If not provided, the default is 1.0 for all channels.
		\xmlitemd[Offset] If not provided, the default is 0.0 for all channels.
		\xmlitemd[Power] If not provided, the default is 1.0 for all channels.
	\end{xmlfields}
	\xmlitem[SatNode][optional] The \texttt{SatNode} is optional, but if present, must contain one of the following sub-element:
	\begin{xmlfields}
		\xmlitemd[Saturation] If not provided, the default is 1.0 for all channels.
	\end{xmlfields}
\end{xmlfields}

\note{The structure of this \texttt{ProcessNode} matches the structure of the XML format described in the v1.2 ASC CDL specification. However, unlike the ASC CDL XML format, there are no alternate spellings allowed for these elements.}

The math for \texttt{style="Fwd"} is:
	\begin{align*}
		SAT_{in} &= \mathrm{clamp}(RGB_{in} \times slope + offset)^{power} \\
		luma &= 0.2126 * SAT_{in_R} + 0.7152 * SAT_{in_G} + 0.0722 * SAT_{in_B} \\
		RGB_{out} &= \mathrm{clamp}(luma + saturation * (SAT_{in} - luma))
	\end{align*}

where clamp() clamps the argument to [0,1].

The math for \texttt{style="FwdNoClamp"} is the same as for \texttt{"Fwd"} but the two clamp() functions are omitted. Also, if $(input * slope + offset) < 0$, then no power function is applied.

The math for \texttt{style="Rev"} is:
	\begin{align*}
		RGB_{in_{clamp}} &= \mathrm{clamp}(RGB_{in}) \\
		luma &= 0.2126 * R_{in_{clamp}} + 0.7152 * G_{in_{clamp}} + 0.0722 * B_{in_{clamp}} \\
		RGB_{sat_{out}} &= luma + \frac{1}{saturation} * (RGB_{in_{clamp}} - luma) \\
		RGB_{out} &= \mathrm{clamp}\left(\frac{\mathrm{clamp}(RGB_{sat_{out}})^{\frac{1}{power}} - offset}{slope}\right) \\
	\end{align*}

The math for \texttt{style="RevNoClamp"} is the same as for \texttt{"Rev"} but the two clamp() functions are omitted. Also, if $RGB_{sat_{out}} < 0$, then no power function is applied.

\note{The equations above assume that the input and output bit depths are floating-point. For integer inputs and outputs, the values must be normalized to or from [0.0, 1.0] scaling. In other words, the slope, offset, power, and saturation values stored in the \texttt{ProcessNode} do not depend on \texttt{inBitDepth} and \texttt{outBitDepth} they are always interpreted as if the bit depths were float.}

\section{\texttt{IndexMap} element} \label{sec:indexmap}
This element defines a list that is a new mapping of input code values, $inValues$, to index positions, $n$, in a LUT's \texttt{Array}. The format of each item in the list is $newInValue\mathrm{@}n$. For example, the first \texttt{IndexMap} item might be $64\mathrm{@}0$ which assigns the $inValue=64.0$ to position $0$ in the LUT.

In its simplest form, with a \texttt{dim=2}, this element can be used to define the input floating point range that will be used by the LUT.

An extension to the LUT format described in Appendix \ref{appendixC}.

Attributes:
\begin{xmlfields}
	\xmlitem[dim][required] Field that specifies the number of items in the list.
\end{xmlfields}

\section{\texttt{Array} element}
This element contains the table entries of a LUT in order from minimum value to maximum value with a single line for each color component triple.  The \texttt{dim} attribute specifies the dimensions of the cube, the length of the LUT, or the size of the array.

The \texttt{dim} attribute and the type of node should match.

Attributes:
\begin{xmlfields}
	\xmlitem[dim][required] 	Specifies the dimension of the LUT or the matrix and the number of components. The data points for a \texttt{ProcessNode} are contained in an XML array element. The \texttt{dim} attribute provides the dimensionality of the indexes, where:

		4 entries have the dimensions of a 3D cube plus the number of components per entry.
		\begin{list}{}{\setlength{\itemsep}{4pt}\setlength{\topsep}{0pt}}
				\item e.g. \texttt{dim = 17 17 17 3 } indicates a 17-cubed 3D lookup table with 3 component color
		\end{list}

		3 entries have the matrix dimensions and component value.
		\begin{list}{}{\setlength{\itemsep}{4pt}\setlength{\topsep}{0pt}}
				\item e.g. \texttt{dim = 3 3 3 } is a 3 by 3 matrix acting on 3-component values
				\item e.g. \texttt{dim = 3 4 3 } is a 3 by 4 matrix acting on 3-component values
		\end{list}

		2 entries have the length of the LUT and the component value (1 or 3).
		\begin{list}{}{\setlength{\itemsep}{4pt}\setlength{\topsep}{0pt}}
				\item e.g. \texttt{dim = 256 3 } indicates a 256 element 1D LUT with 3 components (a 3by1DLUT)
				\item e.g. \texttt{dim = 256 1 } indicates a 256 element 1D LUT with 1 component (1DLUT)
		\end{list}
\end{xmlfields}

ext: tex

max_stars_repo_name: KelSolaar/aces-dev

max_issues_repo_name: colour-science/aces-dev

max_forks_repo_name: colour-science/aces-dev


text:
%THIS SECTION IS LIKELY TO DISAPPEAR
\section{Philosophy}
For thoughts.

\subsection{Decline in violence, Human Nature and a Bright Future}
I've a good feeling about the future. The more I travel, the more people I know, the more I study... I cannot feel that the world is getting better and that are many factors are steering it in that direction.

In the Summer of 2019 I did a 2400 km, 14 days bike travel from the Netherlands to Portugal which, from my experience is far more than anyone that will read this (apart from myself in the future, of course). During that trip I met people that have travelled far more and in far more adventurous ways. So I believe it is safe to assume that I collected knowledge from people with enough experience of the world.

From this experience, some a ground-truth could be extracted: if there are people around, you will be okay. From a guy that spent 3 days walking in the snowy mountains without eating to a guy that travelled more than 50 countries before he was 30, all of them have the same experience: people seem innately good.

Steven Pinker's book `The Better Angles of our Nature - How Violence has declined' takes a very good look at why the world is going in the correct direction, at least in terms of violence, sympathy, kindness, fairness, etc\dots

Therefore, this big topic will be separated in the technological advances, completely from my own head, and a Steven Pinker inspired analysis.

\subsubsection{How Technology is making the world a better place}
Technology seems to be able to more efficiently provide for humans. Imagine that we reach a point where there are so many solar panels and so many dams to store electricity naturally and so many means of electricity transportation that everyone is capable of having enough electricity. Since technology is allowing everything to become electric, if everyone has electricity it seems common sense that everyone will have enough to satisfy their needs.

And with regards to food? Well, enough electricity would allow environment manipulation inside a greenhouse to grow whatever in whatever climate. Moreover, is surely must be possible to create and monitor a sustainable natural cycle where Earth can survive for very long.

This scales very well since if people are not worried about food or survival, they can contribute as much as they can to human development.

From my math, we still have a couple of million years before sun explodes and I'm quite sure at this rate that we won't need more than a 200 to start living in other planets.

\subsubsection{The Better Angles of our Nature}

Violence is declining at an unthinkable rate. Steven evidences 6 historical eras where that happened, ............ and 5 (or so) biological treats that lead us to cooperation and altruism.

\subsection{Write. It's important}

Jordan Peterson writes well, thinks well and seems to have quite a bit to teach.
One thing certainly is not arguable about him, he knows how to get his points across and defends his arguments ferociously well.

We wrote \href{https://www.jordanbpeterson.com/docs/230/2014/Papers%20from%20previous%20years/Mar.pdf}{\ul{The Benefits of Writing: Health
and Productivity}}, which is the basis for the \href{https://www.selfauthoring.com/}{\a¢{Self Authoring Programme}} - a programme I hope to follow \ii{eventually}.

Additionally, his \href{https://docs.google.com/viewer?url=http://jordanbpeterson.com/wp-content/uploads/2018/02/Essay_Writing_Guide.docx}{\ul{Easy Writing Guide}} is the closest he has written to a experience compendium. Truly a valuable resource from his authorship.

There are far too many important things in the links above to write a summary about them. It wouldn't be a summary, more like a less complete copy.

As such, I plan to know how to write properly, construct solid arguments and to report any revolutionary findings here.

max_stars_repo_name: jmoraispk/TheDocument

max_issues_repo_name: jmoraispk/TheDocument

max_forks_repo_name: jmoraispk/TheDocument


text:
% language=uk

\startcomponent introduction

\environment mk-environment

\chapter{Introduction}

In this document I will keep track of the transition of \CONTEXT\
from \MKII\ to \MKIV, the latter being the \LUA\ aware version.

The development of \LUATEX\ started with a few email exchanges
between me and Hartmut Henkel. I had played a bit with \LUA\ in
\SCITE\ and somehow felt that it would fit into \TEX\ quite well.
Hartmut made me a version of \PDFTEX\ which provided a \type
{\lua} command. After exploring this road a bit Taco Hoek\-water
took over and we quickly reached a point where the \PDFTEX\
development team could agree on following this road to the future.

The development was boosted by a substantial grant from Colorado
State University in the context of the Oriental \TEX\ Project of
Idris Samawi Hamid. This project aims at bringing features into
\TEX\ that will permit \CONTEXT\ to do high quality Arabic
typesetting. Due to this grant Taco could spent substantial time
on development, which in turn meant that I could start playing
with more advanced features.

This document is not so much a users manual as a history
of the development. Consider it a collection of articles, and some
chapters indeed have ended up in the journals of user groups. Things
may evolve and the way things are done may change, but it felt right
to keep track of the process this way. Keep in mind that some features
may have changed while \LUATEX\ matured.

Just for the record: development in the \LUATEX\ project is done
by Taco Hoekwater, Hartmut Henkel and Hans Hagen. Eventually, the
stable versions will become \PDFTEX\ version~2 and other members
of the \PDFTEX\ team will be involved in development and
maintenance. In order to prevent problems due to new and maybe
even slightly incompatible features, \PDFTEX\ version~1 will be kept
around as well, but no fundamentally new features will be added to
it. For practical reasons we use \LUATEX\ as the name of the
development version but also for \PDFTEX~2. That way we can use
both engines side by side.

This document is also one of our test cases. Here we use traditional
\TEX\ fonts (for math), \TYPEONE\ and \OPENTYPE\ fonts. We use color
and include test code. Taco and I always test new versions of
\LUATEX\ (the program) and \MKIV\ (the macros and \LUA\ code) with
this document before a new version is released. It also means that
there can be temporary flaws in the rendering. Keep tuned,

\blank

Hans Hagen, Hasselt NL,\crlf August 2006\endash\currentdate[year]

\blank

\type {http://www.luatex.org}

\stopcomponent


text:
\documentclass[12pt, letterpaper]{article}
\usepackage[hyphens]{url}
\setlength{\topmargin}{-1.75cm} \setlength{\textheight}{22.5cm}
\setlength{\oddsidemargin}{0.25cm}
\setlength{\evensidemargin}{0.25cm} \setlength{\textwidth}{16.2cm}
\renewcommand{\figurename}{Figure}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{xcolor}
\usepackage[normalem]{ulem}
\usepackage{fontenc}
\usepackage{footnote}
\usepackage[breaklinks]{hyperref}
\usepackage{palatino, multicol, listings} % for multiple columns
\lstset{mathescape=true, basicstyle=\ttfamily,}

%\usepackage{pictex}
%% in the .pictex output of xfig, there is command \colo
%% however the old version of pictex may not define this
%% so we define color here as empty
%\def \color#1]#2{}

\begin{document}

\newcommand{\hide}[1]{}
\newcommand{\exercise}[1]{}
\newcommand{\future}[1]{}
\newcommand{\otherquestions}[1]{}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\pg}[1]{{\tt #1}}
\newtheorem{definition}{Definition}
\newcommand{\emptyclause}{\Box}
\def\st{\bigskip\noindent}
\newcommand{\lplus}
{
   \stackrel{+}{\gets}
}

\newcommand{\fe}[1] {
  \begin{frame}
    #1
  \end{frame}}

\newcommand{\eoa}{ {\bf End} of algorithm}

\newcommand{\ft}[1] {\frametitle{#1}}

\newcommand{\ie}[1] {
  \begin{itemize}
    #1
  \end{itemize}
}

\newcommand{\ee}[1] {
  \begin{enumerate}
    #1
  \end{enumerate}\label{marker}
}
\newcommand{\blk}[2] {
  \begin{block}{#1}
    #2
  \end{block}
}

\newtheorem{collorary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{invariant}{Invariant}
\newtheorem{property}{Property}
\newtheorem{claim}{Claim}
\newtheorem{example}{Example}

\title{${\cal SPARC}$ manual}
\date{\today}
\maketitle
\tableofcontents
\pagebreak

\section{System installation}

\st For using the system, you need to have the following installed:
\begin{enumerate}
\item Java Runtime Environment (JRE) can be found at \\
{\scriptsize
\url{http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads-2133155.html}
}.\\
Java versions 1.8.0\_181 or higher is required.
\item The SPARC to ASP translator. It can be downloaded at \\
{\scriptsize
\url{https://github.com/iensen/sparc/blob/master/sparc.jar?raw=true}
}.
\item An ASP solver. It can be one of the following:
  \begin{enumerate}
  \item Clingo (recommended)  {\scriptsize
 \url{https://github.com/potassco/clingo/releases}
}.
\item DLV
{\scriptsize
 \url{http://www.dlvsystem.com/dlv/#1}
}. You need to download the \textit{static} version of the executable file.

\end{enumerate}

\item (\textit{optional}) Swi-Prolog. {\scriptsize \url{http://www.swi-prolog.org/}}. This item is only required if option \textit{-wcon} is used for type warning detection.
(See sections \ref{option} and \ref{clp_type_warnings}).

\end{enumerate}
If you are using the dlv solver, rename the solver executable file to \textit{dlv} (\textit{dlv.exe} for windows).

Be sure the PATH system variable includes the directory where the solver executable is located. For instructions on how to view/modify the PATH system variable, see either of the following links:\\
{\scriptsize
\url{http://www.java.com/en/download/help/path.xml}\\
\url{http://www.cyberciti.biz/faq/appleosx-bash-unix-change-set-path-environment-variable/}\\
}
To check if the solver is installed correctly, run the command \texttt{dlv -v} (for dlv) or \\ \texttt{clingo -v} (for clingo). See figures \ref{fig:dlv_solver_check} for dlv and \ref{fig:clingo_solver_check} for clingo for examples of the expected output.

\begin{figure}[p]
\centering
\includegraphics[width=0.9\textwidth]{dlv_version.jpg}
\caption{Checking the version of DLV solver}
\label{fig:dlv_solver_check}
\end{figure}

\begin{figure}[p]
\centering
\includegraphics[width=0.9\textwidth]{clingo_version.jpg}
\caption{Checking the version of Clingo solver}
\label{fig:clingo_solver_check}
\end{figure}

\section{System usage}

To demonstrate the usage of the system we will use the program $\Pi$ below.
\begin{verbatim}
sorts
#person={bob,tim,andy}.
predicates
teacher(#person).
rules
teacher(bob).
\end{verbatim}

\st
The system can work in one of the  two modes: \textit{querying mode} and \textit{answer set mode}.

\subsection{Querying mode}

In this mode we can ask queries about a ${\cal SPARC}$ program loaded into the system.
The general command line syntax for this mode is \textit{java -jar sparc.jar program\_file}.
Queries in ${\cal SPARC}$ are positive or negative literals of the forms $p(t1,t2,\dots,tn)$ or
$-p(t1,t2,\dots,tn)$ correspondingly, where $p(t1,t2,\dots,tn)$  is an atom of the loaded program $\Pi$
( note that \textit{n} can be equal to zero, in this case the query will be of the form \textit{p} or \textit{-p}  ).

The queries are answered as follows:
\ie{
\item The answer to a query $l$ not containing variables is \textit{yes}, if $l$(with all arithmetic expressions evaluated) belongs to all answer sets of  $\Pi$.
\item The answer to a query $l$ not containing variables is \textit{no}, if $-l$(with double classical negation removed and all arithmetic expressions evaluated) belongs to all answer sets of  $\Pi$.
\item The answer to a query $l$ not containing variables is \textit{unknown}, if it is not \textit{yes} or \textit{no}.
\item The answer to a query of the form $l$($l$ is an atom of the form $p(t1, \dots, tn)$  possibly preceeded by a negation sign)  is  a collection of assignments $X_1 = t_1, \dots, X_n=t_n$,
where $X_1, \dots, X_n$ are all variables in $p(t1, \dots, tn)$, $t_1, \dots, t_n$ are ground terms, and the answer to the query $p(t1',\dots,tn')$, obtained from  $p(t1, \dots, tn)$ by replacing each variable $X_i$ by a ground term $t_i$, is \textit{yes}.

}

To run  ${\cal SPARC}$  on the program above,
we change current directory to a directory having the file \texttt{program.sp} with the program written in it, and the downloaded file \texttt{sparc.jar}.  Then, we run the command:
\begin{verbatim}
username@machine:~$ java -jar sparc.jar program.sp
SPARC  V2.25
program translated
?- teacher(bob).
yes
?- teacher(tim).
unknown
?- teacher(X).
X = bob
?- teacher(john).
program.sp: argument number 1 of predicate teacher/1, "john",
            violates definition of sort "person"
?-exit.
\end{verbatim}

The answer to the first query \texttt{?- teacher(bob)} is \textit{yes}, because the atom \textit{teacher(bob)} belongs to the only answer set of $\Pi$.

The answer to the second query \texttt{?- teacher(tim)} is \textit{unknown}, because neither the atom \textit{teacher(bob)} nor its negation belongs to the answer set of $\Pi$.

The answer to the query \texttt{?- teacher(X)} is \textit{X = bob}, because there is only one replacement (bob) for X, such that \textit{teacher(X)} belongs to the answer set of $\Pi$.

For the fourth query, we see an error, because teacher(john) is not an atom of $\Pi$.

To quit the querying engine, use \textbf{exit} command.

\subsection{Answer Set Mode}

In this mode we can see the computed answer sets of the loaded program.
The general command line syntax for this mode is \textit{java -jar sparc.jar program\_file -A}.

For the program $\Pi$, the answer set may be computed as it is shown below:
\begin{verbatim}
username@machine:~$ java -jar sparc.jar program.sp -A
SPARC  V2.25
program translated
DLV [build BEN/Dec 16 2012   gcc 4.6.1]
{teacher(bob)}

\end{verbatim}

\section{Command Line Options}\label{option}

In this section we  describe the meanings of command line options supported by
${\cal SPARC}$. Some options(flags) do not take an argument and have the form \textit{-option},
while others require arguments and can be written in the form \textit{-option arg}.
For each command line option, we indicate whether it requires
an argument, and if so, we  describe its meaning.

\begin{itemize}
 \item \textbf{-A}

  Compute answer sets of the loaded program.

\item \textbf{-wcon}

  Show warnings determined by CLP-based algorithm. See section \ref{clp_type_warnings}

\item \textbf{-wasp}
  \footnote{\textcolor{red}{This option is temporarily broken, use -wcon instead}}
  Show warnings determined by ASP-based algorithm. See section \ref{asp_type_warnings}

\item \textbf{-solver arg}
  Specify the solver which will be used for computing answer sets. \textit{arg} can have two possible values: \textit{dlv} and \textit{clingo}.
\item \textcolor{red}{(\textbf{new!})} \textbf{-n [number]}

  Specify how many answer sets need to be displayed. This option can only be used with option -A.

  Examples:
  \begin{itemize}
  \item[$\bullet$] \texttt{-n 2} will display two arbitrary answer sets. In case the program has less than two answer sets, all of them will be shown.
  \item[$\bullet$] \texttt{-n 0} will display all the answer sets.
    \end{itemize}

\item \textbf{-Help, -H, -help, --Help, --help, -h}

  Show help message.

\item \textbf{-o arg}

  Specify the output file where the translated ASP program will be written. \textit{arg} is the path to the output file.
  Note that if the option is not specified, the translated ASP program will not be stored anywhere.

\item \textbf{input\_file}

Specify the file where the sparc program is located.

\end{itemize}

\section{Syntax Description}

\subsection{Directives}
Directives should be written before sort definitions, at the very beginning of a program.
${\cal SPARC}$ allows two types of directives:
\subsection*{\#maxint}
Directive \#maxint specifies the maximum nonnegative number that could be used in arithmetic calculations. For example,
\begin{verbatim}
 #maxint=15.
\end{verbatim}
\st limits integers to [0,15].
\subsection*{\#const}
Directive \#const allows one to define constant values. The syntax is:

\begin{verbatim}
   #const constantName = constantValue.
\end{verbatim}
\st where $constantName$  must begin with a lowercase letter and may be composed of letters, underscores and digits,
 and $constantValue$ is either a nonnegative number or the name of another constant defined before it.

\subsection{Sort definitions}\label{ss}

This section starts with a keyword $sorts$ followed by a collection of sort definitions of the form:

\begin{equation*}
  sort\_name=sort\_expression.
\end{equation*}
\textit{sort\_name} is an identifier preceeded by the pound sign (\#).
\textit{sort\_expression}  on the right hand side denotes a collection of strings called  $a~sort$. We divide all the sorts into \textit{basic sorts} and \textit{non-basic sorts}.

\st \textit{Basic sorts} are defined as named collections of numbers and \textit{identifiers}, i.e, strings consisting of

\begin{itemize}

 \item letters: $\{a,b,c,d,...,z,A,B,C,D,...,Z\}$

 \item digits: $\{0,1,2,...,9\}$

 \item underscore: $\_$

\end{itemize}

and starting with a lowercase letter.

A \textit{non-basic sort} also contains at least one \textit{record} of the form $id(\alpha_1,\dots, \alpha_n)$ where $id$ is an identifier and

$\alpha_1, \dots, \alpha_n$ are either identifiers, numbers or records.

\st We define sorts by means of expressions (in what follows sometimes referred to as statements) of six types:
\begin{enumerate}

\item
\textbf{numeric range} is of the form:
\begin{equation*}
number_1..number_2
\end{equation*}
where $number_1$ and $number_2$ are non-negative numbers such that $number_1 \le number_2$. The expression defines the set

of sequential numbers \\$\{number_1, number_1+1, \dots, number_2\}$.

\textit{Example:}

\begin{verbatim}

 #sort1=1..3.

\end{verbatim}

\texttt{\#sort1} consists of numbers $\{1,2,3\}$.

\item \textbf{identifier range} is of the form:

\begin{equation*}
  id_1..id_2
\end{equation*}

where $id_1$ and $id_2$ are identifiers both starting with a lowercase letter.

$id_1$ should be lexicographically \footnote{ The system default encoding is used for  ordering of individual characters} smaller than or equal to  $id_2$, and the length of $id_1$ must be less than or equal to the length of $id_2$. That is,  $id_1 \leq id_2$ and $|id_1| \leq |id_2|$.

The expression defines the set of strings  $\{s: id_1\leq s \leq id_2 \land |id_1|\leq |s| \leq |id_2|\}$.
\textit{Example:}

\begin{verbatim}
 #sort1=a..f.
\end{verbatim}

\texttt{\#sort1} consists of letters $\{a,b,c,d,e,f\}$.

\item \textbf{set of ground terms} is of the form:

\begin{equation*}
\{t_1,..,,t_n\}
\end{equation*}
The expression denotes a set of \textit{ground terms} $\{t_1,...,t_n\}$, defined as follows:
\begin{itemize}
 \item numbers and identifiers are ground terms;
 \item If $f$ is an identifier and $\alpha_1, \dots, \alpha_n$ are ground terms,
then $f(\alpha_1,\dots, \alpha_n)$ is a ground term.
\end{itemize}

\textit{Example}:
\begin{verbatim}
 #sort1={f(a),a,b,2}.
\end{verbatim}
\item \textbf{set of records} is of the form:

\begin{equation*}
f(sort\_name_1(var_1),..., sort\_name_n(var_n)):
                                     condition(var_1,...,var_n)
\end{equation*}
where $f$ is an identifier, for $ 1\leq i\leq n$, $sort\_name_i$ occurs in one of the preceeding sort definitions and a \textit{condition} on variables $var_1,...,var_n$ (written as $condition(var_1,...,var_n)$) is defined as follows:

\begin{itemize}
\item if $var_i$ and $var_j$ occur in the sequence  $var_1,...,var_n$ and $\odot$ is an element of $\{>,<,\le,\ge\}$, then $var_i \odot var_j$ is a \textit{condition} on   $var_1,...,var_n$.
\item if $\mathcal{C}_1$ and $\mathcal{C}_2$ are both conditions on  $var_1,...,var_n$, and $\oplus$ is an element of  $\{\cup,\cap\}$, then
$(\mathcal{C}_1 \oplus \mathcal{C}_2)$ is a \textit{condition} on  $var_1,...,var_n$.
\item if $\mathcal{C}$ is a  condition on  $var_1,...,var_n$, then $not(\mathcal{C})$ is also a \textit{condition} on  $var_1,...,var_n$.
\end{itemize}
Variables $var_1,...,var_n$ occurring in parenthesis after sort names are optional as well as the condition :$condition(var_1,...,var_n)$.

If a condition contains a subcondition $var_i~\odot~var_j$,  then the sorts  $sortname_i$ and  $sortname_j$ must be defined by basic statements (the definition of which is given below after the definition of a concatenation statement).

The expression defines a collection of ground terms
\\ $\{f(t_1,\dots,t_n):  t_1 \in s_i \land \dots \land t_n \in s_n \land (condition(X_1,\dots, X_n)|_{X_1 = t_1,\dots,X_n = t_n})\}$

\textit{Example}
\begin{verbatim}
 #s=1..2.
 #sf=f(#s(X),#s(Y),#s(Z)): (X=Y or Y=Z).
\end{verbatim}

The sort \texttt{\#sf} consists of records $\{f(1,1,2),f(1,1,1),f(2,1,1)\}$

 \item \textbf{set-theoretic expression} is in one of the following forms:
\begin{itemize}
\item $\#sort\_name$
\item an expression of the form 3, denoting a set of ground terms
\item an expression of the form 4, denoting a set of records
\item $(S_1 \bigtriangledown S_2)$, where $\bigtriangledown \in \{+,-,*\}$ and both $S_1$ and $S_2$ are set theoretic expressions
\end{itemize}

$\#sort\_name$ must be a name of a sort occurring in one of the preceeding sort definitions.
The operations $+$ $*$ and $-$ stand for union, intersection and difference correspondingly.

\textit{Example} :
\begin{verbatim}
 #sort1={a,b,2}.
 #sort2={1,2,3} + {a,b,f(c)} + f(#sort1).
\end{verbatim}
 \texttt{\#sort2} consists of ground terms $\{1,2,3,a,b,f(c),f(a),f(b),f(2)\}$.
\item \textbf{concatenation} is of the form
\begin{equation*}
 [b\_stmt_1] ... [b\_stmt_n]
\end{equation*}

$b\_stmt_1, \dots, b\_stmt_n$ must be \textit{basic statements}, defined as follows:

\begin{itemize}
 \item statements of the forms 1 to 3 are basic
 \item statement $S$ of the form 5 is basic if:
 \begin{itemize}
 \item it does not contain sort expressions of the form 4, denoting sets of records,
  \item there is no records between any pair of matching curly brackets,
  \item all sorts occurring in $S$ are defined by basic statements .
 \end{itemize}
\end{itemize}
Note that basic statement can only define a basic sort.

\textit{Example\footnote{We allow a shorthand `b` for singleton  set \{b\}}.:}

\begin{verbatim}
 #sort1=[b][1..100].
\end{verbatim}

\texttt{sort1} consists of identifiers $\{b1,b2,\dots, b100\}$.

\end{enumerate}
\subsection{Predicate Declarations}

\noindent  The second part of a  ${\cal SPARC}$ program starts with the keyword
$predicates$ and is followed by statements of the form

\begin{equation*}
pred\_symbol(\#sortName_1,\dots,\#sortName_n)
\end{equation*}
\st

Where $pred\_symbol$ is an identifier (in what follows referred to as a predicate symbol) and  $\#sortName_1$,\dots,$\#sortName_n$ are sorts defined in sort definitions section of the program.

Multiple declarations containing the same predicate symbol are not allowed.
0-arity predicates must be declared as $pred\_symbol()$.
\st For any sort name $\#s$, the system includes declaration  $\#s(\#s)$ automatically.

\subsection{Program Rules}
\st The third part of a ${\cal SPARC}$ program starts with the keyword \textit{rules} followed by standard ASP rules(supported by the specified ASP solver
\footnote{Currently, only DLV solver is fully supported(excluding \#import directives). Clingo's choice rules and minimize statements will be added later})
, possibly enchanced by arithmetic expressions of arbitrary depth (e.g, p(X*X*X*X+1).) and/or consistency restoring (cr)-rules.
\st
CR-rules are of the following form:

\begin{equation}
   [label:] l_0 \lplus l_1,  \ldots, l_k, not~l_{k+1} \ldots not~l_{n}.
 \end{equation}
where $l$'s are literals.
Literals occurring in the heads of the rules must not be formed by predicate symbols
occurring as sort names in sort definitions. In addition, rules must not contain \textit{unrestricted variables}.

\begin{definition}(Unrestricted Variable)
 A variable occurrung in a rule of a ${\cal SPARC}$ program is called unrestriced if all its occurrences in the rule either belong to some relational atoms of the form
$term1$ \textbf{rel} $term2$ (where \textbf{rel} $\in  \{>,>=,<,<=,=,!=$\})  and/or  some term appearing in a head of a choice or aggregate element.
\end{definition}
\begin{example}
\em{
 Consider the following ${\cal SPARC}$ program:
\begin{verbatim}
sorts
#s={f(a),b}.
predicates
p(#s).
rules
p(f(X)):-Y<2,2=Z,F>3,#count{Q:Q<W,p(W),T<2},p(Y).
\end{verbatim}
Variables F,T,Z,Q are unrestricted.
}
\end{example}

\subsection{Display \textit{\textcolor{red}{(New!)}}}

\medskip\noindent
The last (optional) section of the program starts from the keyword \texttt{display} and is followed by a collection of literals of the program.
Every literal is followed by a dot symbol ('.').

\medskip\noindent
The section defines which literals are included into the output of answer sets computed in answer set mode (section 2.2). A ground literal is included into the output if and only if it is unifiable with one of the literals from the display section of the program.

\medskip\noindent
\textbf{If the display section is not present, the output contains all the literals formed by all the predicates of the program.}

\medskip\noindent
For example, consider the program:

\begin{verbatim}
sorts
#s = {a,b,c,f(a),f(b)}.
predicates
p(#s).
q().
s(#s).
rules
s(a):- #s(b).
s(a) :- #s(b).
-q:- #s(a).
p(a) :- -q.
-p(b).
p(f(a)).
-p(f(b)).
display
-q.
-p(f(X)).
p(X).
#s.

\end{verbatim}

\medskip\noindent
The program has one answer set, and the following literals are shown in the output:

\begin{verbatim}
{-q, -p(f(b)), p(a), p(f(a)), #s(a), #s(b), #s(c),
 #s(f(a)), #s(f(b))}
\end{verbatim}

\medskip\noindent
Note that, for example, \texttt{p(b)} is not shown because it is not unifiable with any of the literals in the display section.

\medskip\noindent
If the display section is removed from the program, the output is as follows:

\begin{verbatim}
{s(a), -q, p(a), p(f(a)), -p(b), -p(f(b))}
\end{verbatim}

\medskip\noindent
Note that, when compared to the previous scenario, the literals formed by sort names are not included into the output.

\section{Answer Sets}
\noindent A set of ground literals $S$ is an {\em answer set} of a ${\cal SPARC}$
program $\Pi$ with regular rules only if $S$ is an answer set of an ASP program consisting of the same rules.

\st To define the semantics of a general ${\cal SPARC}$ program, we need notation for abductive support.
By $\alpha(r)$ we denote a regular rule
obtained from a consistency restoring rule $r$
by replacing $\lplus$ by $\leftarrow$;
$\alpha$ is expanded in the standard way to a set $X$ of CR-rules,
i.e., $\alpha(A) = \{\alpha(r)\; :\; r \in A\}$.
\st A %minimal (with respect to the preference relation $\leq$ of the program)
collection $A$ of CR-rules of $\Pi$ such that
\begin{enumerate}
\item $R \cup \alpha(X)$ is consistent (i.e., has an answer set), and
\item any $R_0$ satisfying the above condition has cardinality
which is greater than or equal to that of $R$
\end{enumerate}
is called an {\em abductive support} of $\Pi$.
\st A set of ground literals $S$ is an {\em answer set} of a ${\cal SPARC}$ program
$\Pi$ if $S$ is an answer set of $R \cup \alpha(A)$, where $R$ is the set of regular rules of $\Pi$, for some abductive
support $A$ of $\Pi$.

\st \textbf{Example}
\begin{verbatim}
sorts
#s1={a}.  % term "a" has sort "s1"

predicates
p(#s1).  %predicate  "p" accepts terms of sort s1
q(#s1).  %predicate  "q" accepts terms of sort s1

rules
p(a) :- not q(a).
-p(a).
q(a):+.  % this is a CR-RULE.
\end{verbatim}
\st Result:
\begin{verbatim}
username@machine:~$ java -jar sparc.jar program -A
SPARC  V2.25
program translated
DLV [build BEN/Dec 16 2012   gcc 4.6.1]

Best model: {-p(a), appl(r_0), q(a)}
Cost ([Weight:Level]): <[1:1]>
\end{verbatim}

\st Additional literal $appl(r_0)$ was added to the answer set, which means that the
first cr-rule from the program was applied.

\section{Typechecking}
If no syntax errors are found, a static check of the program is performed. Any type-related problems found during this check are classified into type errors and type warnings.
\subsection{Type errors}
Type errors are considered as serious issues which make it  impossible to compile and execute the program.
Type errors can occur in all four sections of a ${\cal SPARC}$ program.
\subsubsection{Sort definition errors}
The following are possible causes of a sort definition error  that will result in a type error  message from ${\cal SPARC}$:
\begin{enumerate}
\item  A set-theoretic expression (statement 5 in section \ref{ss}) containing a sort name that has not been defined.

\textit{Example:}
\begin{verbatim}
 sorts
 #s={a}.
 #s2=#s1-#s.
\end{verbatim}

\item  Declaring a sort more than once.

\textit{Example:}
\begin{verbatim}
 sorts
 #s={a}.
 #s={b}.
\end{verbatim}

\item An identifier range $id_1..id_2$ (statement 2 in section \ref{ss}) where $id_1$ is greater than $id_2$.

\textit{Example:}
\begin{verbatim}
 sorts
 #s=zbc..cbz.
\end{verbatim}

\item A numeric range $n_1..n_2$ (statement 1 in section \ref{ss}) where  $n_1$ is greater than $n_2$.

\textit{Example:}
\begin{verbatim}
 sorts
 #s=100500..1.
\end{verbatim}

\item A numeric range (statement 2 in section \ref{ss}) $n_1..n_2$ that  contains an undefined constant.

\textit{Example:}
\begin{verbatim}
 #const n1=5.
 sorts
 #s=n1..n2.
\end{verbatim}

\item An identifier range $id_1..id_2$ (statement 3 in section \ref{ss}) where  the length of $id_1$ is greater than the length of $id_2$.

\textit{Example:}
\begin{verbatim}
 sorts
 #s=abc..a.
\end{verbatim}

\item A concatenation (statement  4 in section \ref{ss}) that contains a non-basic sort.

\textit{Example:}
\begin{verbatim}
 sorts
 #s={f(a)}.
 #sc=[a][#s].
\end{verbatim}

\item A record definition (statement 5 in section \ref{ss}) that contains an undefined sort.

\textit{Example:}
\begin{verbatim}
 sorts
 #s=1..2.
 #fs=f(#s,#s2).
\end{verbatim}

\item A record definition  (statement 5 in section \ref{ss}) that contains a condition with relation $>,<,\geq,\leq$ such that the
   corresponding sorts are not basic.

\textit{Example:}
\begin{verbatim}
#s={a,b}.
#s1=f(#s).
#s2=g(s1(X),s2(Y)):X>Y.
\end{verbatim}

\item  A variable that is used more than once in a record definition (statement  5 in section \ref{ss}).

\textit{Example:}

\begin{verbatim}
 sorts
 #s1={a}.
 #s=f(#s1(X),#s1(X)):(X!=X).
\end{verbatim}
\item A sort that contains an empty collection of ground terms.

\textit{Example}
\begin{verbatim}
 sorts
 #s1={a,b,c}
 #s=#s1-{a,b,c}.
\end{verbatim}
\end{enumerate}
\subsubsection{Predicate declarations errors}

\begin{enumerate}
\item A predicate with the same name is defined more than once.
\textit{Example:}
\begin{verbatim}
 sorts
 #s={a}.
 predicates
 p(#s).
 p(#s,#s).
\end{verbatim}
\item A predicate declaration contains an undefined sort.
\textit{Example:}
\begin{verbatim}
 sorts
 #s={a}.
 predicates
 p(#ss).
\end{verbatim}
\end{enumerate}
\subsubsection{Program rules errors}

In program rules we first check each atom of the form $p(t_1,\dots,t_n)$ and each term occurring in the program $\Pi$ for satisfying
the definitions of program atom and program term correspondingly\cite{sparc}. Moreover, we check that no sort occurs in a head of a rule of $\Pi$.
\subsection{Type warnings}\label{type_warnings}
During this phase each rule in input ${\cal SPARC}$ program is checked for having at least one ground instance. Warnings are reported if no ground instance for a ${\cal SPARC}$ rule was found.  Two options are available:
\begin{itemize}
\item \texttt{-wcon}: find warnings using  constraint solver algorithm described in \cite{sparc}.
\item \texttt{-wasp}: find warnings using ASP-based algorithm.
\end{itemize}

While both algorithms are intended to produce same results, their execution time may vary. We recommend using constraint solver based option for programs involving many arithmetic terms and numeric sorts and ASP-based checker for programs with many deeply-nested records and symbolic terms.

\subsubsection{ASP based warning checking} \label{asp_type_warnings}
The option \texttt{-wasp} should be passed to the  system  to detect and display warnings using a simple ASP based algorithm.
For example, consider the ${\cal SPARC}$ program below.

\begin{verbatim}
sorts
#s1={a}.
#s2=f(#s1).
#s3={b}.

predicates
p(#s2).
q(#s3).

rules
p(f(X)):-q(X).
\end{verbatim}

The only rule of the program has no ground instances with respect to defined sorts.
The execution trace is provided below
\begin{verbatim}
username@machine:~$ java -jar sparc.jar program.sp -A -wasp
                             -solveropts "-pfilter=warning"
SPARC  V2.29.5
program translated
DLV [build BEN/Dec 16 2012   gcc 4.6.1]
{ warning("p(f(X)):-q(X). ( line: 11, column: 1)")}
\end{verbatim}

The atom \texttt{warning("p(f(X)):-q(X). ( line: 11, column: 1)")} is included into the answer set as an indicator of potential problem.

In general, when the \texttt{-wasp} is passed to ${\cal SPARC}$ system, each answer set will contain
\begin{verbatim}
warning("rule description")
\end{verbatim}
for each rule which has no ground instances\footnote{in current version, aggregates are skipped by this algorithm} and
\begin{verbatim}
has_ground_instance("rule description")
\end{verbatim}
\st
for all other rules of the input program.
\subsubsection{Constraint solver based warning checking}\label{clp_type_warnings}

The option \texttt{-wcon} must be passed to the  system  in order to detect and display warnings using the algorithm described in \cite{sparc}.
Consider the following ${\cal SPARC}$ program:

\begin{verbatim}
#maxint = 1000.
sorts
#s = 1..1000.
predicates
p(#s).
q(#s).
rules
p(X-600):- q(X+600).
\end{verbatim}

The only rule of the program has no ground instances with respect to defined sorts.
The execution trace is provided below
\begin{verbatim}
username@machine:~$ java -jar sparc.jar program.sp -A -wcon
                                    -solveropts "-pfilter=p"
%WARNING: Rule p(X-600):-q(X+600). at line 8, column 1
is an empty rule
program translated
DLV [build BEN/Dec 16 2012   gcc 4.6.1]
{}
\end{verbatim}

\st The message
\begin{equation*}
\texttt{WARNING: Rule p(f(X)):-q(X). at line 8, column 1 is an empty rule}
\end{equation*}
\st is an indicator of a potential problem.
\pagebreak
\section{${\cal SPARC}$ and ASPIDE}
\subsection{Installation}

For using ${\cal SPARC}$ in ASPIDE, you will need to install ASPIDE(version 1.42 or greater).
The installer is available from {\scriptsize
\url{https://www.mat.unical.it/ricca/aspide/download.html}
}. See the instructions here:  {\scriptsize
\url{https://www.mat.unical.it/ricca/aspide/documentation.html}
}.  Once ASPIDE is installed, go to \textit{File -\textgreater Plug-ins -\textgreater Available plugins} menu,
and press install button in the row containing ${\cal SPARC}$ plug-in (see Fig.\ref{fig:plug_install}).
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{plugin.png}
\caption{Installing ${\cal SPARC}$ plugin}
\label{fig:plug_install}
\end{figure}

\pagebreak
\subsection{Creating Projects and Adding  ${\cal SPARC}$  source files}
ASPIDE uses \textit{workspaces} to store projects. Workspace is a folder that can contain multiple projects. ASPIDE can have only one workspace opened, that is selected by a user when ASPIDE starts. Source files should belong to a project to be used by  ASPIDE query engine and answer set computation tools.

\begin{itemize}
\item To create a new project, go to the menu \textit{File -\textgreater New} and select \textit{New Project} submenu. Specify the project name in the pop-up window and click on \textbf{Finish} button. You should see a new project appeared in \textbf{workspace explorer}.
\item To add a new SPARC file, right click on the project to display context menu and select \textit{New -\textgreater File -\textgreater SPARC File} as it is shown on Figure \ref{fig:createfile} . Choose the file name in the pop-up window. You should see a new file added under the project in workspace explorer and displayed in ASPIDE editor window.
\end{itemize}

\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{project.png}
\caption{Adding  ${\cal SPARC}$ source file }
\label{fig:createfile}
\end{figure}

\subsection{Executing queries and computing Answer sets}
You can execute queries and compute answer sets as for usual ASP file.
To execute a query, open a sparc file in the ASPIDE editor and click on the button with a question mark in the toolbar:
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{openqueries.jpg}
\caption{Open Query Interface}
\label{fig:openqueries}
\end{figure}

A window will appear where you can input and run queries.
To run a query,
\begin{itemize}
\item mark \textbf{Epistemic Mode} checkbox (this is to follow the definition of query given in the class)
\item input your query into editbox named \textbf{Query} or select one from history
\end{itemize}
The results will appear in the listview named \textbf{Results}.
See fig \ref{fig:runquery} for details.
\pagebreak
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{runquery.jpg}
\caption{Execute a query}
\label{fig:runquery}
\end{figure}
\pagebreak

To compute answer sets of the program, press the button with green arrow marked on figure \ref{fig:ansshow}.

\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{toolbarans.jpg}
\caption{Open answer sets window}
\label{fig:ansshow}
\end{figure}

In the appeared \textbf{Run Configurations} window:
\begin{itemize}
\item make sure a correct path to dlv in selected in \textbf{Executable} listbox.
\item press \textbf{Run} button to see the answer sets
\end{itemize}

\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{answindow.jpg}
\caption{Run configurations window}
\label{fig:ansset}
\end{figure}
\pagebreak

In the displayed window, answer sets are grouped by predicate symbols in their literals.
On figure \ref{fig:ansres}, two answer sets are shown. The first one  contains two literals $p(a,b)$ and $p(e,f)$ and some literals with predicate symbol $q$.
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{results.jpg}
\caption{Answer Sets}
\label{fig:ansres}
\end{figure}

\subsection{Warnings Checking}

To see allow ASPIDE to show warnings (section \ref{type_warnings}), you need to install swi-prolog on your system. Swi-prolog is available from  {\scriptsize
\url{http://www.swi-prolog.org/Download.html}
}

After swi-prolog is installed, go to the ASPIDE menu \textit{File -\textgreater Preferences}. In the appeared window select the tab \textbf{Executables/Solvers} and add a new \textit{executable} named \textit{swipl} with a path pointing to the swi-prolog executable. Usually, it is named \textit{swipl} in Unix/MacOS operating system and \textit {swipl.exe} in Windows. Click on \textbf{Save} button to close the window.
See the details on figure \ref{fig:addswipl}.
\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{swipl_add.jpg}
\caption{Adding swi-prolog executable}
\label{fig:addswipl}
\end{figure}
\pagebreak
After the executable is added, you need to specify a flag property for the ${\cal SPARC}$ plug-in to make it check warnings.
Go to ASPIDE menu \textit{File -\textgreater Plug-ins -\textgreater  Manage Plug-ins}. In the appeared window click on the cell Properties in SPARC plug-in line and add a new property \texttt{CHECK\_WARNINGS=TRUE} as it is shown on figure \ref{fig:addprop}.
Click on \textbf{Close} button to save the results.
\textbf{RESTART ASPIDE FOR THE NEW CHANGES TO TAKE EFFECT}.

\begin{figure}[ht]
\centering
\includegraphics[width=0.9\textwidth]{property.jpg}
\caption{Adding swi-prolog executable}
\label{fig:addprop}
\end{figure}
\pagebreak
After the restart, you should be able to see the warnings in the  left lower corner of aspide interface (\textbf{Error Console}).

\bibliography{mybib}
\bibliographystyle{plain}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

max_stars_repo_name: hharithaki/sparc

max_issues_repo_name: hharithaki/sparc

max_forks_repo_name: hharithaki/sparc


text:
\chapter{Bayesian framework}
\label{apx_BayesGausvars}

\section{Derivation of Linear Gaussian models}
\label{apx_BayesGausvars_1}
\subsection{Bayes' theorem for Gaussian variables}
Let $ \mybold{v} $ is the measurement, then the probability $ p(\mybold{v}) $ is known. Let $ \mybold{u} $ is the desired variable, with the prior distribution $ p(\mybold{u}) $. Suppose also there exists a linear observation model:
\begin{equation}
	\mybold{v}=A\mybold{u}+\mybold{n}
\label{eq:LG5}
\end{equation}
where $ \mybold{n} $ is a zero-mean random vectors and independent on $ \mybold{u} $ and $ \mybold{v} $ and has a precision matrix denoted as $ \Lambda_{\mybold{v}|\mybold{u}}= \Sigma_{\mybold{v}|\mybold{u}}^{-1}$. One can express the joint probability $ p(\mybold{w})$ as the product of the prior probability $ p(\mybold{u}) $ and the likelihood function of the measurement given the variable $ p(\mybold{v}|\mybold{u})$ as:
\begin{eqnarray}
	p(\mybold{u})=&&\distr(\mybold{u}|\mybold{\mu}_{\mybold{u}},\Lambda^{-1}_{\mybold{u}}) \\
	p(\mybold{v}|\mybold{u})=&&\distr(\mybold{v}|A\mybold{\mu}_{\mybold{u}},\Lambda_{\mybold{v}|\mybold{u}}^{-1})
\label{eq:LG6}
\end{eqnarray}
To derive, let take the natural logarithm of both sides, using also the symmetrical shape of precision matrices,  the left hand side gives:
\begin{eqnarray}
	ln \: p(\mybold{w}) =&& -\frac{1}{2} \left(\mybold{w}-\mybold{\mu}_{\mybold{w}} \right)^T \Lambda_{\mybold{w}} \left(\mybold{w}-\mybold{\mu}_{\mybold{w}} \right) + const \nonumber\\
	=&& -\frac{1}{2} \mybold{w}^T \Lambda_{\mybold{w}} \mybold{w} +\mybold{w}^T \Lambda_{\mybold{w}} \mybold{\mu}_{\mybold{w}} \nonumber\\
	&& - \frac{1}{2} \mybold{\mu}_{\mybold{w}} \Lambda_{\mybold{w}} \mybold{\mu}_{\mybold{w}} + const
	\label{eq:LG7}
\end{eqnarray}
and the right hand side gives:
\begin{eqnarray}
	ln \left(p(\mybold{u}) p(\mybold{v}|\mybold{u}) \right) =&& \left(\mybold{u}-\mybold{\mu}_{\mybold{u}} \right)^T \Lambda_{\mybold{u}} \left(\mybold{u}-\mybold{\mu}_{\mybold{u}} \right) \nonumber\\
	&&- \frac{1}{2} \left( \mybold{v}-A\mybold{u} \right)^T \Lambda_{\mybold{v}|\mybold{u}} \left( \mybold{v}-A\mybold{u} \right) \nonumber\\
	&&+ const
\label{eq:LG8}
\end{eqnarray}
In above equations, $ const $ represents all the terms that are independent on $ \mybold{u} $ and $\mybold{v}$. The first order terms in the above equation include:
\begin{eqnarray}
	1^{st} \: order \: terms =&& \mybold{u}^T  \Lambda_{\mybold{u}} \mybold{\mu}_{\mybold{u}} - \mybold{u}^T A^T\Lambda_{\mybold{v}|\mybold{u}} \nonumber\\
	=&&  \left(\begin{matrix}\mybold{u}\\\mybold{v} \end{matrix}\right)^T  \left(\begin{matrix}\Lambda_{\mybold{u}}{\mu}_{\mybold{u}} \\ 0 \end{matrix}\right)
\label{eq:LG9}
\end{eqnarray}
and the second order terms are:
\begin{eqnarray}
	2^{nd} \: order \: terms = && -\frac{1}{2} \mybold{u}^T \left( \Lambda_{\mybold{u}}+A^T \Lambda_{\mybold{v}|\mybold{u}} A \right)\mybold{u}  - \frac{1}{2} \mybold{v}^T \Lambda_{\mybold{v}|\mybold{u}} \mybold{v} \nonumber\\
	&& + \frac{1}{2} \mybold{v}^T \Lambda_{\mybold{v}|\mybold{u}} A \mybold{u} + \mybold{u}^T A^T \Lambda_{\mybold{v}|\mybold{u}} \mybold{v} \nonumber\\
	=&& -\frac{1}{2} \left(\begin{matrix}\mybold{u}\\\mybold{v} \end{matrix}\right)^T  \left(\begin{matrix}A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}} & A^T\Lambda_{\mybold{v}|\mybold{u}} \nonumber\\ -\Lambda_{\mybold{v}|\mybold{u}} A & \Lambda_{\mybold{v}|\mybold{u}}\end{matrix}\right) \left(\begin{matrix}\mybold{u}\\\mybold{v} \end{matrix}\right) \\
	=&& -\frac{1}{2} \mybold{w}^T \Lambda_{\mybold{w}} \mybold{w}
\label{eq:LG10}
\end{eqnarray}
Comparing above equations \ref{eq:LG10}, \ref{eq:LG9} and \ref{eq:LG7}, Gaussian distribution of $ \mybold{w} $ takes the precision matrix $ \Lambda_{\mybold{w}} $ of the form:
\begin{equation}
	\Lambda_{\mybold{w}}= \left(\begin{matrix}\Lambda_{\mybold{u}\mybold{u}} & \Lambda_{\mybold{u}\mybold{v}} \\ \Lambda_{\mybold{v}\mybold{u}} & \Lambda_{\mybold{v}\mybold{v}}\end{matrix}\right) = \left(\begin{matrix}A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}} & A^T\Lambda_{\mybold{v}|\mybold{u}} \\ -\Lambda_{\mybold{v}|\mybold{u}} A & \Lambda_{\mybold{v}|\mybold{u}}\end{matrix}\right)
\label{eq:LG11}
\end{equation}
and the mean $ \mybold{\mu}_{\mybold{w}} $ is:
\begin{equation}
	\mybold{\mu}_{\mybold{w}} = \left(\begin{matrix}\mybold{\mu}_{\mybold{u}} \\ \mybold{\mu}_{\mybold{v}} \end{matrix}\right) = \Lambda_{\mybold{w}}^{-1}\left(\begin{matrix}\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \\ 0 \end{matrix}\right) =\Sigma_{\mybold{w}} \left(\begin{matrix}\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \\ 0 \end{matrix}\right)
\label{eq:LG12}
\end{equation}
The covariance matrix is obtained by taking the inverse of above:
\begin{equation}
	\Sigma_{\mybold{w}}=\left(\begin{matrix}\Sigma_{\mybold{u}\mybold{u}} & \Sigma_{\mybold{u}\mybold{v}} \\ \Sigma_{\mybold{v}\mybold{u}} & \Sigma_{\mybold{v}\mybold{v}}\end{matrix}\right) = \left(\begin{matrix}A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}} & A^T\Lambda_{\mybold{v}|\mybold{u}} \\ -\Lambda_{\mybold{v}|\mybold{u}} A & \Lambda_{\mybold{v}|\mybold{u}}\end{matrix}\right)^{-1}
\label{eq:LG13}
\end{equation}
Using the inversion lemma:
\begin{equation}
	\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)^{-1}= \left(\begin{matrix}M & -MBD^{-1} \\ D^{-1}+D^{-1}CM & D^{-1}CMBD^{-1}\end{matrix}\right)
\label{eq:LG14}
\end{equation}
where $ M=(A-BD^{-1}C)^{-1} $ is the \textit{Schur complement} of the matrix inversion with respect to $ D $. The covariance matrix is finally given as:
\begin{equation}
	\Sigma_{\mybold{w}}= \left(\begin{matrix}\Sigma_{\mybold{u}\mybold{u}} & \Sigma_{\mybold{u}\mybold{v}} \\ \Sigma_{\mybold{v}\mybold{u}} & \Sigma_{\mybold{v}\mybold{v}}\end{matrix}\right) =\left(\begin{matrix}\Lambda^{-1}_{\mybold{u}} & \Lambda^{-1}_{\mybold{u}}A^T \\ A \Lambda^{-1}_{\mybold{u}} &\Lambda^{-1}_{\mybold{v}|\mybold{u}} + A\Lambda^{-1}_{\mybold{u}}A^T\end{matrix}\right)
\label{eq:LG15}
\end{equation}
Replacing this covariance matrix to equation (\ref{eq:LG13}), the expectation of $ \mybold{w} $ is given as:
\begin{equation}
	\mybold{\mu}_{\mybold{w}} = \left(\begin{matrix}\mybold{\mu}_{\mybold{u}} \\ \mybold{\mu}_{\mybold{v}} \end{matrix}\right) =\left(\begin{matrix}\Lambda^{-1}_{\mybold{u}} & \Lambda^{-1}_{\mybold{u}}A^T \\ A \Lambda^{-1}_{\mybold{u}} & \Lambda^{-1}_{\mybold{v}|\mybold{u}} + A\Lambda^{-1}_{\mybold{u}}A^T\end{matrix}\right) \left(\begin{matrix}\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \\ 0 \end{matrix}\right) = \left(\begin{matrix}\mybold{\mu}_{\mybold{u}} \\ A\mybold{\mu}_{\mybold{u}} \end{matrix}\right)
\label{eq:LG16}
\end{equation}
From equation \ref{eq:LG15} and \ref{eq:LG16}, the Gaussian distribution of $ \mybold{v} = \distr(\mybold{v}| \mybold{\mu}_{\mybold{v}},\Sigma_{\mybold{v}}) $ is:
\begin{eqnarray}
	\mybold{\mu}_{\mybold{v}} =&& A\mybold{\mu}_{\mybold{u}} \nonumber\\
	\Sigma_{\mybold{v}} =&& \Lambda^{-1}_{\mybold{v}|\mybold{u}} + A\Lambda^{-1}_{\mybold{u}}A^T
\label{eq:LG17}
\end{eqnarray}
Using results of conditional Gaussian distribution as in equation \ref{eq:LG4}, the posterior ditribution $ \mybold{u}|\mybold{v} $ is $ \distr \left(\mybold{u}|\mybold{\mu}_{\mybold{u}|\mybold{v}}, \Sigma_{\mybold{u}|\mybold{v}} \right) $ where:
\begin{eqnarray}
	\mybold{\mu}_{\mybold{u}|\mybold{v}} =&& \mybold{\mu}_{\mybold{u}}-\Lambda^{-1}_{\mybold{u}\mybold{u}} \Lambda_{\mybold{u}\mybold{v}} (\mybold{u}-\mybold{\mu}_{\mybold{u}}) \nonumber\\
	\Sigma_{\mybold{u}|\mybold{v}} =&& \Lambda^{-1}_{\mybold{u}\mybold{u}}
\label{eq:LG18}
\end{eqnarray}
Taking the partial precision matrices from equation \ref{eq:LG11}, covariance matrix $ \Sigma_{\mybold{u}|\mybold{v}} $ is given as:
\begin{equation}
	\Sigma_{\mybold{u}|\mybold{v}}= \left(A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}}\right)^{-1}
\label{eq:LG19}
\end{equation}
and conditional mean $ \mybold{\mu}_{\mybold{u}|\mybold{v}} $ is as:
\begin{eqnarray}
	\mybold{\mu}_{\mybold{u}|\mybold{v}} =&& \mybold{\mu}_{\mybold{u}}- \left(	A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}} \right) ^{-1} \left( -A^T\Lambda_{\mybold{v}|\mybold{u}} \right) \left( \mybold{v}- A\mybold{\mu}_{\mybold{u}} \right) \nonumber\\
	=&& \left(	A^T\Lambda_{\mybold{v}|\mybold{u}}A+\Lambda_{\mybold{u}} \right)^{-1} \left(	A^T\Lambda_{\mybold{v}|\mybold{u}} \mybold{v} +\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \right)
\label{eq:LG20}
\end{eqnarray}
Final results written in covariance matrices notation, given:
\begin{eqnarray}
	\mybold{v} =&& A\mybold{u} \nonumber\\
	p(\mybold{u}) =&& \distr \left( \mybold{u}| \mybold{\mu}_{\mybold{u}},\Sigma_{\mybold{u}} \right) \nonumber\\
	p(\mybold{v}|\mybold{u}) =&& \distr \left( \mybold{v}| A\mybold{u},\Sigma_{\mybold{v}|\mybold{u}} \right)
\label{eq:LG21}
\end{eqnarray}
one gets:
\begin{eqnarray}
	p(\mybold{v}) =&& \distr \left( \mybold{v}| A\mybold{\mu}_{\mybold{u}},\Sigma_{\mybold{v}|\mybold{u}} +A\Sigma_{\mybold{u}}  A^T \right) \nonumber\\
	p(\mybold{u}|\mybold{v}) =&& \distr \left( \mybold{u}| \Sigma_{\mybold{u}|\mybold{v}} \left(	A^T\Lambda_{\mybold{v}|\mybold{u}} \mybold{v} +\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \right),\Sigma_{\mybold{u}|\mybold{v}} \right) \nonumber\\
	\Sigma_{\mybold{u}|\mybold{v}} =&& \left(A^T\Sigma_{\mybold{v}|\mybold{u}}^{-1}A+\Sigma_{\mybold{u}}^{-1}\right)^{-1}
\label{eq:LG22}
\end{eqnarray}

\subsection{ The model}
As one of the example linear Gaussian model in \cite{roweis1999unifying} and restated in \cite{bishop2006pattern}, given the Gaussian distribution of measurements $p(\mybold{u}) $ and posterior distribution $ p(\mybold{u}|\mybold{v}) $:
\begin{eqnarray}
	p(\mybold{u}) =&& \distr \left( \mybold{u}| \mybold{\mu}_{\mybold{u}},\Sigma_{\mybold{u}} \right) \nonumber\\
	p(\mybold{v}|\mybold{u}) =&& \distr \left( \mybold{v}| A\mybold{u}+\mybold{b},\Sigma_{\mybold{v}|\mybold{u}} \right)
\label{eq:bishop_linear_gaussian_1}
\end{eqnarray}
where $ \mu_{\mybold{u}} $, $ A $ and $ b $ are parameters governing the mean of the distributions; $ \Sigma_{\mybold{v}|\mybold{u}} $ is not a function of $ \mybold{u} $. Applying Bayes's theorem for these Gaussian variables, the joint distribution can be written using the prior and likelihood distributions given as:
\begin{eqnarray}
	p(\mybold{v}) =&& \distr \left( \mybold{v}| A\mybold{\mu}_{\mybold{u}} + \mybold{b},\Sigma_{\mybold{v}|\mybold{u}} +A\Sigma_{\mybold{u}}  A^T \right) \nonumber\\
	p(\mybold{u}|\mybold{v}) =&& \distr \left( \mybold{u}| \Sigma_{\mybold{u}|\mybold{v}} \left(	A^T\Lambda_{\mybold{v}|\mybold{u}} \left( \mybold{v} - \mybold{b} \right) +\Lambda_{\mybold{u}}\mybold{\mu}_{\mybold{u}} \right),\Sigma_{\mybold{u}|\mybold{v}} \right) \nonumber\\
	\Sigma_{\mybold{u}|\mybold{v}} =&& \left(A^T\Sigma_{\mybold{v}|\mybold{u}}^{-1}A+\Sigma_{\mybold{u}}^{-1}\right)^{-1}
\label{eq:bishop_linear_gaussian_2}
\end{eqnarray}

Using results in equation \ref{eq:bishop_linear_gaussian_2}, given the posterior distributions $ \distr(\mybold{z}|\varmathbb{I}_t\mybold{x},\Sigma_{\mybold{h}_t}) $ and $ \distr(\mybold{z}|\varmathbb{I}_s\mybold{y},\Sigma_{\mybold{h}_s}) $ in equations \ref{eq:Bayes21} and \ref{eq:Bayes22}, and known distributions of measurements $ \distr \left( \varmathbb{I}_t\mybold{x} |0, \Sigma_{\varmathbb{I}_t\mybold{x}} \right)$ and $ \distr \left( \varmathbb{I}_s\mybold{y} |0, \Sigma_{\varmathbb{I}_s\mybold{y}} \right)$. Results of above section show that one can get the likelihood functions and the prior distribution as:
\begin{eqnarray}
		\varmathbb{I}_t \mybold{x}|\mybold{z} :&& \distr \left(\varmathbb{I}_t \mybold{x}|\Sigma_t \Sigma_{\mybold{h}_t}^{-1} \mybold{z},\Sigma_t \right) \nonumber\\
		\varmathbb{I}_s \mybold{y}|\mybold{z} :&& \distr \left(\varmathbb{I}_s \mybold{y}|\Sigma_s \Sigma_{\mybold{h}_s}^{-1} \mybold{z},\Sigma_s \right) \nonumber\\
		\mybold{z} :&& \distr \left(\mybold{z}|0, \Sigma_{\mybold{z}}\right)
\label{eq:bishop_linear_gaussian_3}
\end{eqnarray}
where:
\begin{eqnarray}
		\Sigma_t^{-1} =&& \Sigma_{\mybold{h}_t}^{-1} + \Sigma_{\varmathbb{I}_t\mybold{x}}^{-1} \nonumber\\
		\Sigma_s^{-1} =&& \Sigma_{\mybold{h}_s}^{-1} + \Sigma_{\varmathbb{I}_s\mybold{y}}^{-1} \nonumber\\
		\Sigma_{\mybold{z}} =&& \Sigma_{\mybold{h}_t}+\Sigma_{\varmathbb{I}_t\mybold{x}} = \Sigma_{\mybold{h}_s}+\Sigma_{\varmathbb{I}_s\mybold{y}}
\label{eq:bishop_linear_gaussian_4}
\end{eqnarray}
Using above resulting Gaussian distributions, The MAP estimation of $ \mybold{z} $ is given as:
\begin{eqnarray}
	\hat{\mybold{z}} =&& \underset{\mybold{z}}{argmax} \left\lbrace  p(\varmathbb{I}_t\mybold{x}|\mybold{z})p(\varmathbb{I}_s\mybold{y}|\mybold{z})p(\mybold{z}) \right\rbrace \nonumber\\
	=&& \underset{\mybold{z}}{argmin} \left\lbrace -\ln p(\varmathbb{I}_t\mybold{x}|\mybold{z}) -\ln p(\varmathbb{I}_s\mybold{y}|\mybold{z}) -\ln p(\mybold{z}) \right\rbrace
\label{eq:bishop_linear_gaussian_5}
\end{eqnarray}
Logarithm of above probabilities are given as:
\begin{eqnarray*}
	-2\ln p(\varmathbb{I}_t\mybold{x}|\mybold{z}) =&& \left(\varmathbb{I}_t\mybold{x}-\Sigma_t \Sigma_{\mybold{h}_t}^{-1}\mybold{z} \right)^T \Sigma^{-1}_t \left(\varmathbb{I}_t\mybold{x}-\Sigma_t \Sigma_{\mybold{h}_t}^{-1}\mybold{z}\right) \\
	=&& \Arrowvert \Sigma_t \Sigma_{\mybold{h}_t}^{-1}\mybold{z}-\varmathbb{I}_t\mybold{x} \Arrowvert^2_{\Sigma_t}\\
	-2\ln p(\varmathbb{I}_s\mybold{y}|\mybold{z}) =&&  \left(\varmathbb{I}_s\mybold{y}-\Sigma_s \Sigma_{\mybold{h}_s}^{-1}\mybold{z} \right)^T \Sigma^{-1}_s \left(\varmathbb{I}_s\mybold{y}-\Sigma_s \Sigma_{\mybold{h}_s}^{-1}\mybold{z}\right)\\
	=&& \Arrowvert \Sigma_s \Sigma_{\mybold{h}_s}^{-1}\mybold{z}-\varmathbb{I}_s\mybold{y} \Arrowvert^2_{\Sigma_s}\\
	-2\ln p(\mybold{z}) =&& \mybold{z}^T \Sigma^{-1}_z \mybold{z} = \Arrowvert \mybold{z} \Arrowvert^2_{\Sigma_{\mybold{z}}}
\label{eq:bishop_linear_gaussian_6}
\end{eqnarray*}
The cost function $ C(\mybold{z}) $ is defined as the sum of above terms:
\begin{equation}
	C(\mybold{z}) =\Arrowvert \Sigma_t \Sigma_{\mybold{h}_t}^{-1}\mybold{z}-\varmathbb{I}_t\mybold{x} \Arrowvert^2_{\Sigma_t}  + \Arrowvert \Sigma_s \Sigma_{\mybold{h}_s}^{-1}\mybold{z}-\varmathbb{I}_s\mybold{y} \Arrowvert^2_{\Sigma_s} \Arrowvert \mybold{z} \Arrowvert^2_{\Sigma_{\mybold{z}}}
\label{eq:bishop_linear_gaussian_7}
\end{equation}
 The gradient of $ C(\mybold{z}) $ is computed as:
\begin{eqnarray}
	\frac{\partial C(\mybold{z})}{2\partial \mybold{z}} =&& \Sigma^{-1}_t \left( \Sigma_t \Sigma_{\mybold{h}_t}^{-1}\mybold{z}-\varmathbb{I}_t\mybold{x} \right) + \Sigma^{-1}_s \left( \Sigma_s \Sigma_{\mybold{h}_s}^{-1}\mybold{z}-\varmathbb{I}_s\mybold{y} \right) +\Sigma^{-1}_{\mybold{z}} \mybold{z} \nonumber\\
	=&& \left( \Sigma_{\mybold{h}_t}^{-1} + \Sigma_{\mybold{h}_s}^{-1} + \Sigma^{-1}_{\mybold{z}} \right) \mybold{z} - \left( \Sigma^{-1}_t\varmathbb{I}_t\mybold{x} + \Sigma^{-1}_s\varmathbb{I}_s\mybold{y} \right)
\label{eq:bishop_linear_gaussian_8}
\end{eqnarray}
The estimation of optimized $ \hat{\mybold{z}} $ is obtained when setting this gradient to zeros:
\begin{equation}
	\hat{\mybold{z}}=\left( \Sigma_{\mybold{h}_t}^{-1} + \Sigma_{\mybold{h}_s}^{-1} + \Sigma^{-1}_{\mybold{z}} \right)^{-1} \left(\Sigma^{-1}_t\varmathbb{I}_t\mybold{x} +\Sigma^{-1}_s\varmathbb{I}_s\mybold{y}\right)
\label{eq:bishop_linear_gaussian_9}
\end{equation}

\section{Derivation of generalized Millman formula}
\label{apx_BayesGausvars_2}
Let denote $ \left\lbrace \hat{\mybold{z}}_1,...,\hat{\mybold{z}}_K \right\rbrace  $ be K estimates of an unknown random vector $ \mybold{z} \in R^n $. The objective of the fusion model is to find the best linear estimate via a set of coefficient matrices $ C_i $ (i=1,...,K):
\begin{equation}
\hat{\mybold{z}}=\sum\limits_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \:\:\:\:\:\:\:\:\: s.t \:\:\:\:\:\:\:\:\: \sum\limits_{i=1}^{K}{C_i}=I_n
\end{equation}
where the weighting matrices are estimated as:
\begin{equation}
\left\lbrace C_i \right\rbrace_{i=1,...,K}=\argmin_{C_i} \left\| \mybold{z}-\sum_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \right\|^2_2 \:\:\:\:\:\:\:\:\: s.t \:\:\:\:\:\:\:\:\: \sum_{i=1}^{K}{C_i}=I_n
\end{equation}
Define the loss function $ J $ as the error expectation:
\begin{equation}
J=E\left\lbrace \left\|  \mybold{z}-\sum\limits_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \right\| ^2_2 \right\rbrace
\end{equation}
Define also the total error covariance:
\begin{align}
	\Sigma &\triangleq \cov{ \mybold{z}-\hat{\mybold{z}}}  \\
	&= \E {\left(   \mybold{z}-\sum\limits_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \right) \left(   \mybold{z}-\sum\limits_{j=1}^{K}{C_j\hat{\mybold{z}}_j} \right)^T}
\end{align}
Since $ \sum_{i=1}^{K}{C_i}=I_n $, the total error covariance is given as:
\begin{equation}
	\Sigma = \E{ \sum\limits_{i=1}^{K}{C_i\left(\mybold{z}-\hat{\mybold{z}}_i \right)}  \sum\limits_{j=1}^{K}{C_j\left(\mybold{z}-\hat{\mybold{z}}_j\right)^T}}
\end{equation}
Define the local error term as $ \tilde{\mybold{z}}_i \triangleq \mybold{z}-\hat{\mybold{z}}_i $ and the local error covariance as $ \Sigma_{ij}\triangleq \cov{\tilde{\mybold{z}}_i,\tilde{\mybold{z}}_j} $, the total error covariance becomes:
\begin{align}
	\Sigma &= \E{\sum\limits_{i,j=1}^{K}{C_i\tilde{\mybold{z}}_i \left(C_j\tilde{\mybold{z}}_j\right)^T}} \\
	&= \sum\limits_{i,j=1}^{K}{C_i\Sigma_{ij}C_j^T}
\end{align}
The loss function $ J $ is rewritten as:
\begin{align}
	J &= E\left\lbrace \left\|  \mybold{z}-\sum\limits_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \right\| ^2_2 \right\rbrace \\
	&= \tr{\sum\limits_{i,j=1}^{K}{C_i\Sigma_{ij}C_j^T}}
\end{align}
Substituting $ C_K=I_n-C_1-C_2-...-C_{K-1} $ into above equation, one gets:
\begin{equation}
\begin{aligned}
J= & \tr{\sum\limits_{i,j=1}^{K-1}{C_i\Sigma_{ij}C_j^T}+\sum\limits_{i,j=1}^{K-1}{\left(C_i\Sigma_{iK}+\Sigma_{Ki}C_i^T\right)}-\sum\limits_{i,j=1}^{K-1}{\left(C_i\Sigma_{iK}C_j^T+C_j\Sigma_{Ki}C_j^T\right)}} \\
& +\tr{\Sigma_{KK}-\left(\sum\limits_{i,j=1}^{K-1}{C_i}\right)\Sigma_{KK}-\Sigma_{KK}\left(\sum\limits_{i,j=1}^{K-1}{C_j^T}\right)+\sum\limits_{i,j=1}^{K-1}{C_i\Sigma_{KK}C_j^T}}
\end{aligned}
\end{equation}
Using the symmetric property of covariance matrices, i.e. $ \Sigma_{ij}=\Sigma_{ji}^T $ and $ \Sigma_{ii}=\Sigma_{ii}^T $, one gets:
\begin{align}
	\frac{\partial}{\partial C_i} \left(\tr{C_i\Sigma} \right) &= \Sigma^T \\
	\frac{\partial}{\partial C_i} \left(\tr{\Sigma C_i^T} \right) &= \Sigma \\
	\frac{\partial}{\partial C_i} \left(\tr{C_i \Sigma C_i^T} \right) &= C_i \left(\Sigma+\Sigma^T \right)
\end{align}
Taking partial derivative $ \partial J / \partial C_i $ and set to zero, one gets:
\begin{equation}
	\sum\limits_{i,j=1}^{K-1}{C_i} \left(\Sigma_{ij}-\Sigma_{iK}\right)+C_K\left(\Sigma_{Kj}-\Sigma_{KK}\right) = 0 \:\:\:\:\: s.t. \:\:\:\:\: \sum\limits_{i,j=1}^{K}{C_i}=I_n, \:\: j=1,...,K-1
\end{equation}
The final GMF of fusing $ \mybold{z} $ from $ \left\lbrace \hat{\mybold{z}}_1,...,\hat{\mybold{z}}_K \right\rbrace  $ is:
\begin{equation}
\hat{\mybold{z}}=\sum\limits_{i=1}^{K}{C_i\hat{\mybold{z}}_i} \:\:\:\:\: s.t. \:\:\:\:\: \begin{cases}
\sum\limits_{i=1}^{K}{C_i}=I_n\\
\sum\limits_{i,j=1}^{K-1}{C_i} \left(\Sigma_{ij}-\Sigma_{iK}\right)+C_K\left(\Sigma_{Kj}-\Sigma_{KK}\right) = 0, \:\: j=1,...,K-1
\end{cases}
\end{equation}
with a total error covariance of:
\begin{equation}
\Sigma=\sum\limits_{i,j=1}^{K}{C_i\Sigma_{ij}C_j^T}
\end{equation}

\subsubsection*{Bar-Shalom and Campo (1986)}
In the case of fusing two estimates ($ K=2 $), the GMF becomes Bar-Shalom-Campo formula:
\begin{equation}
\hat{\mybold{z}}=C_1\hat{\mybold{z}}_1+C_2\hat{\mybold{z}}_2
\end{equation}
Weighting matrices $ C_1 $ and $ C_2 $ satisfy:
\begin{equation}
\begin{cases}
C_1+C_2=I_n\\
C_1\left(\Sigma_{11}-\Sigma_{12}\right)+C_2\left(\Sigma_{21}-\Sigma_{22}\right)=0 \\
C_1\left(\Sigma_{12}-\Sigma_{12}\right)+C_2\left(\Sigma_{22}-\Sigma_{22}\right)=0
\end{cases}
\end{equation}
which lead to:
\begin{equation}
\begin{cases}
C_1 = \left(\Sigma_{22}-\Sigma_{21}\right)\left(\Sigma_{11}+\Sigma_{22}-\Sigma_{12}-\Sigma_{21}\right)^{-1}\\
C_2 = \left(\Sigma_{11}-\Sigma_{12}\right)\left(\Sigma_{11}+\Sigma_{22}-\Sigma_{12}-\Sigma_{21}\right)^{-1}
\end{cases}
\end{equation}
In case $ \tilde{\mybold{z}}_1 $ and $ \tilde{\mybold{z}}_2 $ are uncorrelated, i.e. $ \Sigma_{12}=\Sigma_{21}=0 $, the fusion formula is known as the Millman's formula:
\begin{equation}
\hat{\mybold{z}}=\Sigma_{22}\left(\Sigma_{11}+\Sigma_{22}\right)^{-1}\hat{\mybold{z}}_1+\Sigma_{11}\left(\Sigma_{11}+\Sigma_{22}\right)^{-1}\hat{\mybold{z}}_2
\end{equation}
This formula is identical to the Bayesian fusion model assuming a non-informative prior on $ \mybold{z} $.

max_stars_repo_name: linhvannguyen/PhDworks

max_issues_repo_name: vanlinhnguyen/PhDworks

max_forks_repo_name: vanlinhnguyen/PhDworks