Abstract:

In Vaucanson, Finite State Machines are mathematically defined by an algebraic structure module called Algebra. Considering the algebraic mathematical definitions, however, the current design is inaccurate: some hierarchical relations are false (for example, the inheritance between semirings and monoids). Moreover, we are unable to add new algebraic structures easily.

Therefore, in order to give Algebra more granularity in its algebraic concept definitions, it is necessary to rework its current structure by introducing a property based class hierarchy similar to the one presented in SCOOP. Using the mathematical operator and set properties to define algebraic structures, as opposed to a usual class hierarchy, we would be able to specialize algorithms more precisely thanks to structure property verifications, thus increasing Vaucanson's performance and expressiveness.

Résumé :

Le module de structures algébriques de Vaucanson, Algebra, sert de base à la définition mathématique des automates finis. Cependant la modélisation actuelle est inexacte du point de vue théorique : les relations d’héritages entre certaines classes sont fausses (l’héritage entre les semi-anneaux et les monoïdes en est le parfait exemple). D’autre part, nous ne pouvons facilement l’étendre avec de nouvelles structures algébriques.

Ainsi, afin de doter Algebra d’une plus grande granularité dans sa définition des concepts algébriques, il est nécessaire de retravailler sa structure globale en introduisant un système de hiérarchie par propriétés similaire à celui présenté dans SCOOP. En se basant sur les propriétés des opérateurs et des ensembles mathématiques pour définir la nature des structures algébriques, et non sur une hiérarchie de classes classique, nous pourrons nous permettre une spécialisation plus précise des algorithmes grâce à la garantie de propriétés sur ces structures, entraˆınant ainsi un gain de performance et d’expressivité important au coeur de Vaucanson.

• Report : hamelin-property-based-algebra.pdf