Regular ${D}$-length: A tool for improved prefix-stable forward Ramsey factorisations
Résumé
Recently, Jecker has introduced and studied the regular ${D}$-length of a monoid, as the length of its longest chain of regular ${D}$-classes. We use this parameter in order to improve the construction, originally proposed by Colcombet, of a deterministic automaton that allows to map a word to one of its forward Ramsey splits: these are a relaxation of factorisation forests that enjoy prefix stability, thus allowing a compositional construction. For certain monoids that have a small regular ${D}$-length, our construction produces an exponentially more succinct deterministic automaton. Finally, we apply it to obtain better complexity result for the problem of fast infix evaluation.
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY NC SA - Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales
licence : CC BY NC SA - Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales