Technical Reports

## 1977 UBC CS Technical Report Abstracts

TR-77-01 On the Invariance of the Interpolation Points of the Discrete l1-approximation, February 1977 Uri Ascher, 14 pages

Consider discrete $l_{1}$-approximations to a data function $f$, on some finite set of points $X$, by functions from a linear space of dimension $m < \infty$. It is known that there always exists a best approximation which interpolates $f$ on a subset of $m$ points of $X$. This does not generally hold for the continuous'' $L_{1}$-approximation on an interval, as we show by means of an example.

We investigate the invariance of the interpolation points of the discrete $l_{1}$-approximation under a change in the approximated function. Conditions are given, under which the interpolant to a function $g$ on a set of best $l_{1}$ points'' of a function $f$ is a best $l_{1}$-approximant to $g$. Additional results are then obtained for the particular case of spline $l_{1}$-approximation.

TR-77-02 On Reading Sketch Maps, May 1977 A. K. Mackworth, 28 pages

A computer program, named MAPSEE, for interpreting maps sketched freehand on a graphical data tablet is described. The emphasis in the program is on discovering cues that invoke descriptive models which capture the requisite cartographic and geographic knowledge. A model interprets ambiguously the local environment of a cue. By resolving these interpretations using a new network consistency algorithm for n-ary relations, MAPSEE achieves an interpretation of the map. It is demonstrated that this approach can be made viable even though the map cannot initially be properly segmented. A thoroughly conservative, initial, partial segmentation is described. The effects of its necessary deficiencies on the interpretation process are shown. The ways in which the interpretation can refine the segmentation are indicated.

TR-77-03 Computers and the Mechanication of Judgement, April 1977 A. Mowshowitz

Computer-based information systems are playing an increasingly important role in organizational decision-making. Although high level managers are not in imminent danger of extinction, many managerial functions have been substantially altered or replaced by computer systems. These developments are viewed here as an extension of bureaucratic rationalism, the peculiar innovative spirit of large-scale enterprise. Advanced information technology in large organizations appears to promote the elaboration of hierarchically structured control mechanisms, and to further the resolution of complex decision tasks into routine procedures. Since the technology could in principle be used to support radically different modes of organization, an explanation must be sought in the evolution of bureaucracy.

Efforts to improve productivity and efficiency affect the distribution of power and authority, so that technical innovation in management raises serious ethical and political problems. Historical observations and empirical results point to a contradiction between bureaucratic rationalism and individual autonomy. This contradiction is revealed in the impact of computer applications on the conduct of certain classes of decision-makers. Policy issues are transformed into technical questions, and opportunities for exercising independent judgment are diminished as analysis of means displaces exploration of ends. I will attempt to show how this transformation is accomplished in the rationalization of functions which typically accompanies the introduction of computer systems.

TR-77-04 A New Notation for Derivations, June 1977 J. L Baker

Ordered directed graphs (generalizing ordered trees) are defined and used in a new formal definition of grammatical derivation. The latter is shown equivalent to the currently accepted definition. The new scheme is illustrated by detailed proofs of two familiar results: the equivalence of the notions context-sensitive'' and length-nondecreasing'' as applied to grammars, and an important lemma in the theory of deterministic context-free parsing.

TR-77-05 Lexic Scanners, June 1977 R. A. Fraley

A fast algorithm for a general purpose scanner is presented. It includes a mechanism for permitting user-defined special character tokens. The scanner is able to separate strings of special characters without imposing arbitrary spacing rules on the programmer. An analysis shows that most special character tokens from selected languages could be handled properly by the scanner, even if they were in the same language. Many of the omitted tokens could be confused for combinations of operators, demonstrating the utility of the scanner for preventing lexical ambiguity. The special character analysis is extended to other classes of tokens.

TR-77-06 Unlanguage Grammars and Their Uses, August 1977 R. A. Fraley

A new technique is presented for using context free grammars for the definition of programming languages. Rather than accumulating a number of specialized statement formats, generalized productions specify the format of all statements. A sample unlanguage grammar is presented, and the use of this grammar is described. Some of the difficulties in parsing the language are described.

TR-77-07 Simulation in a Theory of Programmable Machines, July 1977 J. L. Baker

In a theory of machines controlled by programs, automata-theoretic simulation can be presented simply and directly, and can be understood as an aspect of the algebraic structure of such machines.

Here the notions of product and homomorphism of devices in such a theory are presented, along with a notion of (computational) reducibility of one device to another. Simulation in the automata-theoretic sense is formally defined, and its validity as a technique for proving reducibility established uniformly.

The notions of device, product, homomorphism, and reducibility are then extended to model costs of computation evaluated a posteriori (in the manner of concrete complexity studies), and the validity of simulation as a proof technique established in this extended setting.

TR-77-08 Coroutines in a Theory of Programmable Machines, July 1977 J. L. Baker

It is shown that, in the author's theory of programmable machines, the composition of functions computable by programs is in some important cases computable by a program constructed to use the given programs as coroutines. To illustrate the utility of this result, a characterization of the full AFLs in terms of programmable machines is established with its help.

TR-77-09 *FUNL Semantics Work Towards UNCOL, August 1977 R. A. Fraley

