Cierre transitivo de una relación afín.

8

Estoy buscando trabajo para calcular el cierre transitivo de una relación afín en el siguiente sentido:

Sea la relación definida por un sistema de desigualdades lineales sobre las variables reales , es decirx 1 , ... , x n , x ′ 1 , ... , x ′ nR(x1,…,xn,x1′,…,xn′)x1,…,xn,x1′,…,xn′

A x 1 ... x n x ′ 1 ... x ′ n ≤ bR(x1,…,xn,x1′,…,xn′) iff Ax1…xnx1′…xn′≤b

donde es una matriz y un vector .m × 2 n b mAm×2nbm

Estoy buscando una representación simbólica de , dondeRk

y 1 , ... , y n R k - 1 ( x 1 , ... , x n , y 1 , ... , y n ) R ( y 1 , ... , y n , x ′Rk(x1,…,xn,x1′,…,xn′) si existe tal que y .y1,…,ynRk−1(x1,…,xn,y1,…,yn)R(y1,…,yn,x1′,…,xn′)

Como un ejemplo muy simple, considere

x ′ ≤ x + 1 x ′ ≥ 1R(x,x′) iff yx′≤x+1x′≥12x

En este caso, iff yx ′ ≤ x + k x ′ ≥ 1Rk(x,x′)x′≤x+kx′≥12kx

Hay un caso especial fácil en el que todas las restricciones son igualitarias: entonces podemos aplicar la eliminación de Gauss para encontrar la transformación afín que asigna el al (dependiente) y calcular su ésima potencia. Pero, por supuesto, en general, no será funcional.x ′ j k Rxixj′kR

El problema también parece ser más fácil cuando describe un politopo abierto como un cono convexo, pero no puedo suponer esto.R

Editar: estoy buscando una forma paramétrica independiente del valor concreto de (como en el ejemplo del juguete). Para un valor dado de , una representación de siempre se puede obtener de y por eliminación de variables.k R k R k - 1 RkkRkRk−1R

ds.algorithms linear-algebra matrices warakawa
fuente
(1) "Cierre transitivo" suena como si estuviera buscando algo como R∪R ^ 2∪R ^ 3∪ ... pero supongo que este no es el caso y que está buscando la representación H de R ^ k para un determinado k. Estoy en lo cierto? (2) Perdón por mi ignorancia, pero ¿qué es un politopo abierto?
Tsuyoshi Ito
1
Suponiendo que está buscando una representación H de R ^ k para una k dada, hay al menos un algoritmo ineficiente. Suponga que k = 2 por simplicidad (un k general puede manejarse de la misma manera). Sea P = {(x, x ′) | R (x, x ′)} el poliedro correspondiente a la relación R, y considere el producto cartesiano P × P = {(x, x ′, y, y ′) | R (x, x ′) ∧R (y, y ′)}. Como se nos da una representación H de P, tenemos una representación H de P × P. Agregue la ecuación x ′ = y, y proyecte las variables x ′ e y mediante la eliminación de Fourier-Motzkin (esto es ineficiente). Luego obtenemos una representación H de la relación R ^ 2.
Tsuyoshi Ito
Gracias Tsuyoshi, de hecho, esta también fue mi primera idea. Esto proporciona un SLI (sistema de desigualdades lineales) para cualquier k dado. Estoy buscando una forma paramétrica que sea independiente del valor real de k.
warakawa
2
Interesante. Creo que es mejor editar la pregunta para que las personas puedan entender que está buscando una forma paramétrica independiente del valor de k sin leer el comentario.
Tsuyoshi Ito

Respuestas:

4

Una respuesta en caso de que el monoide generado por para la multiplicación de matrices sea finito: Alain Finkel y Jérôme Leroux, Cómo componer aceleraciones previas a las hamburguesas : aplicaciones para protocolos de transmisión , en FSTTCS 2002 (Fundamentos de la tecnología de software y ciencias de la informática teóricas). Science 2556, páginas 145--156, DOI: 10.1007 / 3-540-36206-1_14 , 2002 (ver también las numerosas referencias allí). La relación está representada por una fórmula Presburger efectivamente computable.R kARk

Una referencia más reciente sobre el tema de calcular el cierre transitivo es Marius Bozga, Radu Iosif y Filip Konečný, Aceleración rápida de las relaciones periódicas finales , en CAV 2010 (Verificación asistida por computadora), Lecture Notes in Computer Science 6174, páginas 227-- 242, DOI: 10.1007 / 978-3-642-14295-6_23 , 2010.

Sylvain
fuente