
Clotilde Bizière (LaBRI) et Wojciech Czerwiński (Université de Varsovie) ont un article accepté dans la prestigieuse conférence STOC qui se tiendra du 23 au 27 juin 2025, à Prague (République Tchèque).
Nous travaillons sur des automates, des objets mathématiques utilisés pour modéliser le calcul. En particulier, nous nous intéressons au problème d'accessibilité dans les systèmes d'addition de vecteurs avec états (ou VASS, selon l’acronyme anglais) à pile. Ces automates combinent une pile, qui permet de modéliser la récursivité (comme les appels de fonctions), et des compteurs, qui modélisent la concurrence. Le problème d’accessibilité consiste à déterminer si un tel système peut atteindre une configuration donnée.
Ce problème a été largement étudié dans les automates à pile d’une part, et dans les VASS sans pile d’autre part, mais sa décidabilité reste ouverte dans le cas des VASS à pile. Autrement dit, on sait bien traiter la récursivité et la concurrence séparément, mais leur combinaison reste mal comprise.
Notre article apporte une avancée sur cette question en proposant un algorithme pour les VASS à pile de dimension 1, c’est-à-dire les automates munis d’une pile et d’un seul compteur.
Le preprint sur arwiv, ici.