Transitiver Abschluss einer affinen Beziehung

8

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 ' nR(x1,,xn,x1,,xn)x1,,xn,x1,,xn

R(x1,,xn,x1,,xn) iff Ax1xnx1xnb

wobei A eine m×2n Matrix und b ein m Vektor ist.

Ich suche eine symbolische Darstellung von Rk , wo

Rk(x1,,xn,x1,,xn) wenn y_1, \ Punkte, y_n existieren ,y1,,yn so dass Rk1(x1,,xn,y1,,yn) und R(y1,,yn,x1,,xn) .

Betrachten Sie als sehr einfaches Beispiel

R(x,x) iff xx+1 und x12x

In diesem Fall ist Rk(x,x) iff xx+k und x12kx

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 xi auf das (abhängige) xj und seine k te Potenz berechnen . Aber natürlich ist R im Allgemeinen Rnicht 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 R.kkRkRk1R

Warakawa
quelle
(1) „Transitive Closure“ klingt so, als ob Sie nach etwas wie R∪R ^ 2∪R ^ 3∪ suchen…, aber ich denke, dass dies nicht der Fall ist und dass Sie nach der H-Darstellung von R ^ suchen k für ein gegebenes k. Habe ich recht? (2) Entschuldigung für meine Unwissenheit, aber was ist ein offenes Polytop?
Tsuyoshi Ito
1
Angenommen, Sie suchen nach einer H-Darstellung von R ^ k für ein gegebenes k, dann gibt es zumindest einen ineffizienten Algorithmus. Nehmen Sie der Einfachheit halber k = 2 an (ein allgemeines k kann auf die gleiche Weise behandelt werden). Sei P = {(x, x ') | R (x, x')} das Polyeder, das der Beziehung R entspricht, und betrachte das kartesische Produkt P × P = {(x, x ', y, y') | R (x, x ') ∧R (y, y')}. Da wir eine H-Darstellung von P erhalten, haben wir eine H-Darstellung von P × P. Addiere die Gleichung x '= y und projiziere die Variablen x' und y durch die Fourier-Motzkin-Eliminierung (dies ist ineffizient). Dann erhalten wir eine H-Darstellung der Beziehung R ^ 2.
Tsuyoshi Ito
Danke Tsuyoshi, in der Tat war dies auch meine erste Idee. Dies ergibt einen SLI (System linearer Ungleichungen) für jedes gegebene k. Ich suche eine parametrische Form, die unabhängig vom tatsächlichen Wert von k ist.
Warakawa
2
Interessant. Ich denke, dass es besser ist, die Frage zu bearbeiten, damit die Leute verstehen, dass Sie nach einer parametrischen Form suchen, die unabhängig vom Wert von k ist, ohne den Kommentar zu lesen.
Tsuyoshi Ito

Antworten:

4

Eine Antwort für den Fall, dass das von erzeugte MonoidARk

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.

Sylvain
quelle