Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 40 Issue 1, Jan. 1993

An algorithm for finding canonical sets of ground rewrite rules in polynomial time
Jean Gallier, Paliath Narendran, David Plaisted, Stan Raatz, Wayne Snyder
Pages: 1-16
DOI: 10.1145/138027.138032
In this paper, it is shown that there is an algorithm that, given by finite set E of ground equations, produces a reduced canonical rewriting system R equivalent to E in polynomial time. This...

Perfectly secure message transmission
Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung
Pages: 17-47
DOI: 10.1145/138027.138036
This paper studies the problem of perfectly secure communication in general network in which processors and communication lines may be faulty. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient...

Generating automatically tuned bitmaps from outlines
John D. Hobby
Pages: 48-94
DOI: 10.1145/138027.138040
Consider the problem of generating bitmaps from character shapes given as outlines. The obvious scan-conversion process does not produce acceptable results unless important features such as stem widths are carefully controlled during the...

The minimum consistent DFA problem cannot be approximated within any polynomial
Leonard Pitt, Manfred K. Warmuth
Pages: 95-142
DOI: 10.1145/138027.138042
The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the DFA found should accept or reject). Assuming that P...

A framework for defining logics
Robert Harper, Furio Honsell, Gordon Plotkin
Pages: 143-184
DOI: 10.1145/138027.138060
The Edinburgh Logical Framework (LF) provides a means to define (or present) logics. It is based on a general treatment of syntax, rules, and proofs by means of a typed &lgr;-calculus with dependent types. Syntax is treated in a style similar...

Learning read-once formulas with queries
Dana Angluin, Lisa Hellerstein, Marek Karpinski
Pages: 185-210
DOI: 10.1145/138027.138061
A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called &mgr;-formulas or Boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using...