Prueba dos árboles de expresión LTL para la equivalencia.

Question

¿Hay un algoritmo sobre cómo verificar si dos expresiones LTL (representadas como árboles binarias) son semánticamente equivalentes?Ya que hay muchas equivalencias más pequeñas, como $ A \ Rudowarrow B \ Equiv \ NET A \ Vee B $ o $ f (a) \ equivalente VERDADERO u A $, así como la conmutatividad, la distribución, etc. que deben considerarse.
Mi idea inicial era crear la tabla de verdad para expresiones y compararlas.Pero entonces los operadores temporales no se tendrían en cuenta.Crear y comparar el autómata para cada expresión sonidos como si fuera bastante ineficiente.

¿Hay una mejor manera de hacer esto?

Answer 1

Desafortunadamente, el enfoque de la construcción de autómatas para cada fórmula y probar su equivalencia es prácticamente lo mejor que puede hacer.

El problema de verificar si una fórmula LTL es válida, es decir, ya sea que esté satisfecho en cada cálculo, se complete el PSPACE (este es un ejercicio fácil, dado que la satisfacción de LTL es PSPACE completa).

Por lo tanto, verificar si dos fórmulas LTL son equivalentes, también es al menos PSPACE DURO, ya que puede reducir de la primera equivalencia de prueba con la fórmula "VERDADERA".

Para mostrar la membresía en PSPACE, puede tomar el enfoque estándar de la revisión de la equivalencia del autómata correspondiente "sobre la marcha", sin construirlos explícitamente.