enter search term and/or author name
Almost tight upper bounds for vertical decompositions in four dimensions
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
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
We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith . 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
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...