Journal of the ACM

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the ...

In this paper, we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are representation ...

We introduce a temporal logic for the specification of real-time systems. Our logic, TPTL, employs a novel quantifier construct for referencing time: the freeze quantifier binds a variable to the time of the local temporal context.

TPTL is both a natural ...