chiark
/
gitweb
/
~ian
/
topbloke-formulae.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
7e6fe6e
)
strategy: ranking: proof of termination
author
Ian Jackson
<ijackson@chiark.greenend.org.uk>
Sun, 27 May 2012 18:49:10 +0000
(19:49 +0100)
committer
Ian Jackson
<ijackson@chiark.greenend.org.uk>
Sun, 27 May 2012 18:49:10 +0000
(19:49 +0100)
strategy.tex
patch
|
blob
|
history
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}
\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$,
\section{Traversal phase}
For each patch $C \in \allpatches$ in topological order by $\hasdep$,