scientific article; zbMATH DE number 3846121
correctness preserving transformationsDijkstra's algorithminverse functionmonotone nondecreasing unbounded functionpartition of set of natural numbers
Permutations, words, matrices (05A05) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to sequences, series, summability (40-01) Software, source code, etc. for problems pertaining to sequences, series, summability (40-04) Specification and verification (program logics, model checking, etc.) (68Q60)
[For the entire collection see Zbl 0507.00015.] For a monotone nondecreasing unbounded function f mapping the set of natural numbers \({\mathbb{N}}\) into itself the function \(f^{-1}\) can be defined by: \(f^{-1}(k):=\) the least n such that \(f(n)>k\). Due to the fact that f is unbounded \(f^{-1}\) is again a total nondecreasing function. The author ascribes to Lambek and Moser (no reference mentioned in the paper) the following two observations: 1) \((f^{-1})^{-1}=f\); 2) the sets of numbers \(\{i+f(i)| i\in {\mathbb{N}}\}\) and \(\{j+f^{-1}(j)| j\in {\mathbb{N}}\}\) form a partition of \({\mathbb{N}}\). In this note the author shows how both results can be obtained from investigating a simple program which computes \(f^{-1}\), given a subroutine for f; next its invariants are strengthened up to the point where a program is obtained which is entirely symmetric with respect to interchanging f and \(f^{- 1}\), from which both observations of Lambek and Moser are easily inferred. The author is quite pleased by this new application of correctness preserving transformations for proving mathematical results, but he shows to be aware of the fact that the same insight should be obtainable by more standard mathematical tools as well. In fact the basic idea could be expressed easily using the (formally inacceptable but very convincing) tool of a graph showing a suitable rectangular representation of the combined graphs of f and \(f^{-1}\) in the square grid \({\mathbb{N}}\times {\mathbb{N}}\), which is easily seen to be symmetric; moreover this graph contains a single point on every line \(x+y=cons\tan t\), and each such point is the endpoint of either a horizontal or a vertical edge (which yields the partition of \({\mathbb{N}}\) claimed by observation 2). Clearly Dijkstra's algorithm does nothing else than traversing this graph in the grid.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3315934)