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