\documentclass{llncs}
\usepackage{graphicx}
\usepackage{mathpartir}
\usepackage{amsmath,amssymb}
\usepackage{stmaryrd}
\newcommand{\hearts}{\heartsuit}
\newcommand{\prems}{\mathit{prems}}
\newcommand{\eval}{\mathit{eval}}
\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\ind}[1]{\llparenthesis #1 \rrparenthesis}
\input{header}
\sloppy
% The following is enclosed to allow easy detection of differences in
% ascii coding.
% Upper-case A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
% Lower-case a b c d e f g h i j k l m n o p q r s t u v w x y z
% Digits 0 1 2 3 4 5 6 7 8 9
% Exclamation ! Double quote " Hash (number) #
% Dollar $ Percent % Ampersand &
% Acute accent ' Left paren ( Right paren )
% Asterisk * Plus + Comma ,
% Minus - Point . Solidus /
% Colon : Semicolon ; Less than <
% Equals =3D Greater than > Question mark ?
% At @ Left bracket [ Backslash \
% Right bracket ] Circumflex ^ Underscore _
% Grave accent ` Left brace { Vertical bar |
% Right brace } Tilde ~
% A couple of exemplary definitions:
%\newcommand{\Nat}{{\mathbb N}}
%\newcommand{\Real}{{\mathbb R}}
\newcommand{\COLOSS}{{\textrm CoLoSS}}
\def\lastname{Hausmann}
\begin{document}
\begin{frontmatter}
\title{Optimizing Coalgebraic Modal Logic Reasoning}
\author{Daniel Hausmann\thanks{Work forms part of DFG-project \emph{Generic Algorithms and Complexity
Bounds in Coalgebraic Modal Logic} (SCHR 1118/5-1)}}
\institute{Department of Computer Science, Universit\"at Bremen\\\email{hausmann@informatik.uni-bremen.de}}
\maketitle
\end{frontmatter}
\begin{abstract}
The framework provided by coalgebraic modal logics offers
broadly applicable coalgebraic semantics and an ensuing general
treatment of modal sequent and tableau calculi while covering a wide
variety of logics ranging from graded and probabilistic modal logic
to coalition logic and conditional logics. Here we discuss generic optimisation
strategies that may be employed to improve the performance of a global
caching algorithm that decides the satisfiability of coalgebraic modal logics.
Specifically, we discuss and show the admissability of generalisations of such
established strategies as \emph{semantic branching} and \emph{dependency directed backtracking}
to coalgebraic modal logics. As a more advanced consideration, the flattened
representation of the involved proof graph by a \emph{proof formula} is shown to be
sound and complete; this separation of \emph{proof structure} from the actual content of
the proof does not only enhance the performance of the propagation
process, it also allows for further optimisation techniques such as
\emph{proof graph simplification} to be applied. The presented optimisation
techniques are implemented as part of the examplary implementation, the
\emph{Coalgebraic Logic Satisfiability Solver}(\emph{CoLoSS}).
\end{abstract}
\section{Introduction}\label{intro}
Coalgebraic modal logic has been established as a unifying framework
for many modal logics~\cite{SchroderPattinson09}, allowing for generic and
efficient decision of satisfiability (and provability) of those modal logics.
In this context, the \emph{Coalgebraic Logic Satisfiability Solver}(\emph{CoLoSS}\footnote{available under \email{http://www.informatik.uni-bremen.de/cofi/CoLoSS/} })
serves as an examplary implementation of the developed algorithms and as a testsuite
for their optimisations~\cite{CalinEA09,HausmannSchroder10}.
The broader focus introduces new difficulties to the process of proving
satisfiablity (or provablility) of a formula, especially since the considered
logics do not necessarily branch only on disjunctions (or conjunctions respectively) but
may also introduce branching through their modal rules.
Recent research in the area of coalgebraic modal logics has shown that the
satisfiability (and provability) of coalgebraic logics with global assumptions
may be decided in EXPTIME by means of an optimal global caching algorithm, thus
enabling support for (basic) description logics in the coalgebraic setting~\cite{GoreEA10}.
The introduced algorithm is based on graph rewriting, however it has the weakness
that the propagation of satisfiability through the graph is realized by
computing fixpoints of the complete graph w.r.t specific functionals.
This work aims at improving the performance of said algorithm in two directions:
\begin{enumerate}
\item Established optimisation techniques for specific logics (such as \textbf{K}) are
generalized and the generalizations are shown to be correct, thus allowing for these techniques
to be applied for any coalgebraic modal logic.
\item \emph{Proof formulas}, a flattened representation of the central data structure of the global caching algorithm
(i.e. the proof graph) are introduced. The process of propagation may then be realized as a simple process of
propositional simplification in the proof formula (thus making it feasable to propagate after each step of expansion).
\end{enumerate}
The paper is structured as follows: We first give a short overview over
coalgebraic modal logics. Then we briefly recall an optimal global caching
algorithm that decides the provability of coalgebraic modal logics (with global
assumptions). As the central contribution of the paper, we then turn our attention
to the optimisation of said algorithm, focussing on three particular optimisation
techniques: Generic semantic branching, generic dependency directed backtracking
and efficient propagation by the use of proof formulas. The admissabilty of each
of these generic optimization techniques is proved.
\section{Coalgebraic Modal Logic}
We quickly recall the needed notions from the domain of coalgebraic modal logic~\cite{SchroderPattinson09}:
\subsection{Notation}
Given an endofunctor on sets $T$, a $T$-coalgebra $\mathcal{C}$ consists of a
carrier-set $C$ and a function $\gamma:C\rightarrow T(C)$.
The semantics of modal operators $\hearts\in\Lambda$ is then defined by means
of \emph{predicate liftings} $\sem{\hearts}:2^n\rightarrow2\circ T^{op}$ where
$2:\mathbf{Set}\rightarrow\mathbf{Set}^{op}$ denotes the contravariant powerset functor.
Formulas are of the shape
\begin{quote}
$\mathcal{F}(\Lambda)\ni A_1,\ldots,A_n\mathrel{\mathop:}=p\mid \neg A_1 \mid A_1\wedge A_2\mid A_1\vee A_2 \mid \hearts(A_1,\ldots,A_n)$
\end{quote}
where $\hearts\in\Lambda$ is an $n$-ary modal operator.
The semantics with respect to a model coalgebra $M=(C,\gamma,\pi)$ (where $\pi$ denotes a
valuation of propositional atoms) is fixed as follows:
\begin{quote}
$\sem{\hearts(A_1,\ldots,A_n)}_M=\gamma^{-1}\circ\sem{\hearts}_C(\sem{A_1}_M,\ldots,\sem{A_n}_M)$
\end{quote}
A ($\Lambda$-)\emph{sequent} $\Gamma$ is a set of formulas (from $\mathcal{F}(\Lambda)$). We refer
to the set of all sequents of a logic as $Seq$ and to the set of all sets of sequents of a
logic as $Prem$.
A \emph{sequent rule} consists of its \emph{premise} $\Sigma$ (a set of sequents)
and its \emph{conclusion} $\Gamma$ (one sequent). A rule $R=(\Sigma=\{\Gamma_1,\ldots,\Gamma_n\},\Gamma)$
is usually presented as follows:
\begin{quote}
\centerline{\inferrule{\Gamma_1 \\ \ldots \\ \Gamma_n}{\Gamma}}
\end{quote}
A rule application of rule $R$ to sequent $\Gamma$ is an instantiation of $R$
s.t. the conclusion of the rule is equal to $\Gamma$.
A formula $\phi$ is provable if there is a model coalgebra $M=(C,\gamma,\pi)$ with a
state $x\in C$ s.t. $\sem{\phi}\ni x$. A sequent $\Gamma=\{\phi_1,\ldots,\phi_n\}$ is provable
iff $\bigvee_{i=1}^n\phi_i$ is provable.
A premise is said to be provable iff all its sequents are provable.
A sound and complete algorithm for the decision of provability (and satisfiability) of formula
of the according coalgebraic logic may be obtained if
the propositional rules from Figures~\ref{fig:bpropRules} and~\ref{fig:lpropRules} are utilized together
with the appropriate modal rule(s). Some examplary modal rules for different coalgebraic modal logics are
depicted in Figure~\ref{fig:modalRules} (for more details, refer to~\cite{SchroderPattinson09}) while the modal rules of some conditional logics are
introduced in Figure~\ref{fig:modalRules2} (more details about optimisation of coalgebraic conditional logics
can be found in~\cite{PattinsonSchroder08b,HausmannSchroder10}). The collection of all currently utilized rules is referred to
as $\mathcal{R}$.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l |}
\hline
($\neg\vee$)\inferrule{\Gamma,A \\ \Gamma,B}{\Gamma, \neg (\neg A\vee \neg B)} \\
\hline
\end{tabular}
\end{center}
\caption{Branching propositional sequent rule}
\label{fig:bpropRules}
\end{figure}
\end{footnotesize}
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l |}
\hline
(T)\inferrule{ }{\Gamma, \top}\qquad
(At)\inferrule{ }{\Gamma, p, \neg p}\qquad
($\neg\neg$)\inferrule{\Gamma, A}{\Gamma, \neg\neg A}\qquad
($\vee$)\inferrule{\Gamma,A,B}{\Gamma, (A\vee B)} \\
\hline
\end{tabular}
\end{center}
\caption{Linear or closing propositional sequent rules}
\label{fig:lpropRules}
\end{figure}
\end{footnotesize}
Take note that the rules from Figure~\ref{fig:lpropRules} may be integrated into
the process of normalisation, saturation or simpification (see 3.1) due to their linearity.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l |}
\hline
Modal Logic (Feature) & Modal Rule(s)\\
\hline
\textbf{M} ($\Box_\mathbf{M}$) & \inferrule{A\rightarrow B}{\Gamma,\Box_\mathbf{M} A\rightarrow\Box_\mathbf{M} B} \\
\hline
\textbf{K} ($\Box_\mathbf{K}$) & \inferrule{\bigwedge\limits_{i=1}^n A_i\rightarrow B}
{\Gamma,\bigwedge\limits_{i=1}^n\Box_\mathbf{K} A_i\rightarrow\Box_\mathbf{K} B} \\
\hline
\textbf{KD} ($\Box_\mathbf{KD}$) & \inferrule{\bigwedge\limits_{i=1}^n A_i\rightarrow B}
{\Gamma,\bigwedge\limits_{i=1}^n\Box_\mathbf{KD} A_i\rightarrow\Box_\mathbf{KD} B} \qquad
\inferrule{\neg\bigwedge\limits_{i=1}^n A_i}
{\Gamma,\neg\bigwedge\limits_{i=1}^n\Box_\mathbf{KD} A_i} \\
\hline
Hennessy-Milner-Logic ($\Box^a_\mathbf{HM}$) & \inferrule{\bigwedge\limits_{i=1}^n A_i\rightarrow B}
{\Gamma,\bigwedge\limits_{i=1}^n \Box^a_\mathbf{HM} A_i\rightarrow\Box^a_\mathbf{HM} B} \\
\hline
Coalition Logic ($\Box^C_\mathbf{C}$) & \inferrule{\bigwedge\limits_{i=1}^n A_i\rightarrow B\vee\bigvee\limits_{j=1}^m C_j}
{\Gamma,\bigwedge\limits_{i=1}^n\Box^{C_i}_\mathbf{C} A_i\rightarrow
\Box^D_\mathbf{C} B\vee\bigvee\limits_{j=1}^m \Box^N_\mathbf{C} C_j} \\
& $m,n\geq 0$,\\ & $C_i$ pairwise disjoint subsets of $D$.\\
\hline
Graded Modal Logic ($\Diamond^i_\mathbf{G}$) & \inferrule{\sum\limits_{i=1}^n A_i\leq\sum\limits_{j=1}^m B_j}
{\Gamma,\bigwedge\limits_{i=1}^n\Diamond^{k_i}_\mathbf{G}
A_i\rightarrow\bigvee\limits_{j=1}^m\Diamond^{l_j}_\mathbf{G} B_j} \\
& $n,m\geq 0$,\\
& $\sum\nolimits_{i=1}^n(k_i + 1)\geq 1 + \sum\nolimits_{j=1}^m l_j$.\\
\hline
Probabilistic Modal Logic ($\Diamond^p_\mathbf{P}$) & \inferrule{\sum\limits_{i=1}^n A_i + u \leq\sum\limits_{j=1}^m B_j}
{\Gamma,\bigwedge\limits_{i=1}^n\Diamond^{p_i}_\mathbf{P}
A_i\rightarrow\bigvee\limits_{j=1}^m\Diamond^{q_j}_\mathbf{P} B_j} \\
& $m,n\geq 0$, $m+n\geq 1$, $u\in \mathbb{Z}$,\\
& $\sum\nolimits_{i=1}^n p_i + u \geq \sum\nolimits_{j=1}^m q_j$ and\\
& $m=0\rightarrow \sum\nolimits_{i=1}^n p_i + u > 0$.\\
\hline
\end{tabular}
\end{center}
\caption{One-step complete, resolution closed modal rules for some coalgebraic modal logics}
\label{fig:modalRules}
\end{figure}
\end{footnotesize}
We introduce the following abbreviations in order to allow for a swift presentation of the modal rules
of propositional and graded modal logic:
Given a formula $\phi_i$ and $r_i\in\mathbb{Z}$ for all $i\in I$ as well as $k\in\mathbb{Z}$,
\begin{quote}
$\sum\limits_{i\in I}r_i\phi_i\geq k\equiv \bigwedge\limits_{J\subseteq I, r(J)<k}(
\bigwedge\limits_{j\in J}\phi_j\rightarrow\bigvee\limits_{j\notin J}\phi_j)$,
\end{quote}
where $r(J)=\sum\nolimits_{j\in J}r_j$. Furthermore, we use $\sum a_i\leq\sum b_j$ as an abbreviation
for $\sum b_j - \sum a_i \geq 0$.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l |}
\hline
Modal Logic (Feature) & Modal Rule(s)\\
\hline
\textbf{CK} ($\Rightarrow_\mathbf{CK}$) & \inferrule{ A_0\leftrightarrow\ldots \leftrightarrow A_n \\ \neg B_1,\ldots, \neg B_n,B_0 }
{ \Gamma,\bigwedge\limits_{i=1}^n (A_i\Rightarrow_\mathbf{CK} B_i)\rightarrow (A_0\Rightarrow_\mathbf{CK} B_0)} \\
\hline
\textbf{CK+CEM} ($\Rightarrow_\mathbf{CK_{CEM}}$) & \inferrule{ A_0\leftrightarrow\ldots \leftrightarrow A_n \\ B_0,\ldots,B_k,\neg B_{k+1},\ldots \neg B_n}
{ \Gamma,\bigwedge\limits_{i=k+1}^ n (A_i\Rightarrow_\mathbf{CK_{CEM}} B_i)\rightarrow
\bigvee\limits_{j=0}^k(A_j\Rightarrow_\mathbf{CK_{CEM}} B_j)} \\
\hline
\textbf{CK+CM} ($\Rightarrow_\mathbf{CK_{CM}}$) & \vspace{-20pt}\begin{tabular}{ c l }
$A_i=A_j$ & for $i,j\in l(v),v\in G$ initial\\
$\bigcup\nolimits_{i\in l(v)} \{\neg B_i,\neg A_i\},A_j$ &
for $v\in G$ and $j\in l(w)$\\
& for some successor $w$ of $v$ \\
$\{\neg B_i\mid i\in I\},D$\\
$\bigcup\nolimits_{i\in I} \{\neg B_i,\neg A_i\},C$ \\
$\neg C, A_i$ & for $i\in I$ \\
\end{tabular}\\
& \inferrule{\empty}{\hspace{28pt}\Gamma,\bigwedge\limits_{i\in I}(A_i\Rightarrow_\mathbf{CK_{CM}} B_i)
\rightarrow (C\Rightarrow_\mathbf{CK_{CM}} D) \hspace{28pt}}\\
& for an $I$-compatibility graph $G$ \\
\hline
System S ($\Rightarrow_{SysS}$) & \inferrule { \Delta_M(\nu(M)) \text{ for each } M\in\mathfrak{S}_{\Gamma_0}}
{ \Gamma,\underbrace {\bigwedge\limits_{i\in I}(A_i\Rightarrow_{SysS} B_i)\rightarrow
(A_0\Rightarrow_{SysS} B_0)}_{\equiv:\Gamma_0}}\\
& where $\mathfrak{S}_{\Gamma_0}$ denotes all S-structures $(S,\preceq)$ over $\Gamma_0$,\\
& $\Delta_M([i])\equiv\bigcup_{k\simeq i}\{\neg A_k, \neg B_k\},
\{A_j\mid i \prec j\vee j\notin S\}$, \\
& $\Delta_M([0])\equiv\neg A_0, \bigcup_{0\neq k\simeq 0}\{\neg A_k, \neg B_k\},
B_0,\{A_j\mid j\notin S\}$.\\
\hline
\end{tabular}
\end{center}
\caption{One-step complete, resolution closed modal rules for some conditional logics}
\label{fig:modalRules2}
\end{figure}
\end{footnotesize}
\noindent Furthermore, we allow for the treatment of global assumptions (which may be thought of as representing a TBox) by expanding
the employed modal rules as follows: Given a set of global assumptions $\Delta$ and a modal rule
$R = \Gamma_0,\ldots,\Gamma_n / \Gamma$, the expanded rule is defined as $R' = (\Delta\rightarrow\Gamma_0),\ldots,
(\Delta\rightarrow\Gamma_n) / \Gamma$, i.e. we add the global assumptions to each newly constructed state.
The presence of global assumptions introduces the possibility of running into circularities during the course of
of the proof so that a simple sequent calculus without blocking is no longer sufficient to solve the task
(as it would possibly not terminate). Hence we introduce an algorithm that uses \emph{global caching} in order to
not only detect circular proof requirements but to also benefit from the improved performance that comes along with
the use of (global) caching techniques.
\section{Global Caching Algorithm for Coalgebraic Logics}
We quickly recall the global caching algorithm that was introduced in~\cite{GoreEA10}
while treating provability of formulas here rather than satisfiability. However, a formula is
satisfiable whenever its negation is not provable.
\subsection{The proof graph and transitions}
Given a sequent $\Gamma$, we define the set of all possible rule applications to $\Gamma$,
$Rules(\Gamma)=\{(\Gamma,\Sigma)\mid\text{ is an instance of a rule } R \}$, the set of
those sequents that appear in premises of rules that are applicable to $\Gamma$, $S(\Gamma)=
\{\Gamma'\mid(\Gamma,\Sigma)\text{ is an instance of a rule } R\wedge \Gamma'\in\Sigma\}$,
and the set of all selections
$Selections(\Gamma)=\{(\Sigma,\Gamma')\mid (\Gamma,\Sigma)\in Rules(\Gamma)\wedge\Gamma'\in \Sigma\}$.
A \emph{proof graph} is a tuple $(A,E,U,X,L_1,L_2)$ where $A,E,U\subseteq Seq$ are sets of sequents,
$X\subseteq Prems$ is a set of premises. The (partial) function $L_1$ assigns the set $Rules(\Gamma)$ to a
sequent $\Gamma$ whereas the (partial) function $L_2$ assigns the set $Selections(\Gamma)$ to a sequent $\Gamma$.
The sets $A$ und $E$ contain those sequents which are already known to be provable and improvable respectively.
The set $U$ contains the already expanded but yet undecided sequents whereas the set $X$ keeps track
of those sequents that have yet to be explored. The relations between sequents and premises are stored
in the two functions $L_1$ and $L_2$.
Unexpanded sequents $\Gamma\in X$ (i.e. sequents to which no rule has been applied
yet), are also called \emph{open sequents}. A proof graph with $X=\emptyset$ is
called \emph{fully expanded}.
Any sequent to which either the rule (T) or the rule (At) may be applied
is called a \emph{successful leaf} of the proof graph.
Any sequent $\Gamma$ to which no rule may be applied (i.e. $\Gamma$ is not equal to the conclusion of any instance of any of
the employed rules) is called an \emph{unsuccessful leaf}.
For the sake of readability, we will sometimes show \emph{simplified proof graphs} where only one rule application
is considered for each sequent (such that only one -- the interesting one -- of the possible premises of each sequent is shown).
We now fix two effectively computable transitions between proof graphs:
\begin{itemize}
\item \emph{Expand:} Given a sequent $\Gamma$ from $X$, this transition leads from a graph
$g$ to the graph $g'$ that is
obtained from $g$ by expanding $\Gamma$. To this end, $X$ is extended by $S(\Gamma)$ and
$\Gamma$ is removed from $X$ ($X'=(X\cup S(\Gamma))\setminus \Gamma$).
Furthermore, $L_1$ is extended by all possible rule applications for $\Gamma$
($L_1'=L_1 \cup Rules(\Gamma)$). Finally, $L_2$ is extended by all possible selections
for rule applications to $\Gamma$ ($L_2'=L_2\cup Selections(\Gamma)$).
In conclusion, this procedure applies all applicable rules to $\Gamma$, marks all resulting
premises as not yet expanded, marks $\Gamma$ as expanded and stores the implied transitions in
$L_1$ and $L_2$.
For a fixed sequent $\Gamma$ and a graph $g$, we denote the expansion of $\Gamma$ in $g$ by
$exp(g,\Gamma)$. If $g'=exp(g,\Gamma)$, we also write $g\stackrel{\Gamma}\rightarrow_E g'$.
\item \emph{Propagate:} This procedure evaluates the given graph as far as yet possible: The sets
$X$, $L_1$ and $L_2$ remain unchanged. The set of provable sequents however is extended by the least
fixpoint of a function $M^L$ ($A'=A\cup\mu(M^L)$). The set of improvable sequents is extended by the
greatest fixpoint of a function $W^L$ ($E'=E\cup\nu(W^L)$). Finally, those sequents that are known to be
either provable or not provable are removed from the set of undecided sequents
($U'=U\setminus(A'\cup E')$).\\
The functions which are used for the fixpoint computations are defined as follows:\\
\begin{quote}
$M^L(X)=\{\Gamma\in U\mid\exists(\Gamma,\Sigma)\in L_1.\forall (\Sigma,\Gamma')\in L_2. \Gamma'\in X\cup A\}$\\
$W^L(X)=\{\Gamma\in U\mid\forall(\Gamma,\Sigma)\in L_1.\exists (\Sigma,\Gamma')\in L_2. \Gamma'\in X\cup E\}$\\
\end{quote}
Given a graph $g$, we denote the graph obtained by propagating in $g$ by
$prp(g)$. If $g'=prp(g)$, we also write $g\rightarrow_P g'$.
\end{itemize}
\subsection{The Algorithm}
In order to show the provability of a formula $\phi$, we start off with the sequent
$\Gamma_0=\{\phi\}$:
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l |}
\hline
\textbf{Algorithm:} (Show provability of $\Gamma_0$)\\
1. Initialize: $A_0=E_0=\emptyset$, $U_0=\{\Gamma_0\}$, $X_0=S(\Gamma_0)$,\\ \quad$g=(A_0, E_0, U_0, X_0
Rules(\Gamma_0), Selections(\Gamma_0))$.\\
2. If $X=\emptyset$, return the current graph as result.\\
3. Otherwise select any sequent $\Sigma$ from $X$. Compute $g'=exp(g,\Gamma)$ s.t.
$g\stackrel{\Gamma}\rightarrow_E g'$.\\ \quad (Optionally: Compute $g''=prp(g')$ s.t.
$g'\rightarrow_P g''$;\\ \quad If $\Gamma_0\in A''\cup E''$, break and return the current
graph as result.)\\
4. Set the current graph to $g'$ (or $g''$ if a propagation step took place). \\\quad Continue with 2.\\\\
After the loop has finished, propagate one final time and then
let $A$ ($E$) \\ denote the set of provable (improvable) sequents of the resulting
graph. \\ If $\Gamma_0\in A$, return \verb|True|, if $\Gamma_0\in E$, return
\verb|False|, otherwise return \verb|Undecided|.\\
\hline
\end{tabular}
\end{center}
\caption{The global caching algorithm}
\label{fig:globalAlg}
\end{figure}
\end{footnotesize}
In~\cite{GoreEA10}, this algorithm has been shown to be
\begin{description}
\item{a) }sound and complete w.r.t. provability of formulas of the logic that is
represented by the utilized set of rules $\mathcal{R}$,
\item{b) }of complexity EXPTIME, if the underlaying ruleset allows for it.
\end{description}
\section{Optimisations}
Even though the complexity of deciding provability (satisfiability) of modal formulas
using the above algorithm is exponential,
it is still possible to achieve reasonable performance by making
use of several optimisation techniques, such as described for specific
logics in~\cite{HorrocksPatelSchneider99}.
Since the above algorithm makes use of global caching in order to
recognize circular proof requirements, it is already optimized in so far as that
the provability (improvability) of any sequent $\Gamma$ has to be shown only once during
the course of a proof (as the status of this sequent is stored and may be looked up upon future occurances of $\Gamma$).
We continue by describing further methods to modify the introduced algorithm such
that even complex formulas may be efficiently treated:
First of all, we assume all appearing formulas to be normalized to truth,
negation and generalized disjunction (where the collection of all disjuncts is treated as a set
in order to remove duplicates and ordering) as indicated by the rules shown in
Figure~\ref{fig:normalisation}.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l |}
\hline
Syntactic construct & Normalisation \\
\hline
$\bot$ & $\neg\top$ \\
$\neg\neg\phi$ & $\phi$ \\
$\phi\wedge\psi$ & $\neg(\neg\phi\vee\neg\psi)$ \\
$\phi\rightarrow\psi$ & $\neg\phi\vee \psi$ \\
$\phi\leftrightarrow\psi$ & $(\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi)$ \\
$\phi\vee\psi$ & $\cup\{\phi,\psi\}$ \\
$\cup\{\phi,(\cup\Gamma)\}$ & $\cup(\{\phi\}\cup\Gamma)$ \\
\hline
\end{tabular}
\end{center}
\caption{Normalisation rules}
\label{fig:normalisation}
\end{figure}
\end{footnotesize}
\noindent Furthermore, the input formula is assumed to already contain only the standard modalities
for each feature (e.g. $\Box_K\phi$ is assumed to be represented by $\neg\Diamond_K\neg\phi$).
\noindent As another convention, we assume that sequents are always being \emph{satured}
(i.e. top-level disjunctions $\cup S$ are replaced by just the set $S$).
\noindent As usual, there is a list of all appearing formulas and a sequent is encoded as a string of
bits, where the bit at position $i$ indicates whether the sequent contains the $i$-th element of the list
of formulas or not.
\noindent Another improvement over the algorithm from~\cite{GoreEA10} is based on the following
observation: If a sequent $\Gamma$ has been shown to be provable, all sequents containing $\Gamma$ will
be provable as well. Thus it is admissable to soften the requirement in the functionals which are used to
compute the fixpoints:
\begin{quote}
$M^L(X)'=\{\Gamma\in U\mid\exists(\Gamma,\Sigma)\in L_1.\forall (\Sigma,\Gamma')\in L_2. \exists \Gamma''\subseteq \Gamma'.\Gamma''\in X\cup A\}$\\
$W^L(X)'=\{\Gamma\in U\mid\forall(\Gamma,\Sigma)\in L_1.\exists (\Sigma,\Gamma')\in L_2. \exists \Gamma''\subseteq \Gamma'.\Gamma''\in X\cup E\}$\\
\end{quote}
\subsection{Simplification}
As a first basic optimisation, simplifaction makes use of specific (propositional or modal)
tautologies in order to deterministically rewrite any appearing formulas in a proof.
The application of simplification does not invoke any branching and is thus a
linear process.
\noindent A non-exhaustive list of some important simplification rules is shown in
Figure~\ref{fig:tauts}.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l |}
\hline
Operator & Propositional Tautology \\
\hline
$\vee$ & $\cup\{\top,...\}\rightarrow \top$ \\
& $\cup\{\neg\top,\phi_1,\ldots,\phi_n\}\rightarrow \cup\{\phi_1,\ldots,\phi_n\}$ \\
& $\cup\{\phi,\neg\phi,\ldots\}\rightarrow \top$ \\
\hline
$\vee\wedge$ & $\cup\{\neg\phi,\neg(\neg\phi\vee\neg\psi)\}\rightarrow\psi$\\
\hline
$\Box_\mathbf{K}$ & $\Box_\mathbf{K}\top\rightarrow \top$ \\
& ($\Box_\mathbf{K}\phi\wedge\Box_\mathbf{K}\psi\rightarrow \Box_\mathbf{K}(\phi\wedge\psi)$) \\
\hline
$\Box_\mathbf{KD}$ & $\Box_\mathbf{KD}\top\rightarrow \top$ \\
& ($\Box_\mathbf{KD}\phi\wedge\Box_\mathbf{KD}\psi\rightarrow \Box_\mathbf{KD}(\phi\wedge\psi)$) \\
& $\neg\Box_\mathbf{KD}\bot\rightarrow \top$ \\
\hline
$\Box^a_\mathbf{HM}$ & $\Box^a_\mathbf{HM}\top\rightarrow \top$ \\
& ($\Box^a_\mathbf{HM}\phi\wedge\Box^a_\mathbf{HM}\psi\rightarrow \Box^a_\mathbf{HM}(\phi\wedge\psi)$) \\
\hline
$\Rightarrow_\mathbf{CK}$ & $(\phi\Rightarrow_\mathbf{CK}\top)\rightarrow\top$ \\
\hline
$\Rightarrow_\mathbf{CK_{CEM}}$ & $(\phi\Rightarrow_\mathbf{CK_{CEM}}\top)\rightarrow\top$ \\
\hline
\end{tabular}
\end{center}
\caption{Examplary tautologies used for simplification}
\label{fig:tauts}
\end{figure}
\end{footnotesize}
\subsection{Generalized Semantic Branching}
The technique of semantic branching~\cite{HorrocksPatelSchneider99} allows to ensure that created
sub-proofs are strictly disjoint. This prevents duplicate proofs of formulas
which might otherwise appear in both sub-proofs.
\subsubsection{Propositional Semantic Branching}
In the propositional case, there is just one branching rule, the conjunction rule.
A semantic version of this rule is shown in Figure~\ref{fig:synSemConj}.
The justification for replacing the standard conjunction rule by the rule for
semantic conjunction branching is simple:
\begin{lemma}
A sequent is provable by syntactic propositional branching iff it is
provable by semantic propositional branching.
\begin{proof}
This fact follows from the propositional tautology
\begin{quote}
$(A\wedge B)\leftrightarrow (A\wedge (A\rightarrow B))$.
\end{quote}
\end{proof}
\end{lemma}
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| c | c |}
\hline
Syntactic branching & Semantic branching \\
\hline
\inferrule{ \Gamma,A \\ \Gamma,B } { \Gamma,A \wedge B} & \inferrule{ \Gamma,A \\ \Gamma,\neg A,B } { \Gamma,A \wedge B}\\
\hline
\end{tabular}
\end{center}
\caption{Syntactic vs. Semantic branching on conjunctions}
\label{fig:synSemConj}
\end{figure}
\end{footnotesize}
\subsubsection{Modal Semantic Branching}
The general principle that can be extracted from propositional semantic branching
is a follows:
A syntactic branching rule
\begin{quote}
\centerline{\inferrule{\Gamma_1\\\ldots\\\Gamma_i\\\ldots\\\Gamma_n}{\Gamma}}
\end{quote}
may be (repeatedly) replaced by a `more semantic` branching rule
\begin{quote}
\centerline{\inferrule{\Gamma_1\\\ldots\\ \Gamma'_i\\\ldots\\\Gamma_n}{\Gamma}}
\end{quote}
where $\Gamma'_i=\bigwedge_{t\in T}\Gamma_t\rightarrow\Gamma_i$ for some
$T\subseteq\{1,\ldots,n\}\setminus\{i\}$.
The justification for this generalized semantic branching is as simple as in the propositional
case:
\begin{lemma}
A sequent is provable by syntactic modal branching iff it is
provable by semantic modal branching.
\begin{proof}
This fact follows from the propositional tautology
\begin{quote}
$(\bigwedge_{t\in T}\Gamma_t\wedge \Gamma_i) \leftrightarrow
(\bigwedge_{t\in T}\Gamma_t\wedge(\bigwedge_{t\in T}\Gamma_t\rightarrow \Gamma_i))$.
\end{quote}
\end{proof}
\end{lemma}
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l |}
\hline
Feature & Semantic Branching\\
\hline
$\Rightarrow_\mathbf{CK}$ & \inferrule{ A_0\leftrightarrow\ldots \leftrightarrow A_n \\ \neg(A_0\leftrightarrow\ldots \leftrightarrow A_n),\neg B_1,\ldots, \neg B_n,B_0 }
{ \Gamma,\bigwedge\limits_{i=1}^n(A_i\Rightarrow_\mathbf{CK} B_i)\rightarrow (A_0\Rightarrow_\mathbf{CK} B_0)} \\
\hline
$\Rightarrow_\mathbf{CK_{CEM}}$ & \inferrule{ A_0\leftrightarrow\ldots \leftrightarrow A_n \\ \neg(A_0\leftrightarrow\ldots \leftrightarrow A_n),B_0,\ldots, B_k, \neg B_{k+1},\neg B_n }
{ \Gamma,\bigwedge\limits_{i=k+1}^n(A_i\Rightarrow_\mathbf{CK_{CEM}} B_i)\rightarrow
\bigvee\limits_{j=0}^k(A_j\Rightarrow_\mathbf{CK_{CEM}} B_j)} \\
\hline
\end{tabular}
\end{center}
\caption{Specific semantic branching for examplary modal logics}
\label{fig:semBranch}
\end{figure}
\end{footnotesize}
\subsection{Generalized Dependency Directed Backtracking}
The technique of \emph{controlled backtracking} (also known as dependency directed
backtracking~\cite{HorrocksPatelSchneider99}) is in fact a special instance of caching: When this optimisation is
employed, each sequent $\Gamma$ depends on a set $\sharp(\Gamma)$ of
sequents (namely on those sequents which introduced any formula $\phi\in\Gamma$ into the proof tree).
Whenever a sequent turns out to be provable, its provability depends
on possibly several sequents. These sequents are called the respective
\emph{dependency set} of $\{\top\}$, denoted by $\sharp(\{\top\})$ (these sequents are
also known as the \emph{promotors} of the successful leaf).
We have yet to formally define dependency sets, but we will rely on the following
crucial fact:
\begin{lemma} Given a dependency set $\sharp(\{\top\})$ of a succesfull leaf, the first
sequent $\Gamma$ s.t. $\Gamma\in \sharp(\{\top\})$, is provable.
\label{fact:promtrs}
\end{lemma}
Due to Lemma~\ref{fact:promtrs}, it will
not be necessary to treat any open sequents between the current successful node in the
proof graph and the first node which is contained in the according dependency set.
To achieve this, a set of \emph{current} dependency sequents is used, and whenever a
sequent is provable, the current set of dependency sequents is defined as the set of
dependency sequents of $\{\top\}$. Now all those open sequents which
appear during the following backtracking through the proof tree and which
are created by a sequent which is \emph{not} in the current set of dependency states,
may be directly set to $provable$.
If however a node in the proof graph which is contained in the current set of dependency
states is reached, the current set of dependency states is set to $\emptyset$ and the
proof may continue as usual.
\begin{definition} Depending on the shape of a proof tree, $\sharp(\Gamma)$ is defined as follows:
\begin{itemize}
\item If $\Gamma$ is the root of the proof tree, $\sharp(\Gamma)=\Gamma$.
\item If $\Gamma$ is obtained from $\Gamma'$ by means of normalisation, saturation or simplification,
then $\sharp(\Gamma):=\sharp(\Gamma')$.
\item If $\Gamma$ is the only sequent in the premise of a rule application of a non-branching rule to
$\Gamma'$, then $\sharp(\Gamma):=\sharp(\Gamma')$.
\item If $\Gamma_1,\ldots,\Gamma_n$ are $n$ sequents from the premise of the rule
application of a branching rule to $\Gamma=\Gamma',\Gamma''$, s.t. $\Gamma_1,\ldots,\Gamma_n$
is constructed from $\Gamma''$,
the dependancy set of any formula $\phi\in \bigcup_{i\in\{1,\ldots,n\}} \Gamma_i$ is
defined as follows: if $\forall i\in\{1,\ldots,n\}. \phi\in \Gamma_i$, then $\sharp(\{\phi\}):=\sharp(\Gamma'')$,
else $\sharp(\{\phi\}):=\Gamma$.
\item Finally, $\sharp(\Gamma_1\cup \Gamma_2):=\sharp(\Gamma_1)\cup\sharp(\Gamma_2)$.
\end{itemize}
\end{definition}
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l | l |}
\hline
Feature & Modal Rule & Dependencies\\
\hline
$\Box_\mathbf{K}$ & \inferrule{ \overbrace{\bigwedge\nolimits_{i=1}^n A_i\rightarrow B}^{\equiv:\Gamma_1} }
{ \Gamma, \underbrace{\bigwedge\nolimits_{i=1}^n \Box_\mathbf{K} A_i\rightarrow \Box_\mathbf{K} B}
_{\equiv:\Gamma'}} & $\sharp(\Gamma_1):=\sharp(\Gamma')$ \\
\hline
$\Rightarrow_\mathbf{CK}$ & \inferrule{ \overbrace{A_0\leftrightarrow\ldots \leftrightarrow A_n}^{\equiv:\Gamma_1} \\
\overbrace{\neg B_1,\ldots \neg B_n,B_0}^{\equiv:\Gamma_2} }
{ \Gamma, \underbrace {\bigwedge\nolimits_{i=1}^n (A_i\Rightarrow_\mathbf{CK} B_i)\rightarrow
(A_0\Rightarrow_\mathbf{CK} B_0)}_{\equiv:\Gamma'}} & $\sharp(\Gamma_1,\Gamma_2):=\Gamma,\Gamma'$ \\
\hline
\end{tabular}
\end{center}
\caption{Propagation of dependencies over some examplary modal features}
\label{fig:depProp}
\end{figure}
\end{footnotesize}
Inituitively, a single application of for instance the modal rule of \textbf{K}
does not \emph{choose} any subformulas of its conclusionary sequent to generate new sequents
(this is already a consequence of the fact that this rule does not branch).
Hence any introduced formulas will depend on those formulas on which the conclusionary literals
already depended.
On the other hand, the modal rule of for instance \textbf{CK} selects some subformulas (the antecedents)
from its conclusionary sequent to be in the first sequent of the premise and others
(the consequents) to be in the second sequent of the premise, thus a choice is made and the
introduced formulas will directly depend on the conclusionary sequent.
The following Lemmas establish that dependency directed backtracking as defined above
is a sound optimisation technique for any coalgebraic modal logic:
\begin{lemma}
Assume an application of any (possibly branching) rule:
\begin{quote}
\centerline{\inferrule{\Gamma_1\\\ldots\\\Gamma_n}{\Gamma}}
\end{quote}
Assume a sequent $\Gamma'$ such that $\Gamma\notin\sharp(\Gamma')$,
but $\Gamma'\subseteq \Gamma_i$ for any $0<i\leq n$.
Then provability of $\Gamma'$ implies the provability of all sequents $\Gamma_i$ of
the premise of the rule.
\begin{proof} Let $\Gamma'$ be provable. Since $\Gamma\notin\sharp(\Gamma')$, we have a non-selecting
rule application (w.r.t. $\Gamma'$). For non-branching rules, the implication is trivial. For a
branching rule, it follows directly from the definition of $\sharp(\_)$ and the fact that one
$\Gamma_j$ contains $\Gamma'$, that all $\Gamma_j$ contain $\Gamma'$.
Hence all the sequents in the premise of the rule are provable.
\end{proof}
\label{lemma:provabilityPropagates}
\end{lemma}
%%\begin{lemma}
%%Assume an application of any (possibly branching) rule:
%%\begin{quote}
%%\inferrule{\Gamma_1\\\ldots\\\Gamma_n}{\Gamma}
%%\end{quote}
%%Assume a formula $\phi$ and its dependency set $\sharp(\{\phi\})$, s.t.
%%$\Gamma\notin\sharp(\{\phi\})$. If $\phi$ is contained in any
%%sequent of the premise, it is contained in all sequents of the premise.
%%\begin{proof}
%%By case distinction on the definition of $\sharp(\Gamma)$.
%%\end{proof}
%%\label{lemma:depAnyAll}
%%\end{lemma}
%%A promoting set of formulas is any subset of appearing conclusionary sequents $\Gamma$
%%of a rule application $\Gamma'_1 \ldots \Gamma'_n / \Gamma$ s.t. $\sharp(\Gamma)=\sharp(\Gamma'_i)$.
%%i.e. it is any subset of any $\Gamma$ as long as $\Gamma\notin\sharp(\{\top\})$
%%\begin{fact}
%%A sequent that contains a set of promoting formulas, is provable.
%%\label{fact:containProv}
%%\end{fact}
\begin{lemma}
Let the following be a (not yet fully explored) proof tree for $\Gamma$ (where $\Gamma^i_j$ denotes
the sequent number $j$ on level $i$; in case that $j>1$ and $i>1$, $\Gamma^i_j$ is assumed to be an
open sequent):
\begin{quote}
\centerline{\inferrule{\inferrule{\inferrule{\inferrule{\inferrule{\checkmark}{\Gamma^{n}_{1}}}{\ldots}}{\Gamma^{2}_{1}}
\\\ldots\\\Gamma^{2}_{i}}{\Gamma^{1}_{1}} \\ \ldots \\ \Gamma^{1}_{j}}{\Gamma}}
\end{quote}
Further, let $\sharp(\{\top\})$ denote the dependency set of the successful leaf. If for all $\Gamma^i_1$
with $0<i\leq n$, $\sharp(\{\top\})\not\subseteq\Gamma^i_1$,
and if $\sharp(\{\top\})\subseteq\Gamma$ (i.e. $\Gamma$ is the first sequent contained in the dependency
set of the successful leaf), then $\Gamma^1_1$ is provable (since any $\Gamma^i_j$ with $i>1$ is provable).
\begin{proof}
Lemma~\ref{lemma:provabilityPropagates} ensures, that the provability of the successful leaf
propagates to all the open sequents $\Gamma^i_j$ for $i,j>1$ (since $\sharp(\{\top\})\not\subseteq\Gamma^{i-1}_j$).
Thus we are not able to find any sequent of level $>1$ that is not provable.
%%We try to find any $\Gamma^i_j$ which is not provable. Since $\Gamma^n_1$ is provable, any
%%open sequent that could be not provable must have been created by a branching rule from
%%the sequent $\Gamma^{i-1}_1$. However, since $\sharp(\{\top\})\not\subseteq\Gamma^{i-1}_1$ and since
%%$\Gamma^i_1$ contains a promoting set of formulas,
%%a promoting set of formulas is by Lemma~\ref{lemma:depAnyAll} also contained in $\Gamma^i_j$,
%%thus $\Gamma^i_j$ is by Fact~\ref{fact:containProv} provable.
%%This shows that any $\Gamma^i_j$ with $i>1$ and in fact also $\Gamma^1_1$ is provable.
\end{proof}
\end{lemma}
To summarize, once we found a successful leaf $\Gamma^n_1$, it is not necessary to treat the whole sub-proof
which is induced by $\Gamma^1_1$, since $\Gamma^1_1$ is always provable in the above situation.
\subsection{Proof Formulas and efficient propagation}
Due to the inherent inefficiency of computing the propagation of provable
sequents $A$ (improvable sequents $E$) through the proof graph (all undecided
sequents have to be traversed in order to compute the necessary fix-points),
we devise the following more efficient method:
\begin{definition}
A \emph{position} $p\in Pos=\{c_1\ldots c_n\mid c_1,\ldots,c_n\in\mathbb{N}\}\cup\{[]\}$ is a finite
list of natural numbers.
A \emph{proof formula} is defined as follows (for $j,p\in Pos$):
\begin{quote}
$\mathcal{PF} \ni \psi_1,\ldots,\psi_n := a_j \mid \wedge \{\psi_1,\ldots,\psi_n\} \mid \vee \{\psi_1,\ldots,\psi_n\} \mid l_p$
\end{quote}
The subformula $\phi|_p$ of a proof formula $\phi$ at position $p=c_1\ldots c_n$ is defined
recursively. If $n=0$, then $\phi|_p=\phi$. If $n=1$ (i.e. $p=c_1$), then $p_2=[]$, otherwise
(i.e. $n>1$, $p=c_1c_2\ldots c_n$), $p_2=c_2\ldots c_n$.
\begin{itemize}
\item If $n>0$, $a_j|_p$ and $l_i|_p$ are undefined.
\item Let $\phi=\wedge \{\psi_1,\ldots,\psi_n\}$ or $\phi=\vee \{\psi_1,\ldots,\psi_n\}$. If $0<c_1\leq n$,
$\phi|_p=\psi_{c_1}|_{p_2}$; if $c_1>n$, $\phi|_p$ is undefined.
\end{itemize}
The partial \emph{indexing function} $\ind{\_}:Seq + Prem \rightharpoonup Pos$
maps sequents $\Gamma\in Seq$ or premises $\Sigma\in Prem$ from the defined
subset of its domain to a position.
We also introduce sets of provable positions $A_p\subseteq Pos$ and non-provable
positions $E_p\subseteq Pos$ as well as the set $tcs$ of positions that have been
expanded since the last propagation step and that are relevant to the propagation.
\end{definition}
When constructing the proof graph $g$ for a formula $\phi$, we build up a proof formula
$pf(g)$ in parallel, beginning with $pf(g_0)=a_{\ind{\{\phi\}}}$, $\ind{\_}$ undefined except
for $\ind{\{\phi\}}=[]$ and $A_p=E_p=tcs=\emptyset$.
\noindent\textbf{Expanding the proof formula:}
Say we expand sequent $\Gamma$, s.t. $g\stackrel{\Gamma}\rightarrow_E g'$ for $g'=exp(g,\Gamma)=(A',E',U',X',L_1',L_2')$.
This means that there are $n$ premises to $\Gamma$ (i.e. $|Rules(\Gamma)|=n$) and for each $(\Gamma,\Sigma_i) \in Rules(\Gamma)$,
$(\Gamma,\Sigma_i)\in L_1'$. Also, for each $(\Gamma,\Sigma_i) \in Rules(\Gamma)$, there is an $m_i$ s.t.
$|\{\Gamma_j\mid (\Sigma_i,\Gamma_j)\in Selections(\Gamma)\}|=m_i$ and each such $(\Sigma,\Gamma_j)$ is contained in $L_2'$.
In other words, $\Gamma$ has $n$ premises, each premise consists of $m_i$ sequents and the according
transitions are stored in $L_1'$ and $L_2'$.
The according changes to the proof formula and the indexing function are as follows:
\noindent First we expand the sequent $\Gamma$:
\begin{itemize}
\item Replace $a_{\ind{\Gamma}}$ with $\vee\{b_1,\ldots,b_n\}$.
\item For $0<i\leq n$, if $\ind{\Sigma_i}$ is defined (i.e. the premise was encountered before),
replace $b_i$ by $l_{\ind{\Sigma_i}}$. If $\ind{\Sigma_i}\in A_p\cup E_p$, add $\ind{\Gamma}$ to $tcs$.
\item For each remaining $b_i$ (i.e. for each new premise), set $\ind{\Sigma_i}=\ind{\Gamma}i$.
\item \emph{Optional:} If $n=1$, then $\vee\{b_1\}=b_1$ and $\ind{\Sigma_1}=\ind{\Gamma}$.
\item If $n=0$, then add $\ind{\Gamma}$ to $tcs$.
\end{itemize}
\noindent Then we expand all the premises $\Sigma_i$:
\begin{itemize}
\item Replace any $b_i$ with $\wedge\{a_1,\ldots,a_{m_i}\}$.
\item For $0<j\leq m_i$, if $\ind{\Gamma_j}$ is defined (i.e. the sequent was encountered before),
replace $a_j$ by $l_{\ind{\Gamma_j}}$. If $\ind{\Gamma_j}\in A_p\cup E_p$, add $\ind{\Sigma_i}$ to $tcs$.
\item For each remaining $a_j$ (i.e. for each new sequent), set $\ind{\Gamma_j}=\ind{\Sigma_i}j$.
\item \emph{Optional:} If $m_i=1$, then $\wedge\{a_1\}=a_1$ and $\ind{\Gamma_1}=\ind{\Sigma_i}$.
\item If $m_i=0$, then add $\ind{\Sigma_i}$ to $tcs$.
\item Replace any $a_j$ with $a_{\ind{\Gamma_j}}$.
\end{itemize}
\noindent\textbf{Propagation in the proof formula:}
Propagation of $A$ ($E$) through the proof formula is realized by iterative approximation of the
fixpoints.
Any of the rules from Figure~\ref{fig:propagation} is applied repeatedly for each $pj\in tcs$ until
no rule may be applied for this specific $pj$ any more, $pj$ is removed from $tcs$ afterwards.
\begin{footnotesize}
\begin{figure}[!h]
\begin{center}
\begin{tabular}{| l | l | l |}
\hline
Condition(s) & Changes to $A_p$ ($E_p$) & Changes to $tcs$\\
\hline
$\phi|_{pj}=\wedge\emptyset$ & add $pj$&\\
\hline
$\phi|_{pj}=\vee\emptyset$ & (add $pj$)&\\
\hline
$\exists q\in Pos.\phi|_{q}=l_{pj}$, $pj\in A_p$ & add $q$ & add $q$\\
\hline
$\exists q\in Pos.\phi|_{q}=l_{pj}$, $pj\in E_p$ & (add $q$) & add $q$\\
\hline
$\phi|_{p}=\wedge\{\psi_1,\ldots,\psi_n\}$, $\forall i\in\{1\ldots n\}. pi\in A_p$ & add $p$ & add $p$\\
\hline
$\phi|_{p}=\vee\{\psi_1,\ldots,\psi_n\}$, $\exists i\in\{1\ldots n\}. pi\in A_p$ & add $p$ & add $p$\\
\hline
$\phi|_{p}=\wedge\{\psi_1,\ldots,\psi_n\}$, $\exists i\in\{1\ldots n\}. pi\in E_p$ & (add $p$) & add $p$\\
\hline
$\phi|_{p}=\vee\{\psi_1,\ldots,\psi_n\}$, $\forall i\in\{1\ldots n\}. pi\in E_p$ & (add $p$) & add $p$\\
\hline
\end{tabular}
\end{center}
\caption{The simplification rules for propagation in proof formulas}
\label{fig:propagation}
\end{figure}
\end{footnotesize}
Propagation adds the positions of all newly added empty conjunctions (and disjunctions) to
$A_p$ ($E_p$) and propagates them through the formula. The set $tcs$ is empty after each
completed propagation step.
The set of all atoms $a_j$ that appear in $pf(g)$ is the relevant subset of the set $X$ of
unexpanded sequents of the proof graph.
\begin{lemma}
$\{\Gamma\in Seq\mid \ind{\Gamma}\in A_p\} = A$.
\begin{proof}
The constructed proof formula is a direct representation of the proof graph.
Repeated application of the rules from Figure~\ref{fig:propagation} iteratively approximates the
collection of fixpoints $A$ and stores the according positions in $A_p$.
\end{proof}
\end{lemma}
It follows that $\phi$ is provable iff $[]\in A_p$ and that $\phi$ is not provable otherwise. The
improved efficiency of the process of propagating in the proof formula turns propagation after
each expansion step into a feasible option.
\section{Conclusion}
We have applied the well known optimisation techniques of semantic branching and dependency directed
backtracking to coalgebraic logics and we have shown that the techniques generalize to all coalgebraic
modal logics in a natural way. This is especially interesting in the case of those modal logics
whose modal rule(s) introduce(s) additional branching (in contrast to more classic modal logics which only
branch on conjunctions).
As a second contribution, we have established a minimal representation of the structure of satisfiability
proofs of coalgebraic modal logics; this is achieved by introducing and justifying the usage of proof formulas
as a representation of the proof graph. Hence basic propagation becomes
a mere process of simplification of the respective proof formula starting at the successful or unsucessful
leaves and only traversing the needed parts of the proof structure.
The presented algorithm and the proposed optimisations have been successfully implemented as a part of the
experimental prover \emph{CoLoSS}. Additionally, the following optimization techniques have been implemented:
\begin{itemize}
\item restriction to maximal application of modal rules (when admissable),
\item irrelevance check for subformulas of polarity preserving modal logics,
\item heuristics (such as \emph{``most-appearing-first''} or \emph{``oldest-first''}).
\end{itemize}
The implementation shows reasonable performance especially for logics for
which few optimisations apart from those presented here exist.
However, detailled and relevant benchmarking of the examplary implementation in \emph{CoLoSS} is a complex task
(due to the amount and nature of different logics and optimisation techniques which are involved)
and subject to ongoing research.
\bibliographystyle{myabbrv}
\bibliography{coalgml}
\end{document}