ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 41 Issue 3, May 1994

On binary constraint problems
Peter B. Ladkin, Roger D. Maddux
Pages: 435-469
DOI: 10.1145/176584.176585
The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski. The concept of path-consistency plays a central role. Algorithms for path-consistency can be implemented on matrices of...

New approximation algorithms for graph coloring
Avrim Blum
Pages: 470-516
DOI: 10.1145/176584.176586
The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k-colorable graphs for constant k ≥ 3. This paper...

On the power of bounded concurrency I: finite automata
Doron Drusinsky, David Harel
Pages: 517-539
DOI: 10.1145/176584.176587
We investigate the descriptive succinctness of three fundamental notions for modeling concurrency: nondeterminism and pure parallelism, the two facets of alternation, and bounded cooperative concurrency, whereby a system...

On the power of bounded concurrency II: pushdown automata
Tirza Hirst, David Harel
Pages: 540-554
DOI: 10.1145/176584.176588
This is the second in a series of papers on the inherent power of bounded cooperative concurrency, whereby an automaton can be in some bounded number of states that cooperate in accepting the input. In this paper, we consider pushdown automata....

Diversity-based inference of finite automata
Ronald L. Rivest, Robert E. Schapire
Pages: 555-589
DOI: 10.1145/176584.176589
We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new representation for finite automata,...