An intermediate semantics language, applicable to many source languages and machines, is proposed in this paper. Over its domain and range it promises many of the advantages of the original UNCOL project. Data abstraction is used to hide machine features. The language hides from the source compiler all implementation representations and conventions, except for a few descriptive constants. The semantic model is espandable by means of a library. Higher level semantic models may be implenented in FUNL, reducing compiler writing effort.

TR-77-10 A Simulation Study of Adaptive Scheduling Policies in Interactive Computer Systems, November 1977 Samuel T. Chanson and C. Bishop

A number of adaptive processor scheduling algorithms (i.e, those that will adjust to varying workload conditions so as to maximize performance) for interactive computing systems are examined and new ones proposed. The performance indices chosen are the mean response time and the mean of those response times less than the x percentile for some x. The robustness of the algorithms are studied and a brief discussion on the overheads involved is included.

Simulation is used throughout the study and because of this, the simulator and the workload used are described in some detail. The target machine is a somewhat simplied version of the UBC system which operates an IBM 370/168 running under MTS (Michigan Terminal System). The UBC system is principally used interactively.

TR-77-11 Duals of Intuitionistic Tableaus, October 1977 G. Criscuolo and R. Tortora

We present a dual version of the intuitionistic Beth tableaus with signed formulas introduced in Fitting $\mid9\mid$ proving their correctness and completeness with respect to Kripke models.

TR-77-12 Assaulting the Tower of Babel: Experiences with a Translator Writing System, November 1977 Harvey Abramson, W. F. Appelbe and M. S. Johnson, 11 pages

TRUST is a translator writing system (TWS) which evolved from several available TWS components, including an LR (k) parser generator and a lexical scanner generator. The design and historical development of TRUST are briefly presented, but the paper is primarily concerned with relating critically the experiences gained in applying the TWS to various practical software projects and to the classroom environment. These experiences lead to a discussion of how a modular TWS should be designed and implemented.

TR-77-13 A Collocation Solver for Mixed Order Systems of BVP's, November 1977 Uri Ascher, J. Christiansen and R. D. Russell

(Abstract not available on-line)

TR-77-14 Evaluation of B-splines for Solving Systems of Boundary Value Problems, November 1977 Uri Ascher and R. D. Russell

A general purpose collocation code COLSYS has been written, which is capable of solving mixed order systems of multi-point boundary value ordinary differential equations. The peicewise polynomial solution is given in terms of a B-spline basis.

Efficient implementation of algorithms to calculate with B-splines is a necessary condition for the code to be competitive. Here we describe these algorithms and the special features incorporated to take advantage of the specific environment in which they are used.

TR-77-15 Deductive Question-Answering on Relational Databases, November 1977 R. Reiter

(Abstract not available on-line)

TR-77-16 On Closed World Data Bases, October 1977 R. Reiter

Deductive question-answering system generally evaluate queries under one of two possible assumptions which we in this paper refer to as the open and closed world assumptions. The open world assumption corresponds to the usual first order approach to query evaluation: Given a data base DB and a query Q, the only answers to Q are those which obtain from proofs of Q given DB as hypotheses. Under the closed world assumption, certain answers are admitted as a result of failure to find a proof. More specifically, if no proof of a positive ground literal exists, then the negation of that literal is assumed true.

In this paper, we show that closed world evaluation of an arbitrary query may be reduced to open world evaluation of so-called atomic queries. We then show that the closed world assumption can lead to inconsistencies, but for Horn data bases no such inconsistencies can arise.

Presented at the Workshop on Logic and Data Bases, Toulouse, France, November 16-18, 1977.

TR-77-18 Some Connections Between the Minimal Polynomial and the Automorphism, November 1977 A. Mowshowitz, G. Criscuolo, R. Tortora and Chung-Mo Kwok

The relationship between the spectrum and the automorphism group of a graph is probed with the aid of the theory of finite group representations. Three related topics are explored: l) graphs with non-derogatory adjacency matrix, 2) point-symmetric graphs, and 3) an algorithm for constructing the automorphism group of a prime, point-symmetric graph. First, we give an upper bound on the order of the automorphism group of a graph with non-derogatory adjacency matrix; and show, in a special case, that the degree of each irreducible factor of the minimal polynomial has a natural interpretation in terms of the automorphism group. Second, we prove that the degree of the minimal polynomial of a point-symmetric graph is bounded above by the number of orbits of the stabilizer of any given element. For point-symmetric graphs with a prime number of points, we exhibit a formula linking the degree of the minimal polynomial with the order of the group. Finally, we give a simple algorithm for constructing the automorphism group of a point-symmetric graph with a prime number of points.

TR-77-19 Topics in Discourse Analysis, November 1977 J. E. Davidson

This thesis deals with the theory and analysis of connected English discourse.

The abstract theory of discourse, and its distinguishing characteristics, are discussed. Some problems in computer analysis of discourse are delineated; a method of analysis, based on a modified system of predictions, is introduced, and illustrated with examples from simple stories. A program embodying these concepts is described. Finally, possibilities for discourse, and its place in computational linguistics, are discussed, and directions for further work indicated.

TR-77-20 On the Separation of Two Matrices, December 1977 Jim M. Varah

The sensitivity of the solution $X$ to the matrix equation C$is primarily dependent on the quantity sep$(A,B)$introduced by Stewart in connection with the resolution of invariant subspaces. In this paper, we discuss some properties of sep$(A,B)$, give some examples to show how very small it can be for seemingly harmless X^{(k)}B + C$ for solving the matrix equation.