PLAN--

[saga.git] / notation.tex

diff --git a/notation.tex b/notation.tex
index 81efb4996403bcdb2666c45b4c0e361c8b62a560..f8a512f4084c1fe92c33079deb8d72b33f1a10f5 100644 (file)
--- a/notation.tex
+++ b/notation.tex
@@ -165,7 +165,7 @@ introduced by Ackermann \cite{ackermann:function} in the context of
 computability theory. Its original purpose was to demonstrate that not every recursive
 function is also primitive recursive. At the first sight, it does not
 seem related to efficient algorithms at all. Its various inverses however occur in
-analyses of various algorithms and mathematical structures surprisingly often:
+analyses of algorithms and mathematical structures surprisingly often:
 We meet them in Section \ref{classalg} in the time complexity of the Disjoint Set Union
 data structure and also in the best known upper bound on the decision tree
 complexity of minimum spanning trees in Section \ref{optalgsect}. Another
@@ -174,13 +174,13 @@ Klazar's survey \cite{klazar:gdss}), but as far as we know, these are not otherw
 related to the topic of our study.
 
 Various sources differ in the exact definition of both the Ackermann's
-function and its inverse, but most of the differences are in factors that
+function and its inverse, but most of these differences are in factors that
 are negligible in the light of the giant asymptotic growth of the function.\foot{%
 To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity,
 Ackermann's function is rarely defined the same way twice. We would not presume to buck
 such a~well-established precedent. Here is a~slight variant.''}
 We will use the definition by double recursion given by Tarjan \cite{tarjan:setunion},
-which is predominant in the literature on graph algorithms:
+which is predominant in the literature on graph algorithms.
 
 \defn\id{ackerdef}%
 The \df{Ackermann's function} $A(x,y)$ is a~function on non-negative integers defined as follows:
@@ -207,8 +207,10 @@ A(4,3) &= A(3,A(4,2)) = A(3,4) = A(2,A(3,3)) = A(2,A(2,A(3,2))) = \cr
        &= A(2,A(2,4)) = 2\tower(2\tower 4) = 2\tower 65536. \cr
 }$$
 
-\para
-Three functions related to the inverse of the function~$A$ are usually considered:
+\paran{Inverses}%
+As common for functions of multiple parameters, there is no single function which
+could claim the title of the only true Inverse Ackermann's function.
+The following three functions related to the inverse of the function~$A$ are often considered:
 
 \defn\id{ackerinv}%
 The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by: