5
$\begingroup$

Let's say that an item is either a natural number or a list of items. Examples of items are:

  • 1
  • [2]
  • [4, [3, 1], 3, 4]

A rule states that two items are equal. For example:

  • 1 = 2
  • 3 = [3, 1]
  • [4, 3] = [1, 5]

When using these example rules, we can transform [4, [3, 2]] into [4, [3, 1]] into [4, 3] into [1, 5] and we can say that [4, [3, 2]] equals [1, 5].

I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.

I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.

Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into [1], 2 into [1, 1], 3 into [1, 1, 1], etcetera.

$\endgroup$
  • 1
    $\begingroup$ This looks like the decision problem for the theory of equality with uninterpreted functions, from smt (arrays here being function calls). However, I don't know of any nice explanation of how to solve it quickly, beyond using Union Find. $\endgroup$ – Curtis F Oct 15 '18 at 1:25
  • 1
    $\begingroup$ @CurtisF The underlying problem is about function calls. I thought this would be an easier way to display the problem. $\endgroup$ – Paul Oct 15 '18 at 2:15
  • $\begingroup$ @Paul, if this question comes from a book or a paper, can you add a reference? If it comes back your personal thinking, any background or motivation? It would be great for you to add those information in the question, which should motivate and help people to tackle this question more and better. $\endgroup$ – Apass.Jack Oct 23 '18 at 3:29
0
$\begingroup$

I found a solution to my problem. Let's look at the simpler but equivalent problem in which an item is recursively defined as an empty list or a list of items. I'll summarize the algorithm.

Variables:

  • Int counter starting at 0
  • Hash map: list of integers $\to$ integer. The integers represent equivalence classes.

Function find(item) $\to$ int:

Finds the equivalence class of an item. Recursively call find on all the children of item. Now you have a list of ints. If this list of ints is contained in the hash map, return the corresponding value. If not, add the list to the hash map with the counter as value. Increase the counter and return the value.

Function merge(int a, int b):

Merges two equivalence classes a and b. In the hash map, replace all occurences (both in keys and in values) of a by b. Now it can happen that one key is mapped to multiple values. If that happens, again merge those values. Repeat this until every key maps to a unique value.

Algorithm:

For every rule c = d, call merge(find(c), find(d)). Then to see if a = b, check if find(a) = find(b).

$\endgroup$
  • 2
    $\begingroup$ "Finds the equivalence class of an item". There are infinitely many elements in an equivalence class. $3 =[3, 1] = [[3,1],1] = [[[3,1],1]]=\cdots$. Have you handled them all? $\endgroup$ – Apass.Jack Oct 23 '18 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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