strategy: ranking: proof of termination

[topbloke-formulae.git] / strategy.tex

diff --git a/strategy.tex b/strategy.tex
index a1632cb42602b161221d7eafd774976e5f1cba68..e2bcf46fc50dfa768b2108b930b9728a0d39cae7 100644 (file)
--- 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$,