Name of this operation?

[helios]

You mean the practical purpose?

Suppose you have a list of numbers that share some meaningful property. Suppose also that you've stored this list in such a way that adding or removing items from it is costly, but that adding or removing several items "in one go" has approximately the same cost as adding or removing a single item. So you would want to progressively construct some data structure (D) that stores the difference between the list you have stored (S1) and some future list (S2), and you would also want a function (g) that takes the list you currently have and the data structure, and gives back the future list.
g() is what I'm really interested in. f() and h() are artifacts for the definition of g().

[tition]

It seems this context is too specific for these objects to have names (but I may be wrong).

Even if what you are exploring is "known", it is certainly not "well-known".

The algebraic operations you are using are simply the arithmetic operations in the direct limit ring I mentioned above:

Bitwise operation <-> operation in the direct limit
& <-> multiplication
~ <-> taking negative sign ([s]multiplying by -1 the ring does not have a unit!).[/s] <-That was wrong!
| <-> addition

Those operations give you a ring, so you have for free the distributive and associative properties, and that's about it.

This is not a usual ring to work with. On top of it you are doing more unusual things. Sounds too specific. So I wouldn't spend too much time looking up the literature (except for 10 minutes to read what little there is to know about direct limits).

[helios]

The algebraic operations you are using are simply the arithmetic operations in the direct limit ring I mentioned above:

Bitwise operation | direct limit operation
& <-> multiplication
~ <-> taking negative sign (multiplying by -1).
| <-> addition

Question: would you come to the same conclusion given these definitions?

f(S1, S2) = (S2\S1, S1\S2)
g(S, (D1, D2)) = (S \ D1) U D2
h((D1, D2)) = (D2, D1)

[48T7M4Gy]

If set theory is used, try this:

If:
S1 = current set
S2 = future set

And:
Difference D = S2\S1

Then:
S2 = S1 U S2\S1 = S1 U D which can be chained (nested) as a time series

[helios]

S2 = S1 U S2\S1

This is incorrect.

Counterexample:
S1 = {1, 2, 3}
S2 = {2, 3, 4}

S2\S1 = {4}
S1 U (S2\S1) = {1, 2, 3, 4} != S2

[48T7M4Gy]

That was quick.

[helios]

I said it before, didn't I? http://www.cplusplus.com/forum/lounge/196857/#msg945476

If f(x, y) = y\x, where you do you get the extra information required to fulfill g(x, y\x) = y? To go from one set to another there's something you have to take out and something you have to add in.

[48T7M4Gy]

I am not skirting the issue of the union not being the solution but what this means is the problem definition needs to be refined.

If you go from 1,2,3 and end up with 2,3,4 then 1 has been dropped and 4 has been added. So maybe the intersection comes into it. My Venn diagram shows

ie S2 = (S1 ∩ S2) ∪ (S2\S1)

It's just another way of interpreting the same diagram.

[helios]

I already gave an exact definition.
f(S1, S2) = (S2\S1, S1\S2)
g(S, (D1, D2)) = (S \ D1) U D2
h((D1, D2)) = (D2, D1)

I also posted a C++ implementation. Maybe it's not that it needs to be refined, maybe you're just not getting it.

[tition]

Question: would you come to the same conclusion given these definitions?

f(S1, S2) = (S2\S1, S1\S2)
g(S, (D1, D2)) = (S \ D1) U D2
h((D1, D2)) = (D2, D1)

No not at all, in fact I still haven't quite digested the connection between what's above and the bitwise operations we were talking about.

[48T7M4Gy]

Could be that I don't get it wouldn't be the first time, more than likely not the last.

I haven't had a chance to look at your program in detail and will do eventually.

I don't want to flog a dead horse but is there a counter example to my second (last) Venn based statement?

The reason for flogging differences is two fold, you started with sets and there are only two legal set differences. That of course doesn't mean you can't invent your own.

[helios]

It's just an analogy. Bitwise operations and set operations are analogous. Polynomial addition and subtraction are also somewhat analogous with g() and f(), respectively.

