Technical Reports

## 1984 UBC CS Technical Report Abstracts

TR-84-01 Scale-Based Descriptions of Planar Curves, March 1984 Alan K. Mackworth and Farzin Mokhtarian

The problem posed in this paper is the description of planar curves at varying levels of detail. Five necessary conditiong are imposed on any candidate solution method. Two candidate methods are rejected. A new method that uses well-known Gaussian smoothing techniques but applies them in a path-based coordinate system is described. By smoothing with respect to a path-length parameter the difficulties of other methods are overcome. An example shows how the method extracts the major features of a curve, at varying levels of detail, based on segmentation at zeroes of the curvature, $\kappa$. The method satisfies the five necessary criteria.

TR-84-02 On Gapping Grammars, April 1984 Harvey Abramson and Veronica Dahl

A Gapping Grammar (GG) has rewriting rules of the form: $\alpha_{1}, {\em gap}(x_{1}), \alpha_{2}, {\em gap}(x_{2}), \ldots, \alpha_{n-1}, {\em gap}(x_{n-1}), \alpha_{n} \rightarrow \beta$

$\alpha_{i} \epsilon V_{N} \bigcup V_{T}$

\{ {\em gap}(x_{1}),{\em gap}(x_{2}), \ldots,{\em gap}(x_{n-1}) \}\]

$x_{i} \epsilon V_{T}^{*}$

$\beta \epsilon V_{N}^{*} \bigcup V_{T}^{*} \bigcup G^{*}$ where $V_{T}$ and $V_{N}$ are the terminal and non-terminal vocabularies of the Gapping Grammar. Intuitively, a GG rule allows one to deal with unspecified strings of terminal symbols called {\em gaps}, represented by $x_{1}, x_{2}, \ldots, x_{n-1}$, in a given context of specified terminals and non-terminals, represented by $\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}$ and then to distribute them in the right hand side $\beta$ in any order. GG's are a generalization of Fernando Pereira's {\em Extrapontion Grammars} where rules have the form (using our notation ): \begin{eqnarray*} \alpha_{1},{\em gap}(x_{1}), \alpha_{2}, {\em gap}(x_{2}), \ldots, {\em gap}(x_{n-1}), \alpha_{n} \rightarrow \\ \beta, {\em gap}(x_{1}), {\em gap}(x_{2}), \ldots, {\em gap}(x_{n-1}) \end{eqnarray*} i.e., gaps are rewritten in their sequential order in the rightmost positions of the rewriting rule. In this paper we motivate GG's by presenting grammatical examples where XGs are not adequate and we describe and discuss alternative implementations of GGs in logic.

TR-84-03 Definite Clause Translation Grammars, April 1984 Harvey Abramson

In this paper we introduce Definite Clause Translation Grammars, a new class of logic grammars which generalizes Definite Clause Grammars and which may be thought of as a logical implementation of Attribute Grammars. Definite Clause Translation Grammars permit the specification of the syntax and semantics of a language: the syntax is specified as in Definite Clause Grammars; but the semantics is specified by one or more semantic rules in the form of Horn clauses attached to each node of the parse tree (automatically created during syntactic analysis), and which control traversal(s) of the parse tree and computation of attributes of each node. The semantic rules attached to a node constitute therefore, a local data base for that node. The separation of syntactic and semantic rules is intended to promote modularity, simplicity and clarity of definition, and ease of modification as compared to Definite Clause Grammars, Metamorphosis Grammars, and Restriction Grammars.

TR-84-04 Classes of Numeration Models of $\lambda$-Calculus, April 1984 K and Akira a

In [4] the reflexive structures in the category of numeration were studied. It was shown that every numerated reflexive set forms a numeration model of $\lambda$-calculus''. In this short note we formalize the concept of numeration models of $\lambda$-calculus, and study several interesting subclasses. Even though the class of numeration models does not coincide with the class of numerated reflexive sets, we can show that the class of numeration models with $\lambda$-definability'' property is equivalent to the class of numerated reflexive sets with $\lambda$-representability'' property. Through this we observe relation between $\lambda$-definability and acceptability of numerations discussed in [5].

