Transitive closure of an affine relation 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&#39;_1,\dots,x&#39;_n)$
be the relation defined by a system of linear inequalities over real variables
$x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_n$,
i.e.

$R(x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_n)$ iff
$A x_1\dots x_n x&#39;_1\dots x&#39;_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&#39;_1,\dots,x&#39;_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&#39;_1,\dots,x&#39;_n)$.

As a very simple example, consider

$R(x,x&#39;)$ iff $x&#39;\leq x+1$ and $x&#39;\geq \frac{1}{2} x$

In this case, $R^k(x,x&#39;)$ iff $x&#39;\leq x+k$ and $x&#39;\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&#39;_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.
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.