Discussion:Construction de Glushkov

Une question

A l'étape 3, on a la formule : $L=PA^{*}\cap A^{*}D\cap A^{*}(A^{2}\setminus F)A^{*}$, je ne comprends pas bien le dernier morceau, n'est-ce pas le complémentaire ? J'hésite à modifier tout seul. --Roll-Morton (discuter) 5 octobre 2015 à 18:07 (CEST)

Oui, c'est le contraire, j'avais pas les yeux en face des trous. ManiacParisien (discuter) 5 octobre 2015 à 20:34 (CEST)

:) --Roll-Morton (discuter) 6 octobre 2015 à 10:19 (CEST)

Merci

Traduit vers l'anglais Arthur MILCHIOR (discuter)

Complexité non linéaire

Il me semble que l'analyse de complexité de l'algorithme est fausse: Le calcul des facteurs $F(L)$ se fait au minimum en O(nˆ2) En effet, l'ensemble des facteurs est une partie de $\Sigma \times \Sigma$ et peut contenir une grande partie des facteurs de taille 2 du langage. 2A02:8440:610C:B714:206D:B5AA:69F9:793B (discuter) 20 octobre 2022 à 21:08 (CEST)

Dénomination de l'algorithme

Le papier de Glushkov semble bien antérieur (1961) au papier de Berry & Sethi (1986). Je suppose que c'est ce qui a motivé de choisir d'appeler cet article d'après le premier plutôt que les seconds. Est-ce que quelqu'un peut confirmer ?

Par ailleurs, est-ce que quelqu'un saurait pourquoi la dénomination « Algorithme de Berry-Sethi » est si répandue ? Luuuuc (discuter) 9 décembre 2023 à 17:31 (CET)