Teste duas árvores de expressão LTL para equivalência

Question

Existe um algoritmo sobre como verificar se duas expressões LTL (representadas como árvores binárias) são equivalentes semanticamente?Como há muitas equivalências menores, como $ a \ rightarrow b \ Equiv \ Neg A \ Vee B $ ou $ f (a) \ equiv u a $, bem como comutatividade, distinção, etc. que precisam ser considerados.
Minha ideia inicial era criar a tabela de verdade para as expressões e compará-las.Mas então os operadores temporais não seriam levados em conta.Criar e comparar o autômato para cada expressão parece que seria bastante ineficiente.

Existe uma maneira melhor de fazer isso?

Answer 1

Infelizmente, a abordagem da construção de autômatos para cada fórmula e testar sua equivalência é praticamente o melhor que você pode fazer.

O problema de verificar se uma fórmula LTL é válida, ou seja, se está satisfeita em cada computação, é o PSpace completo (este é um exercício fácil, dado que a satisfação LTL é PSpace completa).

Assim, verificando se duas fórmulas LTL são equivalentes também é pelo menos pspace duro, uma vez que você pode reduzir do primeiro testando equivalência com a fórmula "true".

Para mostrar a associação no PSpace, você pode tomar a abordagem padrão de verificar a equivalência do autômato correspondente "na mosca", sem realmente construí-los explicitamente.