Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Juegos de Emerson-Lei y Manna-Pnueli para síntesis LTLf+ y PPLTL+

Created by
  • Haebom

Autor

Daniel Hausmann, Shufang Zhu, Gianmarco Parretti, Christoph Weinhuber, Giuseppe De Giacomo, Nir Piterman

Describir

Este artículo presenta el primer solucionador de síntesis reactiva para lógica temporal LTLfp y PPLTLp, que logra plena expresividad LTL en un entorno de trazas infinitas mediante técnicas LTLf/PPLTL de trazas finitas. Se basa en un juego gráfico que construye una arena de juego mediante una técnica LTLf/PPLTL basada en DFA. En primer lugar, presentamos un solucionador simbólico basado en el juego de Emerson-Lei, que reduce las propiedades de bajo nivel (garantías y seguridad) a propiedades de alto nivel (recursividad y persistencia) y resuelve el juego. Finalmente, presentamos el juego Manna-Pnueli, que incorpora de forma natural el objetivo de Manna-Pnueli en la arena. El juego Manna-Pnueli se resuelve sintetizando la solución al DAG del juego más simple de Emerson-Lei, un enfoque demostrablemente más eficiente. Evaluamos experimentalmente el solucionador implementado para varias formulaciones, mostrando que el juego Manna-Pnueli a menudo ofrece beneficios significativos, pero no es universal, lo que sugiere que combinar los dos enfoques podría mejorar aún más el rendimiento práctico.

Takeaways, Limitations

Takeaways:
Presentamos el primer solucionador de síntesis reactiva para LTLfp y PPLTLp.
Presentamos y comparamos el rendimiento de dos solucionadores basados ​​en el juego de Emerson-Lei y el juego de Manna-Pnueli.
Se ha demostrado experimentalmente que el juego Manna-Pnueli es más eficiente en ciertos casos.
La combinación de ambos enfoques sugiere potencial para futuras mejoras del rendimiento.
Limitations:
La eficacia del juego Maná-Pnueli no está garantizada en todos los casos.
Todavía no se ha presentado un solucionador mejorado que combine ambos enfoques.
Se necesitan más investigaciones para determinar la generalización de los resultados experimentales.
👍