Spelling suggestions: "subject:"destinés dde nézondet"" "subject:"destinés dde blondet""
1 |
Utilisation des destinées pour la décision et sa complexité dans le cas de formules à profondeur de quantification bornée sur des structures logiques finies et infiniesChateau, Annie 01 July 2003 (has links) (PDF)
Nous étudions les structures logiques finies ou infinies à travers les énoncés de profondeur de quantification donnée qui sont vrais dans ces structures. <br /><br />Cette étude porte principalement sur un nouvel outil logique appelé $k$-destinées de Nézondet. Une $k$-destinée d'une structure consiste en une présentation arborescente des types de $k$-isomorphisme de Fraïssé de la structure. Nous analysons ce nouvel outil, en particulier nous montrons que les destinées s'intègrent parfaitement au contexte des $k$-isomorphismes de Fraïssé et des jeux d'Ehrenfeucht. <br /><br />Nous détaillons un algorithme de décision utilisant les destinées. Nous comparons en détail les structures dont on peut construire récursivement les destinées et les structures $H$-bornées. Enfin, nous donnons quelques résultats intermédiaires du problème NE ?= CoNE et de sa version logique, la conjecture du Spectre.
|
Page generated in 0.1023 seconds