1
$\begingroup$

I have a set of indexes of integer $\mathbb{I} =\{i_0, i_1, ..., i_n\}$, and an environment $f: \mathbb{I} \rightarrow \mathbb{Z} \times \mathbb{Z}$ which assigns a pair of integer to each index. For instance, $f(i_0) = (-3, 7)$ means the value of $i_0$ is an integer in $[-3, 7]$, in short, $i_0 \in [-3, 7]$. $f(i_1) = (2,5)$ means the value of $i_1$ is an integer in $[2,5]$, in short, $i_1 \in [2,5]$.

I have also 4 variables $a, b, c, d \in \mathbb{V}$, which are constructed with integers, indexes, and the operator $+$. For example, $a = 4, b = i_0, c = i_0 + 2,d = i_1 + 5$.

We define a notation $[[u, v]]= [\min(u, v), \max(u, v)]$ to represent an interval (which could be empty) formed by $u$ and $v$.

So given $a, b, c, d$ and an enviroment $f$, $[[a, b]]$ forms an interval, so is $[[c, d]]$. Then I am looking for an algorithm to calculate $[[a, b]] \cap [[c, d]]$ and $[[a, b]] \cup [[c, d]]$, which means respectively their intersection and union, let's note $Intersection(a, b, c, d, f) = [[a, b]] \cap [[c, d]]$ under $f$, and $Union(a, b, c, d, f) = [[a, b]] \cup [[c, d]]$ under $f$.

$Intersection, Union: \mathbb{V} \times \mathbb{V} \times \mathbb{V} \times \mathbb{V} \times \mathbb{F} \rightarrow \mathbb{V} \times \mathbb{V} \cup \{NotDecidable\} \cup \{NotAnInterval\}$

For instance, given $\{a = 4, b = i_0, c = 8, d = i_0 + 6\}$ and $f: i_0 \mapsto [2,3]$, $Intersection(a, b, c, d, f)$ returns always $\emptyset$, and $Union(a, b, c, d, f)$ returns always "NotAnInterval"; given $f: i_0 \mapsto [8,10]$, $Intersection(a, b, c, d, f)$ returns always $(c, b)$, and $Union(a, b, c, d, f)$ returns always $(a, d)$.

So we can see that it is quite possible that $Intersection$ or $Union$ could not return a fixed answer, in that case, let's make it return "NotDecidable"

It is a complex problem, to simplify a little bit, in the first place, we may assume that the variables are constructed with integers, the operator $+$, and only one index: $i_0$.

I hope my question is clearly described, could anyone help me figure out this algorithm?

Thank you very much

  • 0
    Do the functions Intersection and Union have to answer intervals in the right order? For example, what is the correct answer to Intersection(50, $i_0$, 0, 100, f: $i_0 \mapsto [40,60]$)?2011-07-28

0 Answers 0