0
$\begingroup$

So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free. I'm having a problem with the notation in the following definition presented bellow:

The Set-Enumeration (SE)-tree is a vehicle for representing and/or enumerating sets in a best-first fashion. The complete SE-tree systematically enumerates elements of a power-set using a pre-imposed order on the underlying set of elements. In problems where the search space is a subset of that power-set that is (or can be) closed under set-inclusion, the SE-tree induces a complete irredundant search technique. Let E be the underlying set of elements. We first index E's elements using a one-to-one function ind: E -> $ \mathbb{N} $. Then, given any subset S $\subseteq$ E, we define its SE-tree view:

Definition 2.1 A Node's View

$View(ind,S) \stackrel{def}{=} \{e \in E | ind(e) \gt max_{e' \in S} ind(e')\}$

In the paper there is an example of a tree made with what appears to be E={1,2,3,4}. I have some familiarity with set-builder notation, but much of the other parts of the "node's view" is confusing me. I skimmed ahead to see if there were clarifications, but I didn't manage to find them so either: a) the author is assuming a competency I do not have, b) the explanation is there and I couldn't find it, or c) the author is doing a horrible job as an author.

So with the hope that it is one of the first two:

  • I'm assuming that the prime in e' is for the complement of the set e, so if e = {1}, then e' = {2,3,4}. Is this correct?
  • What is this ind function? What would ind({3,4}) be for example?
  • $max_{e' \in S}$? Is this the maximum height of the sub tree of the complement of e?

    Any assistance on this would be most appreciated.

$\endgroup$
1
$\begingroup$

No, the prime is not complement, $e'$ is just a different variable than $e$.

In words, $\text{View}(\text{ind},S)$ is the set of all edges whose index is higher than the indices of edges in $S$. The function $\text{ind}: E \to \mathbb{N}$ gives a number to each edge, and $\max_{e' \in S}\text{ind}(e')$ is simply the highest index of $S$.

Then $\text{View}(\text{ind},S)$ is the set of all edges whose index is higher than $\max_{e' \in S}\text{ind}(e')$.

$\endgroup$
1
$\begingroup$

Please, one question per question.

The answer to your first question: No, prime most likely does not indicate complement, absent some specific indication of that. It is just another variable. $e$ is one variable; $e'$ is another variable (the author could have used a different letter, like $f$ or $x$ or something, but chose to use $e'$ instead).

The answer to your second question: The ind function is defined in the text immediately preceding the definition. Read it again?

Yes, it's possible you might lack the necessary mathematical background. You might try taking an online course (or working through a textbook) on discrete mathematics for computer science.

$\endgroup$

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.