**On the Parsing of Deterministic Languages**

Ivan M. Havel, Michael A. Harrison

Pages: 525-548

DOI: 10.1145/321850.321851

A parsing method for strict deterministic grammars is presented and a technique for using it to parse any deterministic language is indicated. An important characterization of the trees of strict deterministic grammars is established. This is...

**Efficient Planarity Testing**

John Hopcroft, Robert Tarjan

Pages: 549-568

DOI: 10.1145/321850.321852

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and...

**An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph**

Philippe G. H. Lehot

Pages: 569-575

DOI: 10.1145/321850.321853

Given a graph H with E edges and N nodes, a graph G is sought such that H is the line graph of G, if G exists. The algorithm...

**A Search Procedure for Hamilton Paths and Circuits**

Frank Rubin

Pages: 576-580

DOI: 10.1145/321850.321854

A search procedure is given which will determine whether Hamilton paths or circuits exist in a given graph, and will find one or all of them. A combined procedure is given for both directed and undirected graphs. The search consists of creating...

**Linear Least Squares by Elimination and MGS**

Robert J. Plemmons

Pages: 581-585

DOI: 10.1145/321850.321855

An algorithm combining Gaussian elimination with the modified Gram-Schmidt (MGS) procedure is given for solving the linear least squares problem. The method is based on the operational efficiency of Gaussian elimination for LU...

**The Undecidability of the Existence of Zeros of Real Elementary Functions**

Paul S. Wang

Pages: 586-589

DOI: 10.1145/321850.321856

From Richardson's undecidability results, it is shown that the predictive “there exists a real number r such that G(r) = 0” is recursively undecidable for...

**Unit Refutations and Horn Sets**

L. Henschen, L. Wos

Pages: 590-605

DOI: 10.1145/321850.321857

The key concepts for this automated theorem-proving paper are those of Horn set and strictly-unit refutation. A Horn set is a set of clauses such that none of its members contains more than one positive literal. A strictly-unit refutation is a...

**A Human Oriented Logic for Automatic Theorem-Proving**

Arthur J. Nevins

Pages: 606-621

DOI: 10.1145/321850.321858

A deductive system is described which combines aspects of resolution (e.g. unification and the use of Skolem functions) with that of natural deduction and whose performance compares favorably with the best predicate calculus theorem...

**Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity**

James R. Slagle

Pages: 622-642

DOI: 10.1145/321850.321859

To prove really difficult theorems, resolution principle programs need to make better inferences and to make them faster. An approach is presented for taking advantage of the structure of some special theories. These are theories with...

**Optimal Order of One-Point and Multipoint Iteration**

H. T. Kung, J. F. Traub

Pages: 643-651

DOI: 10.1145/321850.321860

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2n-1 which use n evaluations of ƒ and no...

**Allocating Storage for Extendible Arrays**

Arnold L. Rosenberg

Pages: 652-670

DOI: 10.1145/321850.321861

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In...

**Testing for the Church-Rosser Property**

Ravi Sethi

Pages: 671-679

DOI: 10.1145/321850.321862

The central notion in a replacement system is one of a transformation on a set of objects. Starting with a given object, in one “move” it is possible to reach one of a set of objects. An object from which no move is possible is...

**An Analysis of Some Relationships Between Post and Boolean Algebras**

Anthony S. Wojcik, Gernot Metze

Pages: 680-696

DOI: 10.1145/321850.321863

The fundamentals of Post algebras are presented and Post and Boolean functions are examined. A functional representation is developed that facilitates the comparison of Post and Boolean algebras. Based on this representation, relationships...