Utilisateur : sieghttct

Carton en donne une version naïve (AFN puis déterminisation), qui montre seulement le résultat théorique, mais le développement devient intéressant si l'on calcule directement un AFD pas trop énorme, ce que font Aho et al.'

Pour Tykhonoff dénombrable, on pourra voir chez Queffélec. Le PDF ci-joint, dû à Benjamin Dadoun (que je remercie !), donne la preuve du théorème de compacité et deux applications classiques.'

'

'

'

'

'

'

'

Le programme ne parle que de $\lambda$-calcul pur, ça peut donc paraître étonnant de mettre du typage ici. Néanmoins, le typage d'un terme est une méthode efficace pour prouver qu'il est (fortement) normalisant ! C'est l'intérêt du théorème rappelé en début de développement. Pour la leçon 923, le rapport 2017 rappelle aussi qu'on peut introduire des bouts d'analyse sémantique, cet algo y trouve donc aussi toute sa place.'

'

On propose aussi une adaptation de l'algo pour rechercher (sans trop de finesse) les facteurs d'un mot $w$ à distance d'édition au plus $k$ de $w$.'

À présenter tranquillement, en agitant beaucoup les mains...'

'

Papadimitriou pour 2-SAT, Cormen pour CLIQUE.'