EDIT:

I don't want to flog a dead horse but is there a counter example to my second (last) Venn based statement?

This statement: S2 = (S1 ∩ S2) ∪ (S2\S1)
is true, but useless.
The point is to define a function g() such that g(S1, x) = S2. x can be anything. It can be a set, a number, whatever. It doesn't matter as long as that identity holds. Your statement is of no use to define g():
g(S1, x) = (S1 ∩ g(S1, x)) ∪ (g(S1, x)\S1)

[tition]

The connection between sets and binary notation that I know about is the following.

Suppose you are talking about the subsets of a large ambient set X. Let A be a subset of X. Then for each element of X you write 1 if it is in A and 0 if it is not in A. In this way, you have identified the subset A with a collection of 1's and 0's. Then "bitwise and" becomes intersection of sets, "bitwise or" becomes union, and "bitwise not" becomes complement relative to X.

This does establish a direct relationship between the function g and binary operations.

However, we were also talking about some direct limit business, and that is different: the minus operation in the direct limit does not correspond to the "bitwise not" (complement relative to X). [Edit:] I previously made an error saying that bitwise not is the direct-limit equivalent of taking a negative sign. It is not.



So, it seems to me there are two possible ways to interpret g algebraically. The set-theoretic way requires the existence of some large ambient set X that contains all possible sets you are talking about.

The second possible interpretation is using direct limits. The direct limit business does not require you to name a large ambient set X. With the direct limit business you don't have an analog of the operation of taking complement relative to X.


However, the functions f and h, which send pairs of subsets to pairs of subsets are more difficult for me to comprehend.

[helios]

Your understanding of the analogy is consistent with mine.

However, the functions f and h, which send pairs of subsets to pairs of subsets are more difficult for me to comprehend.

The problem is that g() needs at least three sets to do its magic. It needs a set to operate on, a set to remove from it, and a set to add to it. In the general case, there's no way for f() to encode this information as a single set, other than by adding a boolean to each element:
f({1, 2, 3}, {3, 4, 5}) = {(1, F), (2, F), (4, T), (5, T)}
By this definition, h() would flip the booleans:
h({(1, F), (2, F), (4, T), (5, T)}) = {(1, T), (2, T), (4, F), (5, F)}

[48T7M4Gy]

Given:
S2 = (S1 ∩ S2) ∪ (S2\S1)

Let:
g(S1, x) = S2, x is an independent variable

Therefore, by substitution:
g(S1, x) = (S1 ∩ g(S1, x)) ∪ (g(S1, x)\S1)

The 3 sets are S1, S2 and S1\S2, for all x

QED

[helios]

g(S1, x) = (S1 ∩ g(S1, x)) ∪ (g(S1, x)\S1)

Therefore, g() is ill-defined, and the rest of the proof is invalid.

[48T7M4Gy]

"x can be anything", just plug in S1 and the answer is always S2. I am thinking maybe the problem is ill-defined.

[helios]

Just stop. You're just embarrassing yourself.

[toad]

Suppose you have a list of numbers that share some meaningful property. Suppose also that you've stored this list in such a way that adding or removing items from it is costly, but that adding or removing several items "in one go" has approximately the same cost as adding or removing a single item. So you would want to progressively construct some data structure (D) that stores the difference between the list you have stored (S1) and some future list (S2), and you would also want a function (g) that takes the list you currently have and the data structure, and gives back the future list.

Not sure how relevant it is, but batched / global / lazy rebuilding from chapter 5 in Okasaki's thesis is what first comes to mind after reading this.

https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

[helios]

Thanks. The technique I describe is basically the same idea -- if an operation has a costly set-up and tear-down that can be shared by several consecutive operations, accumulate operations until an appropriate time and then apply them in a batch. The paper, from I can understand, describes several ways to schedule those batches.
I was rather looking for a mathy way to name f(), although I guess I'll have to resign myself and accept that no one has found or named such an operation.