Daily Arxiv

Cette page résume et organise les publications en intelligence artificielle du monde entier.
Les contenus sont synthétisés grâce à Google Gemini et le service est proposé à but non lucratif.
Les droits d'auteur des articles appartiennent à leurs auteurs ou institutions respectives ; en cas de partage, il suffit d'en mentionner la source.

Jeux Emerson-Lei et Manna-Pnueli pour la synthèse LTLf+ et PPLTL+

Created by
  • Haebom

Auteur

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

Contour

Cet article présente le premier solveur de synthèse réactive pour la logique temporelle LTLfp et PPLTLp. Il atteint une expressivité LTL complète dans un environnement à traces infinies grâce aux techniques LTLf/PPLTL à traces finies. Il repose sur un jeu de graphes qui construit une arène de jeu à l'aide d'une technique LTLf/PPLTL basée sur l'AFD. Nous présentons d'abord un solveur symbolique basé sur le jeu d'Emerson-Lei, qui réduit les propriétés de bas niveau (garanties et sécurité) à des propriétés de haut niveau (récursivité et persistance) et résout le jeu. Enfin, nous introduisons le jeu de Manna-Pnueli, qui intègre naturellement l'objectif de Manna-Pnueli dans l'arène. Le jeu de Manna-Pnueli est résolu en synthétisant la solution du DAG du jeu d'Emerson-Lei plus simple, une approche manifestement plus efficace. Nous évaluons expérimentalement le solveur implémenté pour diverses formulations, montrant que le jeu Manna-Pnueli offre souvent des avantages significatifs, mais n'est pas universel, suggérant que la combinaison des deux approches pourrait encore améliorer les performances pratiques.

Takeaways, Limitations

Takeaways:
Nous présentons le premier solveur de synthèse réactive pour LTLfp et PPLTLp.
Nous présentons et comparons les performances de deux solveurs basés sur le jeu Emerson-Lei et le jeu Manna-Pnueli.
Il a été démontré expérimentalement que le jeu de Manna-Pnueli est plus efficace dans certains cas.
La combinaison des deux approches suggère un potentiel d’amélioration des performances futures.
Limitations:
L’efficacité du jeu Manna-Pnueli n’est pas garantie dans tous les cas.
Un solveur amélioré combinant les deux approches n’a pas encore été présenté.
Des recherches supplémentaires sont nécessaires pour déterminer la généralisabilité des résultats expérimentaux.
👍