8
$\begingroup$

I am looking for work on computing the transitive closure of an affine relation in the following sense:

Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ be the relation defined by a system of linear inequalities over real variables $x_1,\dots,x_n,x'_1,\dots,x'_n$, i.e.

$R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff $A x_1\dots x_n x'_1\dots x'_n \leq b$

where $A$ is an $m\times 2n$ matrix and $b$ an $m$-vector.

I am looking for a symbolic representation of $R^k$, where

$R^k(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff there exists $y_1,\dots,y_n$ such that $R^{k-1}(x_1,\dots,x_n,y_1,\dots,y_n)$ and $R(y_1,\dots,y_n,x'_1,\dots,x'_n)$.

As a very simple example, consider

$R(x,x')$ iff $x'\leq x+1$ and $x'\geq \frac{1}{2} x$

In this case, $R^k(x,x')$ iff $x'\leq x+k$ and $x'\geq \frac{1}{2^k} x$

There is an easy special case where all constraints are equalities: then we can apply Gauss elimination to find the affine transformation that maps the $x_i$ to the (dependent) $x'_j$ and compute its $k$th power. But of course in general, $R$ will not be functional.

The problem also seems to be easier when $R$ describes an open polytope a convex cone, but I can not assume this.

Edit: I'm looking for a parametric form independent of the concrete value of $k$ (as in the toy example). For a given value of $k$, a representation of $R^k$ can always be obtained from $R^{k-1}$ and $R$ by variable elimination.

$\endgroup$
  • $\begingroup$ (1) “Transitive closure” sounds as if you are looking for something like R∪R^2∪R^3∪…, but I guess that this is not the case and that you are looking for the H-representation of R^k for a given k. Am I right? (2) Sorry for my ignorance, but what is an open polytope? $\endgroup$ – Tsuyoshi Ito Jan 6 '11 at 14:04
  • 1
    $\begingroup$ Assuming that you are looking for an H-representation of R^k for a given k, there is at least an inefficient algorithm. Assume k=2 for simplicity (a general k can be handled in the same way). Let P={(x,x′)|R(x,x′)} be the polyhedron corresponding to the relation R, and consider the Cartesian product P×P={(x,x′,y,y′)|R(x,x′)∧R(y,y′)}. Since we are given an H-representation of P, we have an H-representation of P×P. Add the equation x′=y, and project out the variables x′ and y by the Fourier-Motzkin elimination (this is inefficient). Then we obtain an H-representation of the relation R^2. $\endgroup$ – Tsuyoshi Ito Jan 6 '11 at 14:37
  • $\begingroup$ Thank you Tsuyoshi, indeed this was also my first idea. This gives an SLI (system of linear inequalities) for any given k. I am looking for a parametric form that is independent of the actual value of k. $\endgroup$ – warakawa Jan 6 '11 at 14:45
  • 2
    $\begingroup$ Interesting. I think that it is better to edit the question so that people can understand that you are looking for a parametric form independent of the value of k without reading the comment. $\endgroup$ – Tsuyoshi Ito Jan 6 '11 at 15:02
4
$\begingroup$

An answer in case the monoid generated by $A$ for matrix multiplication is finite: Alain Finkel and Jérôme Leroux, How to Compose Presburger-accelerations: Applications to Broadcast Protocols, in FSTTCS 2002 (Foundations of Software Technology and Theoretical Computer Science) Lecture Notes in Computer Science 2556, pages 145--156, DOI: 10.1007/3-540-36206-1_14, 2002 (see also the many references there). The relation $R^k$ is represented by an effectively computable Presburger formula.

A more recent reference on the subject of actually computing the transitive closure is Marius Bozga, Radu Iosif and Filip Konečný, Fast Acceleration of Ultimately Periodic Relations, in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, pages 227--242, DOI: 10.1007/978-3-642-14295-6_23, 2010.

$\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.