Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 39 Issue 2, April 1992

A general approach to connected-component labeling for arbitrary image representations
Michael B. Dillencourt, Hanan Samet, Markku Tamminen
Pages: 253-280
DOI: 10.1145/128749.128750
An improved and general approach to connected-component labeling of images is presented. The algorithm presented in this paper processes images in predetermined order, which means that the processing order depends only on the...

An analysis of the longest match and the greedy heuristics in text encoding
Jyrki Katajainen, Timo Raita
Pages: 281-294
DOI: 10.1145/128749.128751
Text compression is often done using a fixed, previously formed dictionary (code book) that expresses which substrings of the text can be replaced by code words. There always exists an optimal solution for text-encoding problem. Due to the long...

Nonlinear pattern matching in trees
R. Ramesh, I. V. Ramakrishnan
Pages: 295-316
DOI: 10.1145/128749.128752
Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as mechanical theorem proving, term rewriting, symbolic computation, and nonprocedural programming languages. In this paper, we present new...

The generation of binary trees as a numerical problem
Renzo Sprugnoli
Pages: 317-327
DOI: 10.1145/128749.128753
The problem of generating random, uniformly distributed, binary trees is considered. A closed formula that counts the number of trees having a left subtee with k-1 nodes ...

What can machines know?: On the properties of knowledge in distributed systems
Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi
Pages: 328-376
DOI: 10.1145/128749.150945

Theorem proving using equational matings and rigid E-unification
Jean Gallier, Paliath Narendran, Stan Raatz, Wayne Snyder
Pages: 377-430
DOI: 10.1145/128749.128754
In this paper, it is shown that the method of matings due to Andrews and Bibel can be extended to (first-order) languages with equality. A decidable version of E-unification called rigid...

A Four Russians algorithm for regular expression pattern matching
Gene Myers
Pages: 432-448
DOI: 10.1145/128749.128755
Given a regular expression R of length P and a word A of length N, the membership problem is to determine if A is in the language denoted by R....