TR-84-05 On The Adequacy of Predicate Circumscription For Closed-World Reasoning, September 1984 David W. Etherington, Robert E. Mercer and Raymond Reiter

We focus on McCarthy's method of predicate circumscription in order to establish various results about its consistency, and about its ability to conjecture new information. A basic result is that predicate circumscription cannot account for the standard kinds of default reasoning. Another is that predicate circumscription yields no new information about the equality predicate. This has important consequences for the unique names and domain closure assumptions.

TR-84-06 A Unified Approach to the Geometric Rectification of remotely Sensed Imagery, May 1984 Frank Hay-Chee Wong

Many applications of remotely sensed digital imagery require images that are corrected for geometric distortions. It is often desirable to rectify different types of satellite imagery to a common data base. A high throughput rectification system is required for commercial application. High geometric and radiometric precision must be maintained.

The thesis has accomplished the following tasks: \begin{enumerate} \item The sensors used to obtain remotely sensed imagery have been investigated and the associated geometric distortions inherent with each sensor are identified. \item The transformation between image coordinates and datum coordinates has been determined and the values of the parameters in the transformation are estimated. \item A unified rectification approach has been developed, for all types of remotely sensed digital imagery, which yields a high system throughput. \item Use of digital terrain models in the rectification process to correct for relief displacement has been incorporated. \item An efficient image interpolation algorithm has been developed. This algorithm takes into account the fact that imagery does not always correspond to sampling on a uniform grid. \item The applications of rectified imagery such as mosaicking and multisensor integration have been studied. \item Extension of the rectification algorithm to a future planetary mission has been investigated. \end{enumerate}

The sensors studied include TIROS-N Landsat-1, -2 and -3 multispectral scanners, Seasat synthetic aperture radar, Landsat-4 thematic mapper and SPOT linear array detectors. Imagery from the last two sensors is simulated.

TR-84-07 Numeration models of $\lambda$B-Calculus, May 1984 K and Akira a

Numeration models of extensional $\lambda$-calculus have been studied (see [5,7]). In this paper, we study numeration models of $\lambda \beta$-calculus. Engeler's graph algebra construction [3] is applied to the category of numerations and is used as a tool to obtain numeration models of $\lambda \beta$-calculus. Several classes of numeration models are studied and several examples of them are presented.

TR-84-08 RF-Maple: A Logic Programming Language with Functions, Types \& Concurrency, April 1984 Paul J. Voda and Benjamin Yu

Currently there is a wide interest in the combination of functional programs with logic programs. The advantage is that both the compostion of functions and non-determinism of relations can be obtained. The language RF-Maple is an attempt to combine logic programming style with functional programming style. RF'' stands for Relational and Functional''. It is a true union of a relational programming language R-Maple and a functional programming language F-Maple.

R-Maple is a concurrent relational logic programming language which tries to strike a balance between control and meaning. Sequential and parallel execution of programs can be specified in finer details than in Concurrent Prolog. R-Maple uses explicit quantifiers and has negation. As a result, the declarative reading of R-Maple programs is never compromised by the cuts and commits of both Prologs.

F-Maple is a very simple typed functional programming language (it has only four constructs) which was designed as an operating system at the same time. It is a syntactically extensible language where the syntax of types and functions is entirely under the programmer's control.

In combining the two concepts of R-Maple and F-Maple producing RF-Maple, the readability of programs and the speed of execution are improved. The latter is due to the fact that many relations are functional and therefore, do not require backtracking. We believe its power as well as its expressiveness and ease of use go a little beyond the possibilities of the currently available languages.

TR-84-09 A View of Programming Languages as Symbiosis of Meaning \& Control, May 1984 Paul J. Voda

