Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most once!

You can also describe this data structure by the rules for its growth:

  1. Start with node 0 with associated empty set C(0) = {} = creating new object
  2. For any node x create a new node y where (x,y) is oriented edge from x to y and C(y) = C(x) union { (x,y) } = versioning and branching
  3. For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and C(r) = C(f) union C(t) union { (f,r), (t,r) } = merging

Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not.

Base node is defined as a node b, such as C(b) = C(f) intersect C(t), where f and t are nodes representing two versions to be merged.

Simple Merge equation Result=To + (From-Base) = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = 3-way merge

Complex merge equation Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. (1+2n)-way merge

I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.

  1. Prove there can be no circles in the graph
  2. Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
  3. Create algorithm to find B in simple case where n = 1.
  4. Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.
  5. Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.
share|cite|improve this question
Cross-posted to math.SE. – mhum Jan 8 '13 at 3:53
I find out in my discussion in that the problem is not stated correctly. I will be editing it soon. – Jiri Klouda Jan 9 '13 at 8:27
It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions. – Kaveh Jan 11 '13 at 4:54
ps: please read the FAQ if you haven't. – Kaveh Jan 11 '13 at 4:55
Kaveh, the discussion on math hit dead end pretty soon, but then I found this site and thought the question might be better suited for it. And it seems I have been right. I am doing some extra research on the problem and will update the question with all relevant information by Monday. – Jiri Klouda Jan 11 '13 at 4:58
up vote 3 down vote accepted

If you insist that the edges in the complex merge equation don't appear twice (eg. that the + you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:

V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }

now, if To = c and F = d: C(c) contains already all the edges except (b,d) and (c,d), So Sum (Fi-Bi) has to be exactly those edges. Since these edges are only contained in C(d), they must be (not necessarily both) contained in summand d-B for some B. But that is not possible, because whatever B we choose, we add also edges that are already in C(To).

(*) otherwise the assertion (2) is actually false: Result = To + (From - To) satisfies the simple merge equation for all From and To (even if it looks bizarre).

Long story short: You gave inadequate or incomplete definitions.

Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?

A: The definitions are almost always wrong.

share|cite|improve this answer
You are absolutely right, the definition is not adequate and congratulations to finding minimal graph to show the problem with non-existing base. I'm at work on fixing the definition of the problem. – Jiri Klouda Jan 9 '13 at 8:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.