ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 21 Issue 4, Oct. 1974

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...