TR-84-10 Photometric Method for Determining Shape from Shading, July 1984 R. J. Woodham

A smooth opaque object produces an image in which brightness varies spatially even if the object is illuminated evenly and is covered by a surface material with uniform optical properties. Photometric methods relate image irradiance to object shape and surface material using physical models of the way surfaces reflect light. A reflectance map allows image irradiance to be written as a function of surface orientation, for a given surface material and light source distribution. Shape from shading algorithms use a reflectance map to analyze what is seen.

The development of photometric methods for determining shape from shading is discussed, beginning with examples from lunar astronomy. The results presented delineate shape information that can be determined from geometric measurements at object boundaries from shape information that can be determined from intensity measurements over sections of smooth surface. Recent work of Ikeuchi and Horn is presented which relaxes the requirement that the image irradiance equation be satisfied exactly. Instead, the image irradiance equation specifies one constraint that is combined with another constraint derived from general surface smoothness criteria. Shape from shading is expressed as a constrained minimization problem.

Another method uses multiple images in a technique called photometric stereo. In photometric stereo, the illumination is varied between successive images while the viewing direction remains constant. Multiple images obtained in this way provide enough information to determine surface orientation at each image point, without smoothness assumptions.

TR-84-11 Definite Clause Translation Grammars \& the Logical Specification of Data Types as Unambiguous Context Free Grammars, August 1984 Harvey Abramson

Data types may be considered as unambiguous context free grammars. The elements of such a data type are the derivation trees of sentences generated by the grammars. Furthermore, the generators and recognizers of non-terminals specified by such grammars provide the composition and decomposition operators which can be used to define functions or predicates over such data types. We present a modification of our Definite Clause Translation Grammars (Abramson 1984) which is used to logically specify data types as unambiguous context free grammars. For example, here is a grammatical specification of binary trees: \begin{center} string.$\\ "(" , left :tree, " ,", right :tree, " )".$ \end{center} The decomposition operators'', left, right, and (implicitly) string, are semantic attributes generated by the compiler which translates these grammar rules to Prolog clauses; these operators, together with the parser for $tree$s, and the predicates $leaf$ and $branch$, can be used to construct more complex predicates over the data type $tree$. We show how such grammars can be used to impose a typing system on logic programs; and indicate how such grammars can be used to implement Kaviar, a functional programming language based on data types as context tree grammars.

TR-84-12 A Generalization of the Frank Matrix, January 1984 James M. Varah

In this paper, we give a generalization of the well-known Frank matrix and show how to compute its eigensystem accurately. As well, we attempt to explain the ill-condition of its eigenvalues by treating it as a perturbation of a defective matrix.

TR-84-13 Stability of Collocation at Gaussian Points, October 1984 Uri Ascher and G. Bader

Symmetric Runge-Kutta schemes are particularly useful for solving stiff two-point boundary value problems. Such A-stable schemes perform well in many cases, but it is demonstrated that in some instances the stronger property of algebraic stability is required.

A characterization of symmetric, algebraically stable Runge-Kutta schemes is given. The class of schemes thus defined turns out not to be very rich: The only collocation schemes in it are those based on Gauss points, and other schemes in the class do not seem to offer any advantage over collocation at Gaussian points.

TR-84-14 Photometric Method for Radiometric Dorrection of Multispectral Scanner Data, October 1984 R. J. Woodham and T. K. Lee

Radiometric correction of multispectral scanner data requires physical models of image formation in order to deal with variations in topography, scene irradiance, atmosphere and viewing conditions. The scene radiance equation is more complex for rugged terrain than for flat terrain since it must model elevation, slope and aspect dependent effects. A simple six parameter model is presented to account for differential amounts of solar irradiance, sky irradiance and path radiance across a scene. The model uses the idea of a reflectance map to represent scene radiance as a function of surface orientation. Scene radiance is derived from the bidirectional reflectance distribution function (BRDF) of the surface material and a distribution of light sources. The sun is treated as a collimated source and the sky is treated as a uniform hemispherical source. The atmosphere adds further complication and is treated as an optically thin, horizontally uniform layer.

