Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 42 Issue 4, July 1995

Translating default logic into standard autoepistemic logic
Georg Gottlob
Pages: 711-740
DOI: 10.1145/210332.210334
Since Konolige's translation of default logic into strongly grounded autoepistemic logic, several other variants of Moore's original autoepistemic logic that embody default logic have been studied. All these logics differ significantly from...

Logical foundations of object-oriented and frame-based languages
Michael Kifer, Georg Lausen, James Wu
Pages: 741-843
DOI: 10.1145/210332.210335
We propose a novel formalism, called Frame Logic (abbr., F-logic), that accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages. These features include object...

Noga Alon, Raphael Yuster, Uri Zwick
Pages: 844-856
DOI: 10.1145/210332.210337

The complexity of probabilistic verification
Costas Courcoubetis, Mihalis Yannakakis
Pages: 857-907
DOI: 10.1145/210332.210339
We determine the complexity of testing whether a finite state, sequential or concurrent probabilistic program satisfies its specification expressed in linear-time temporal logic. For sequential programs, we present an algorithm that runs in time...

A constant-time optimal parallel string-matching algorithm
Zvi Galil
Pages: 908-918
DOI: 10.1145/210332.210341
Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text....

Greed sort: optimal deterministic sorting on parallel disks
Mark H. Nodine, Jeffrey Scott Vitter
Pages: 919-933
DOI: 10.1145/210332.210343
We present an algorithm for sorting efficiently with parallel two-level memories. Our main result is an elegant, easy-to-implement, optimal, deterministic algorithm for external sorting with D disk drives. This...