World's most popular travel blog for travel bloggers.

# Assistance with Notation in the Paper Entitled: "Search Through Systematic Set Enumeration"

, ,
Problem Detail:

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.

###### Answered By : Pål GD

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')$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40146

3200 people like this