The required six parameters account for atmospheric effects and can be estimated when a suitable digital terrain model (DTM) is available. This is demonstrated for Landsat MSS images using a test site near St. Mary Lake in southeastern British Columbia. An intrinsic surface albedo is estimated at each point, independent of how that point is illuminated and viewed.

It is argued that earlier conclusions about the usefulness of the Lambertian assumption for the radiometric correction of multispectral scanner data were premature. Correction methods proposed in the literature fail even if the surface is Lambertian. This is because sky irradiance is significant and must be dealt with explicitly, especially for slopes approaching the grazing angle of solar incidence.

TR-84-15 Scale-Based Description and Recognition of Planar Curves and Two-Dimensional Shapes, October 1984 Farzin Mokhtarian and Alan K. Mackworth

The problem of finding a description for planar curves and two-dimensional shapes at varying levels of detail and matching two such descriptions is posed and solved in this paper. A number of necessary criteria are imposed on any candidate solution method. Path-based Gaussian smoothing techniques are applied to the curve to find zeroes of curvature at varying levels of detail. The result is the generalized scale space' image of a planar curve which is invariant under rotation, uniform scaling and translation of the curve. These properties make the scale space image suitable for matching. The matching algorithm is a modification of the uniform cost algorithm and finds the lowest cost match of contours in the scale space images. It is argued that this is preferable to matching in a stable scale of the curve because no such scale may exist for a given curve. This technique is applied to register a Landsat aerial image of the Strait of Georgia, B.C. (manually corrected for skew) to a map containing the shorelines of an overlapping area.

TR-84-16 A Theory of Schema Labelling, June 1984 William S. Havens

Schema labelling is a representation theory which focuses on composition and specialization as two major aspects of machine perception. Previous research in computer vision and knowledge representation have identified computational mechanisms for these tasks. We show that the representational adequacy of schema knowledge structures can be combined advantageously with the constraint propagation capabilities of network consistency techniques. In particular, composition and specialization can be realized as mutually- interdependent cooperative processes which operate on the same underlying knowledge representation. In this theory, a schema is a generative representation for a class of semantically related objects. Composition builds a structural description of the scene from rules defined in each schema. The scene description is represented as a network consistency graph which makes explicit the objects found in the scene and their semantic relationships. The graph is hierarchical and describes the input scene at varying levels of detail. Specialization applies network consistency techniques to refine the graph towards a global scene description. Schema labelling is being used for interpreting hand-printed Chinese characters [10], and for recognizing VLSI circuit designs from their mask layouts [2].

TR-84-17 Collocation for Two-Point Boundary Value Problems Revisited, November 1984 Uri Ascher

Collocation methods for two-point boundary value problems for higher order differential equations are considered. By using appropriate monomial bases, we relate these methods to corresponding one-step schemes for 1st order systems of differential equations. This allows us to present the theory for nonstiff problems in relatively simple terms, refining at the same time some convergence results and discussing stability. No restriction is placed on the meshes used.

TR-84-18 The Design of a Distributed Interpreter for Concurrent Prolog, November 1984 Chun Man Tam

Prolog is a programming language based on predicate logic. Its successor, Concurrent Prolog, was designed to meet the needs of a multiprocessing environment to the extent that it may be desirable as a succinct language for writing operating systems. Here, we demonstrate the feasibllity of implementing a distributed interpreter for Concurrent Prolog using traditional programming tools under a multiprocess structuring methodology. We will discuss the considerations that must be made in a distributed environment and how the constructs of the language may be implemented. In particular, several subtle pitfalls associated with the implementation of read-only variables and the propagation of new bindings will be illustrated. In addition, a modification to Shapiro's treatment of read-only variables is proposed in an attempt to `clean up'' the semantics of the language.

