ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 49 Issue 1, January 2002

Fast context-free grammar parsing requires fast boolean matrix multiplication
Lillian Lee
Pages: 1-15
DOI: 10.1145/505241.505242
In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time...

An optimal minimum spanning tree algorithm
Seth Pettie, Vijaya Ramachandran
Pages: 16-34
DOI: 10.1145/505241.505243
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning tree of a graph with n vertices and ...

On a model of indexability and its bounds for range queries
Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas
Pages: 35-55
DOI: 10.1145/505241.505244
We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload, we can construct an...

Expressiveness of structured document query languages based on attribute grammars
Frank Neven, Jan Van Den Bussche
Pages: 56-100
DOI: 10.1145/505241.505245
Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we...

Bounded concurrent timestamp systems using vector clocks
Sibsankar Haldar, Paul Vitányi
Pages: 101-126
DOI: 10.1145/505241.505246
Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control...