Suppression efficace de transitions spontanées dans Vcsn

Auteurs

Antoine Pietri

Type

techreport

Année

2015

Numéro

1504

Résumé

Ce rapport expose des fac c ons performantes et génériques d'implémenter la suppression de transitions spontanées dans un varepsilon-NFA. Nous comparons deux approches : l'algorithme d'varepsilon-clôture de J. Sakarovitch et S. Lombardyet l'algorithme d'varepsilon-suppression de M. Mohri. Nous discutons de la fac c on dont ces algorithmes peuvent être implémentés dans le cas d'automates pondérés génériques, ainsi que de leur performance, en comparant des résultats empiriques obtenus dans Vcsn.