On the Reachability Problem for One-Dimensional Thin Grammar Vector Addition Systems

Résumé technique : Sur le problème de la joignabilité pour les systèmes d'ajout de vecteurs à grammaire unidimensionnels et minces

Énoncé du problème
L'article traite du problème de la joignabilité (reachability) pour les systèmes d'ajout de vecteurs à grammaire (GVAS), un modèle étendant les systèmes d'ajout de vecteurs avec états (VASS) en utilisant des grammaires hors contexte pour contrôler les ajouts de vecteurs. Les auteurs se concentrent spécifiquement sur les GVAS unidimensionnels minces (1-TGVAS). Un GVS est dit « mince » si aucun non-terminal ne peut dériver plus d'une copie de lui-même dans une seule dérivation (c'est-à-dire qu'aucune dérivation de la forme $X \Rightarrow \alpha X \beta X \gamma$ n'est possible). Le problème de la joignabilité demande si une configuration cible peut être atteinte à partir d'une configuration source via une exécution non négative.

Bien que le problème de la joignabilité pour les GVAS généraux soit connu pour être décidable, les bornes de complexité restent élevées. Des travaux antérieurs ont établi que le problème de la joignabilité pour un $d$-GVAS mince indexé par $k$ appartient à $F_{4kd+2k-4d}$, ce qui donne une borne supérieure de $F_{6k-4}$ pour le cas unidimensionnel. Les auteurs notent que l'écart entre les bornes supérieures et inférieures pour la joignabilité des GVAS reste important, et qu'il s'agit d'une question ouverte de savoir si une borne supérieure plus serrée, potentiellement élémentaire, existe pour les 1-TGVAS.

Méthodologie
Les auteurs généralisent la technique de décomposition KLM, initialement développée pour la joignabilité des VASS, au contexte des arbres de dérivation générés par grammaire. La méthodologie centrale implique les étapes suivantes :

1. Arbres et composantes KLM : Les auteurs introduisent les arbres KLM comme une représentation structurelle de la joignabilité. Un arbre KLM est composé de composantes KLM, qui capturent des « segments fortement connexes » d'un arbre de dérivation. Un segment est fortement connexe si tous les non-terminaux le long du chemin entre sa racine et sa feuille appartiennent au même composant fortement connexe (SCC) du graphe de production.
2. Systèmes caractéristiques : Pour chaque composante KLM, un système de programmation linéaire en nombres entiers (ILP), nommé système caractéristique, est construit. Ce système encode les images de Parikh des règles de production et les variables de configuration (vecteurs source et cible) pour décrire le comportement de joignabilité du segment correspondant.
3. Classement et décomposition : Pour gérer la complexité, les auteurs définissent un rang pour les composantes KLM basé sur deux métriques :
   • Indice ($\iota$) : L'indice du sous-GVAS induit, lié à la profondeur structurelle de la grammaire.
   • Dimension géométrique ($dim$) : La dimension de l'espace vectoriel engendré par les effets des cycles supérieurs au sein de la composante.
     Le rang d'un arbre KLM est un vecteur comptant les composantes par leur rang. Les auteurs emploient une séquence de opérations de raffinement (contrainte de configuration, orthogonalisation, décomposition algébrique et décomposition combinatoire) pour transformer un arbre KLM initial en un arbre KLM parfait.
4. Séquence de raffinement :
   • Opérations de nettoyage : La contrainte de configuration et l'orthogonalisation fixent les variables bornées et encodent les déplacements uniformes, garantissant que l'arbre est « entièrement contraint » et « entièrement orthogonalisé » sans augmenter le rang.
   • Décomposition : Si l'arbre n'est pas « parfait » (spécifiquement, si les règles de production sont bornées ou si le pompage n'est pas possible dans des bornes exponentielles), il est décomposé. Ces opérations diminuent strictement le rang de l'arbre KLM.
5. Terminaison et bornes : La terminaison de cette séquence de raffinement est garantie par une fonction de classement et les propriétés des séquences mauvaises (Lemme 2.1). La longueur de la séquence est bornée par la fonction de la hiérarchie à croissance rapide $F_{2k-1}$.

Contributions principales et résultats
La contribution principale est l'établissement d'une borne supérieure plus serrée pour le problème de la joignabilité des 1-TGVAS.

• Théorème principal : Le problème de la joignabilité pour les 1-TGVAS minces indexés par $k$ appartient à $F_{2k}$.
• Amélioration : Ce résultat améliore la meilleure borne supérieure connue de $F_{6k-4}$ dérivée des réductions vers des modèles VASS étendus.
• Algorithme : Les auteurs présentent un algorithme non déterministe (Algorithme 1) qui devine un arbre KLM parfait de taille bornée par une fonction dans $F_{2k-1}$. L'algorithme vérifie l'existence d'une solution au système caractéristique et vérifie de manière récursive les règles de certificat (sous-problèmes avec des indices inférieurs).
• Arbres KLM parfaits : Les auteurs prouvent qu'un arbre KLM parfait sert de certificat pour la joignabilité. Si un arbre KLM parfait possède une solution à son système caractéristique, un arbre de dérivation complet et non négatif peut être construit à partir de celui-ci sans connaître l'arbre de dérivation original.

Signification
L'article affirme qu'en adaptant la technique de décomposition KLM à la nature structurée en arbre des GVAS et en introduisant le concept d'arbres KLM, il est possible de surmonter les limitations des approches précédentes basées sur la réduction. Ce résultat fournit une caractérisation de complexité plus précise pour la sous-classe des 1-TGVAS, réduisant l'écart entre les bornes supérieures et inférieures connues. Les auteurs notent que, bien que cela améliore la borne pour les systèmes minces, la complexité exacte pour les 1-GVAS généraux reste ouverte, la meilleure borne supérieure actuelle pour le cas général étant d'ordre Ackermannien en raison de la réduction de l'état général vers l'état mince. Le travail suggère que l'indice $k$ est un paramètre crucial pour mesurer la difficulté dans ce domaine.