1,721,088 research outputs found
Three Euler's Sieves and a Fast Prime Generator (Functional Pearl)
No full textThe Euler's Sieve refines the Sieve of Eratosthenes to compute prime numbers, by crossing off each non prime number just once. Euler's Sieve is considered hard to be faithfully and efficiently coded as a purely functional stream based program. We propose three Haskell programs implementing the Euler's Sieve, all based on the idea of generating just once each composite to be crossed off. Their faithfulness with respect to the Euler's Sieve is up to costly stream unions imposed by the sequential nature of streams. Our programs outperform classical naive stream based prime generators such as trial division, but they are asymptotically worse than the O'Neill `faithful' Sieve of Eratosthenes. To circumvent the bottleneck of union of streams, we integrate our techniques inside the O'Neill program, thus obtaining a fast prime generator based on the Euler's Sieve and priority queues
Conflict vs Causality in Event Structures
No full textEvent structures are one of the best known models for concurrency. Many variants of the basic model and many possible notions of equivalence for them have been devised in the literature. In this paper, we study how the spectrum of equivalences for Labelled Prime Event Structures built by Van Glabbeek and Goltz changes if we consider two simplified notions of event structures: the first one is obtained by removing the causality relation (Coherence Spaces) and the second one by removing the conflict relation (Elementary Event Structures). As expected, in both cases the spectrum turns out to be simplified, since some notions of equivalence coincide in the simplified settings; actually, we prove that removing causality simplifies the spectrum considerably more than removing conflict. Furthermore, we also prove that the labeling of events and a property that we call finitariness strongly influence the spectrum of equivalences in the conflict-free setting, whereas they have no impact on the causality-free spectrum
Inefficiencies in network models: a graph-theoretic perspective
No full textWe consider three network models where information items flow from a source to a sink node: flow networks, depletable channels, and traffic networks. We start with the standard model of flow networks; we characterise graph topologies that admit non-maximum saturating flows, under some capacity-to-edge assignment. We then consider a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption and again to maximality of saturating flows. Finally, we consider a traffic model for selfish routing, where efficiency is related to latency at a Wardrop equilibrium. We show that all these forms of inefficiency yield different classes of graphs (apart from in the acyclic case, where the first and the last forms generate the same class). Interestingly, in all cases inefficient graphs can be made efficient by removing edges; this resembles a well-known phenomenon, called Braess's paradox
- …