(The discussion will centre around a primitive version of an interpreter for the language written in Zed (a language similar to C) on an Unix-like operating system, Verex. Although a brief introduction of Prolog and Concurrent Prolog will be given, it is assumed that the reader is familiar with the paper \underline{A Subset of Concurrent Prolog and Its Interpreter} by E.Y. Shapiro [Shapiro83].)

TR-84-19 Natural Deduction Based Set Theories: A New Resolution of the Old Paradoxes, January 1984 Paul C. Gilmore

The comprehension principle of set theory asserts that a set can be formed from the objects satisfying any given property. The principle leads to immediate contradictions if it is formalized as an axiom scheme within classical first order logic. A resolution of the set paradoxes results if the principle is formalized instead as two rules of deduction in a natural deduction presentation of logic. This presentation of the comprehension principle for sets as semantic rules, instead of as a comprehension axiom scheme, can be viewed as an extension of classical logic, in contrast to the assertion of extra-logical axioms expressing truths about a pre-existing or constructed universe of sets. The paradoxes are disarmed in the extended classical semantics because truth values are only assigned to those sentences that can be grounded in atomic sentences.

TR-84-20 An Alternative Characterization of Precomplete Numerations, November 1984 K and Akira a

Er\u{s}ov [1] characterized precomplete numerations as those numerations which satisfy the 2nd recursion theorem. In this short note we show that they are exactly those numerations which satisfy the strongest form of the 2nd recursion theorem.

TR-84-21 The File System of a Logic Operating System, November 1984 Anthony J. Kusalik

This paper describes the file system of an operating system for a logic inference machine. The file system is composed of a file system device and a collection of file system servers. The former provides the basic services of creation, access (reading or writing), removal, and stable storage of files. It realizes a simple, though powerful model: a file store as a special type of name server maintaining associations between identifiers and entities. A file is then a pair, $<$file name, file content$>$, of terms. Clients gain access to a file by sharing the file content term with the file system device. Reading the file corresponds to examination of the term; writing, to instantiation. There is no need of explicit read or write operations, or of file closure. File system servers enhance or modify this basic file abstraction. They can provide features of more conventional file systems, such as hierarchical directories or fixed, structured file formats.

Concurrent Prolog is assumed as the underlying machine language and the operating system implementation language. However, the ideas are also applicable to other parallel logic programming languages, such as PARLOG.

As a prerequisite to describing the file system, the Concurrent Prolog machine model is presented, as well as an overview of the entire operating system design.

TR-84-22 Recursion Theorems and Effective Domains, January 1984 K and Akira a

Every acceptable numbering of an effective domain is complete. Hence every effective domain admits the 2nd recursion theorem of Er\u{s}ov [1]. On the other hand for every effective domain, the 1st recursion theorem holds. In this note, we establish that for effective domains, the 2nd recursion theorem is strictly more general than the 1st recursion theorem, a generalization of an important result in recursive function theory.

TR-84-23 Nystroms Method vs. Founier Tupe Methods for the Numerical Solution of Integral Equations, December 1984 M Trummer and red R.

It is shown that Nystrom's method and Fourier type methods produce the same approximation to a solution of an integral equation at the collocation points for Nystrom's method. The quadrature rule for numerical integration must have these collocation points as abscissa.

TR-84-24 An Efficient Implementation of a Conformal Mapping Method Using the Szego Kernel, December 1984 Manfred R. Trummer

An implementation, based on iterative techniques, of a method to compute the Riemann mapping function is presented. The method has been recently introduced by N. Kerzman and the author; it expresses the Szego kernel as the solution of an integral equation of the second kind. It is shown how to treat symmetric regions. The algorithm is tested on five examples. The numerical results show that the method is competitive, with respect to accuracy, stability, and efficiency.

TR-84-25 Theory of Pairs, Part I: Provably Recursive Functions, January 1984 Paul J. Voda