Research indexThesis
Simplifying transducers using sequentiality
Villevalois
26 Nov 2019Open access
NobleIDark:/48914/w1/20261105/B60F40C3DOI10.70675/28c6ed2ez142bz46b3zaed1zdd6eced3d708
Simplifying transducers using sequentiality
Villevalois · 2019
NobleIDark:/48914/w1/20261105/B60F40C3DOI10.70675/28c6ed2ez142bz46b3zaed1zdd6eced3d708
Abstract
Simplification de transducteurs en utilisant la séquentialité La synthèse est un domaine de l'informatique consistant à générer des programmes à partir de spécifications abstraites. Les spécifications sont souvent décrites à l'aide d'un formalisme logique et les programmes sont obtenus sous la forme de modèles de transformation. Alors qu'il est utile de pouvoir exprimer les propriétés des spécifications avec du non-déterminisme, nous souhaitons en général obtenir des modèles déterministes pour des raisons évidentes d'efficacité. Ceci nous amène à vouloir simplifier les modèles synthétisés afin d'optimiser leur évaluation ou leur représentation concrète dans un programme.Dans cette thèse, les modèles de transformations qui nous intéressent sont exprimés par des Streaming String Transducers (SSTs) [AČ10 ; AČ11]. Un SST est un automate fini déterministe équipé d'un nombre fini de registres qui peuvent être utilisés pour élaborer un mot de sortie. Ces registres peuvent être mis à jour en utilisant la concatenation de registres ou en les préfixant ou suffixant par des mots finis. Nous sommes intéressés par le problème ambitieux de la minimisation de registres, qui consiste, étant donné un SST, à calculer un SST équivalent avec un nombre minimal de registres. Comme première étape à la prise en compte de ce modèle très expressif, nous contraignons la manière dont les registres sont manipulés: ils ne peuvent pas être concaténés les uns aux autres (cette classe est appelée Concatenation-Free SST).Nous présentons deux contributions principales. Tout d'abord, nous élaborons une procédure permettant de minimiser le nombre de registres dans la classe des Copyless Appending SSTs (dans cette classe, les registres ne peuvent qu'être [...]