Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 51 Issue 5, September 2004

Almost tight upper bounds for vertical decompositions in four dimensions
Vladlen Koltun
Pages: 699-730
DOI: 10.1145/1017460.1017461
We show that the complexity of the vertical decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n4+ϵ), for any ϵ > 0. This improves the best...

Automatic information extraction from large websites
Valter Crescenzi, Giansalvatore Mecca
Pages: 731-779
DOI: 10.1145/1017460.1017462
Information extraction from websites is nowadays a relevant problem, usually performed by software modules called wrappers. A key requirement is that the wrapper generation process should be automated to the largest extent, in order to allow for...

Self-stabilizing clock synchronization in the presence of Byzantine faults
Shlomi Dolev, Jennifer L. Welch
Pages: 780-799
DOI: 10.1145/1017460.1017463
We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect...

A unified theory of shared memory consistency
Robert C. Steinke, Gary J. Nutt
Pages: 800-849
DOI: 10.1145/1017460.1017464
The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial...