Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 13 Issue 2, April 1966

Sequential Processing Machines (S.P.M) Analyzed With a Queuing Theory Model
Leonard Kleinrock
Pages: 179-193
DOI: 10.1145/321328.321329
Results are obtained for a model of many processors operating in series. The results are obtained directly by recognizing that a sequential processing may be viewed as a cyclic queue. Exact results are given for two sequential processing stages...

BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces
Ruth A. Weiss
Pages: 194-204
DOI: 10.1145/321328.321330
BE VISION is a package of FORTRAN programs for drawing orthographic views of combinations of plane and quadric surfaces. As input, the package takes rectangular coordinate equations specifying the surfaces plus a three-angle specification of the...

A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
John T. Welch, Jr.
Pages: 205-210
DOI: 10.1145/321328.321331
A method of finding every cycle of an undirected linear graph by computation, rather than search, is presented. The method consists of three algorithms. The first produces a fundamental set of cycles from which all others can be generated. The...

Analysis of Graphs by Connectivity Considerations
C. V. Ramamoorthy
Pages: 211-222
DOI: 10.1145/321328.321332
Discrete sequential systems, such as sampled data systems, discrete Markov processes, linear shift register generators, computer programs, sequential code generators, and prefixed comma-free codes, can be represented and studied in a uniform...

The Solvability of the Derivability Problem for One-Normal Systems
Stephen A. Cook
Pages: 223-225
DOI: 10.1145/321328.321333
A one-normal system is a Post production system on a finite alphabet {s1, s2, · · ·, s&sgr;} with productions...

A Theory of Computer Instructions
Ward Douglas Maurer
Pages: 226-235
DOI: 10.1145/321328.321334
A computer is a set M (the memory), a set B, a class of maps S: MB, known as states, and a class @@@@ of maps T: @@@@ → @@@@,...

On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
Kojiro Kobayashi, Shigeru Sekiguchi
Pages: 236-261
DOI: 10.1145/321328.321335
The problem of deciding predicates concerned with m-tuples of words by means of 2-way multitape finite automata is considered. In general, more than m tapes are used to decide a predicate concerned with...

The Synthesis of Recursive Digital Filters
Howard Holtz, C. T. Leondes
Pages: 262-280
DOI: 10.1145/321328.321336
The circumstances and methods of the synthesis of linear digital recursive filters which are both stable and physically realizable are described. It is shown that any amplitude requency transfer function expressible as an even trigonometric...

Unrecognizable Sets of Numbers
Marvin Minsky, Seymour Papert
Pages: 281-286
DOI: 10.1145/321328.321337
When is a set A of positive integers, represented as binary numbers, “regular” in the sense that it is a set of sequences that can be recognized by a finite-state machine? Let &pgr;...

Boundary Value Techniques for the Numerical Solution of Certain Initial Value Problems in Ordinary Differential Equations
Riaz A. Usmani
Pages: 287-295
DOI: 10.1145/321328.321338
Linear initial value problems, particularly involving first order differential equations, can be transformed into systems of higher order and treated as boundary value problems. The type of difference equations used to replace the associated...

Numerical Experiments in Conformal Mapping by the Method of Orthonormal Polynomials
Philip Rabinowitz
Pages: 296-303
DOI: 10.1145/321328.321339
Conformal maps of simply connected regions onto the interior and exterior of the unit circle can be computed from complex polynomials orthonormal over the boundary of the given region. As an example of this method, maps of ellipses, rectangles,...

Some Results on Multicategory Pattern Recognition
W. W. Bledsoe
Pages: 304-316
DOI: 10.1145/321328.321340
Some problems arising in multicategory (many pattern types) pattern recognition are treated mathematically, and formulas are derived which describe some inherent limitations associated therewith. The principal results concern the...