Fechamento transitivo de uma relação afim

8

Estou procurando trabalho para calcular o fechamento transitivo de uma relação afim no seguinte sentido:

Seja a relação definida por um sistema de desigualdades lineares sobre as variáveis ​​reais , iex 1 , … , x n , x ′ 1 , … , x ′ nR(x1,…,xn,x1′,…,xn′)x1,…,xn,x1′,…,xn′

R(x1,…,xn,x1′,…,xn′) se UMAx1…xnx1′…xn′≤b

onde é uma matriz um vetor .m × 2 n b mUMAm×2nbm

Estou procurando uma representação simbólica de , ondeRk

Rk(x1,…,xn,x1′,…,xn′) se existir modo que e .R k - 1 ( x 1 , … , x n , y 1 , … , y n ) R ( y 1 , … , y n , x ′ 1 , … , x ′ n )y1,…,ynRk-1(x1,…,xn,y1,…,yn)R(y1,…,yn,x1′,…,xn′)

Como um exemplo muito simples, considere

se x ′ ≤ x + 1 e x ′ ≥ 1R(x,x′)x′≤x+1x′≥12x

Neste caso, sse x ' ≤ x + k e X ' ≥ 1Rk(x,x′)x′≤x+kx′≥12kx

Existe um caso fácil e especial em que todas as restrições são iguais: então podemos aplicar a eliminação de Gauss para encontrar a transformação afim que mapeia para o (dependente) x ′ j e calcula sua k- ésima potência. Mas é claro que, em geral, R não será funcional.xEuxj′kR

O problema também parece ser mais fácil quando descreve um pólipo aberto, um cone convexo, mas não posso assumir isso.R

Edit: Estou procurando uma forma paramétrica independente do valor concreto de (como no exemplo do brinquedo). Para um dado valor de k , uma representação de R k sempre pode ser obtida de R k - 1 e R por eliminação variável.kkRkRk-1R

ds.algorithms linear-algebra matrices warakawa
fonte
(1) “Fechamento transitivo” soa como se você estivesse procurando algo como R∪R ^ 2∪R ^ 3∪…, mas acho que esse não é o caso e que você está procurando a representação H de R ^ k para um dado k. Estou certo? (2) Desculpe pela minha ignorância, mas o que é um politopo aberto?
Tsuyoshi Ito
1
Supondo que você esteja procurando uma representação H de R ^ k para um determinado k, existe pelo menos um algoritmo ineficiente. Suponha k = 2 por simplicidade (um k geral pode ser tratado da mesma maneira). Seja P = {(x, x ′) | R (x, x ′)} o poliedro correspondente à relação R e considere o produto cartesiano P × P = {(x, x ′, y, y ′) | R (x, x ′) ∧R (y, y ′)}. Como recebemos uma representação H de P, temos uma representação H de P × P. Adicione a equação x ′ = y e projete as variáveis ​​x ′ e y pela eliminação de Fourier-Motzkin (isso é ineficiente). Então obtemos uma representação H da relação R ^ 2.
Tsuyoshi Ito
Obrigado Tsuyoshi, de fato, essa também foi minha primeira ideia. Isso fornece um SLI (sistema de desigualdades lineares) para qualquer dado k. Estou procurando uma forma paramétrica que seja independente do valor real de k.
Warakawa
2
Interessante. Eu acho que é melhor editar a pergunta para que as pessoas possam entender que você está procurando uma forma paramétrica independente do valor de k sem ler o comentário.
Tsuyoshi Ito

Respostas:

4

UMARk

Uma referência mais recente sobre o fato de computar o fechamento transitivo é Marius Bozga, Radu Iosif e Filip Konečný, Aceleração Rápida de Relações Ultimamente Periódicas , no CAV 2010 (Verificação Assistida por Computador), Notas de Aula em Ciência da Computação 6174, páginas 227-- 242, DOI: 10.1007 / 978-3-642-14295-6_23 , 2010.

Sylvain
fonte