https://veri-bbb.imag.fr/b/rad-ofn-9t8-rqc
20 septembre 2021 - 14h00
Décidabilité de la rationalité des VAS
par Lucas Bueri de VERIMAG
Résumé : Obtenir la rationalité d'un système d'addition de vecteurs (VAS) permet de simplifier les problèmes associés en utilisant les résultats des automates finis. Ce travail vise donc à approfondir l'identification des VAS rationnels en se tournant vers les configurations de départ.
Après avoir corrigé une preuve de décidabilité de la rationalité des VAS, proposé en 1980 par Ginzburg et Yoeli, nous démontrons que le problème de rationalité struturelle d'un VAS évoqué par Valk et Vidal-Naquet en 1981 est décidable en temps co-NP.
Les caractérisations introduites dans ces preuves permettent alors de hiérarchiser les configurations pour identifier celles qui initient un VAS rationnel.
