Direct and dual laws for automata with multiplicities

Gérard Henry Edmond Duchamp (1) , Marianne Flouret (2) , Eric Laugerotte (3) , Jean-Gabriel Luque (4)

1 LIPN - Laboratoire d'Informatique de Paris-Nord
2 LIH - Laboratoire d'informatique du Havre
3 LIFAR - Laboratoire d'informatique fondamentale et appliquée de Rouen
4 LIGM - Laboratoire d'Informatique Gaspard-Monge

We present here theoretical results coming from the implementation of the package called AMULT (automata with multiplicities in several noncommutative variables). We show that classical formulas are ``almost every time'' optimal, characterize the dual laws preserving rationality and also relators that are compatible with these laws.

Mots clés: Automata with multiplicities; rational laws; dual laws; congruences; shuffle compatibility

Domaines: Combinatoire [math.CO]; Algorithme et structure de données [cs.DS]; Calcul formel [cs.SC]

Gérard Henry Edmond Duchamp, Marianne Flouret, Eric Laugerotte, Jean-Gabriel Luque. Direct and dual laws for automata with multiplicities. Theoretical Computer Science, 2001, 267 (1-2), pp.105-120. ⟨hal-00085316v2⟩