Transitiver Abschluss einer affinen Beziehung

Ich suche nach Arbeiten zur Berechnung des transitiven Abschlusses einer affinen Beziehung in folgendem Sinne:

Sei die Beziehung, die durch ein System linearer Ungleichungen über reelle Variablen , dhx 1 , ... , x n , x ' 1 , ... , x ' $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$$x_1,\dots,x_n,x'_1,\dots,x'_n$

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

wobei $A$ eine $m\times 2n$ Matrix und $b$ ein $m$ Vektor ist.

Ich suche eine symbolische Darstellung von $R^k$ , wo

$R^k(x_1,\dots,x_n,x'_1,\dots,x'_n)$ wenn y_1, \ Punkte, y_n existieren ,$y_1,\dots,y_n$ so dass $R^{k-1}(x_1,\dots,x_n,y_1,\dots,y_n)$ und $R(y_1,\dots,y_n,x'_1,\dots,x'_n)$ .

Betrachten Sie als sehr einfaches Beispiel

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

In diesem Fall ist $R^k(x,x')$ iff $x'\leq x+k$ und $x'\geq \frac{1}{2^k} x$

Es gibt einen einfachen Sonderfall, in dem alle Bedingungen gleich sind: Dann können wir die Gauß-Eliminierung anwenden, um die affine Transformation zu finden, die das $x_i$ auf das (abhängige) $x'_j$ und seine $k$ te Potenz berechnen . Aber natürlich ist R im Allgemeinen $R$nicht funktionsfähig.

Das Problem scheint auch einfacher zu sein , wenn $R$ beschreibt einen offenen Polytop eines konvexen Kegel, aber ich kann das nicht annehmen.

Bearbeiten: Ich suche eine parametrische Form unabhängig vom konkreten Wert von (wie im Spielzeugbeispiel). Für einen gegebenen Wert von kann eine Darstellung von immer aus und durch variable Eliminierung erhalten werden.k R k R k - 1$k$$k$$R^k$$R^{k-1}$$R$

Eine Antwort für den Fall, dass das von erzeugte Monoid$A$$R^k$

Eine neuere Referenz zum Thema der tatsächlichen Berechnung des transitiven Verschlusses ist Marius Bozga, Radu Iosif und Filip Konečný, Schnelle Beschleunigung letztendlich periodischer Beziehungen , in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, S. 227-- 242, DOI: 10.1007 / 978-3-642-14295-6_23 , 2010.