From: Ian Jackson
Date: Sun, 27 May 2012 18:49:10 +0000 (+0100)
Subject: strategy: ranking: proof of termination
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke-formulae.git;a=commitdiff_plain;h=be08dfe44764573fcf4d903dbe74576e3762ee04
strategy: ranking: proof of termination
---
diff --git a/strategy.tex b/strategy.tex
index a1632cb..e2bcf46 100644
--- a/strategy.tex
+++ b/strategy.tex
@@ -212,6 +212,18 @@ and corresponding merge bases $M^{\pcn}_i = M_i$.
\end{itemize}
+\subsection{Proof of termination}
+
+$\alg{Rank-Recurse}(\pc)$ recurses but only downwards through the
+finite graph $\hasdirdep$, so it must terminate.
+
+The whole ranking algorithm iterates but each iteration involves
+adding one or more patches to $\allpatches$. Since there are
+finitely many patches and we never remove anything from $\allpatches$
+this must complete eventually.
+
+$\qed$
+
\section{Traversal phase}
For each patch $C \in \allpatches$ in topological order by $\hasdep$,