3 ms·
That mostly makes sense so I apologize if this is pedantic, but: Is it not possible for a set to have logically infinite sets in Bloom? For instance, "the set
by pfraze 8y ago
That mostly makes sense so I apologize if this is pedantic, but:
Is it not possible for a set to have logically infinite sets in Bloom? For instance, "the set of all integers" ? If so, how does it determine the limits of set sizes - is it connected to bit counts? Eg, "The set of all 8bit integers" ?
- sriram_malhar 8y agoNo, not in Bloom. The sets must be finite. There is one aspect that is infinite, which is along the time axis. But the way the logic works is that you are never in a position to enumerate all possible behaviours. This is a very superficial answer, and perhaps you'll gain more insight from this paper on the logical semantics: Dedalus: Datalog in Time and Space. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-173.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-...
- russell_sears 8y agoYou can guarantee termination by limiting bit precision, but it is more interesting to limit the set of operators your program uses instead. For instance, you might have an operator that translates from hostname to IPv4 address. That function can return billions of different numbers, but if your program’s input only has 10 hostnames in it (and you don’t use string manipulation or other tricks to fabricate hostnames) then you can infer that the IP lookup function only adds 10 new symbols to the sets that your program maintains. Searching for “herbrand universe” will produce formal writeups of these ideas.