Abstract FR:

Nous étudions dans cette thèse la recherche d'un motif homomorphe dans un texte et montrons que ce problème est NP-complet. Nous établissons une première classification des motifs: les motifs simples (ou motifs élémentaires) et les motifs non simples. Nous donnons une caractérisation de la rationalité des motifs simples. Nous proposons ensuite une classification des motifs simples selon leurs degrés, ainsi qu'un algorithme efficace de recherche dans un texte des images de tout motif de degré un ou deux, qui fait gagner, ou presque gagner, un ou deux degrés de complexité par rapport à l'algorithme naïf que nous présentons également. Nous proposons enfin une généralisation de cet algorithme à toute classe de motifs de degré supérieur ou égal à deux. Nous nous inspirons du cas de la classe des motifs de degré un pour proposer un algorithme efficace de résolution des équations aux mots à une variable