Regular ${D}$-length: A tool for improved prefix-stable forward Ramsey factorisations

Théodore Lopez (1) , Benjamin Monmege (1) , Jean-Marc Talbot (1)

1 MOVE - Modélisation et Vérification

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.

Keywords: Ramsey factorisation; Green’s relations; Fast infix query evaluation

Domains: Logic in Computer Science [cs.LO]; Computation and Language [cs.CL]; Formal Languages and Automata Theory [cs.FL]

Théodore Lopez, Benjamin Monmege, Jean-Marc Talbot. Regular ${D}$-length: A tool for improved prefix-stable forward Ramsey factorisations. Information Processing Letters, 2024, 187, pp.106497. ⟨10.1016/j.ipl.2024.106497⟩. ⟨hal-04562306⟩