Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 38 Issue 2, April 1991

Modularity of cycles and paths in graphs
E. M. Arkin, C. H. Papadimitriou, M. Yannakakis
Pages: 255-274
DOI: 10.1145/103516.103517
Certain problems related to the length of cycles and paths modulo a given integer are studied. Linear-time algorithms are presented that determine whether all cycles in an undirected graph are of length P mod Q...

Maintenance of geometric extrema
David Dobkin, Subhash Suri
Pages: 275-298
DOI: 10.1145/103516.103518
Let S be a set, f: S×SR+ a bivariate function, and f(x,S) the...

A methodology for hardware verification based on logic simulation
Randal E. Bryant
Pages: 299-328
DOI: 10.1145/103516.103519
A logic simulator can prove the correctness of a digital circuit if it can be shown that only circuits fulfilling the system specification will produce a particular response to a sequence of simulation commands.This style of verification has...

Towards an algebraic theory of recursion
Yannis E. Ioannidis, Eugene Wong
Pages: 329-381
DOI: 10.1145/103516.103521
An algebraic framework for the study of recursion has been developed. For immediate linear recursion, a Horn clause is represented by a relational algebra operator. It is shown that the set of all such operators forms a closed semiring. In this...

A model-theoretic analysis of knowledge
Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi
Pages: 382-428
DOI: 10.1145/103516.128680

On stability and performance of parallel processing systems
Nicholas Bambos, Jean Walrand
Pages: 429-452
DOI: 10.1145/103516.103520
The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view. As a basic simple model, consider infinitely many processors that can work simultaneously, and a stream of arriving jobs,...

A lower bound for integer greatest common divisor computations
Yishay Mansour, Baruch Schieber, Prasoon Tiwari
Pages: 453-471
DOI: 10.1145/103516.103522
It is proved that no finite computation tree with operations { +, -, *, /, mod, < } can decide whether the greatest common divisor (gcd) of a and b is one, for all pairs of integers a and...

Space-bounded probabilistic game automata
Anne Condon
Pages: 472-494
DOI: 10.1145/103516.128681

Efficient simulation of finite automata by neural nets
Noga Alon, A. K. Dewdney, Teunis J. Ott
Pages: 495-514
DOI: 10.1145/103516.103523
Let K(m) denote the smallest number with the property that every m-state finite automaton can be built as a neural net using K(m) or fewer neurons. A counting...