diaporama

article

Il est bien connu que la classe des treillis générés par les CFGs est strictement incluse dans la classe des treillis supérieurement localement distributifs (upper locally distributive lattices). Cependant une caractérisation complète pour cette classe est toujours une question ouverte. Nous allons résoudre ce problème en donnant une condition complète pour cette classe. Cette condition permet de créer un algorithme en temps polynomial pour la construction de CFGs qui génèrent un treillis donné, si un tel CFG existe. Pour aller plus loin, nous résoudrons le même problème pour deux autres classes de treillis qui sont générés par des CFGs sur la classe des graphes non orientés, et celle des graphes orientés acycliques.