Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 43 Issue 3, May 1996

On linear potential functions for approximating Bayesian computations
Eugene Santos, Jr.
Pages: 399-430
DOI: 10.1145/233551.233552
Probabilistic reasoning suffers from NP-hard implementations. In particular, the amount of probabilistic information necessary to the computations is often overwhelming. For example, the size of conditional probability tables in Bayesian...

Software protection and simulation on oblivious RAMs
Oded Goldreich, Rafail Ostrovsky
Pages: 431-473
DOI: 10.1145/233551.233553
Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this...

Foundations of multimedia database systems
Sherry Marcus, V. S. Subrahmanian
Pages: 474-523
DOI: 10.1145/233551.233554
Though numerous multimedia systems exist in the commercial market today, relatively little work has been done on developing the mathematical foundation of multimedia technology. We attempt to take some initial steps towards the development of a...

Linear-time suffix parsing for deterministic languages
Mark-Jan Nederhof, Eberhard Bertsch
Pages: 524-554
DOI: 10.1145/233551.233555
We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether wis a suffix of some string in L. In contrast to a...

Branching time and abstraction in bisimulation semantics
Rob J. van Glabbeek, W. Peter Weijland
Pages: 555-600
DOI: 10.1145/233551.233556
In comparative concurrency semantics, one usually distinguishes between linear time and branching time semantic equivalences. Milner's notion of observatin equivalence is often mentioned as the...