📖
Résolution de contraintes du premier ordre dans la théorie des arbres évalués
Thi-Bich-Hanh Dao, Khalil Djelloul

Résolution de contraintes du premier ordre dans la théorie des arbres évalués

Author / Organization:
Science & Mathematics Published 2006 Verification Pending

Overview & Synopsis

Nous présentons dans ce papier un algorithme général de résolution de contraintes du premier ordre dans la théorie T des arbres évalués. Cette théorie est une combinaison de la théorie des arbres finis ou infinis et de la théorie des rationnels munis de l'addition, de la soustraction et d'une relation d'ordre dense sans extrême. L'algorithme est donné sous forme d'un ensemble de 28 règles de réécriture et transforme toute formule du premier ordre ', qui peut éventuellement contenir des variables libres, en une disjonction D de formules résolues, équivalente à ' dans T, sans nouvelles variables libres, et telle que D est soit la formule vrai , soit la formule faux , soit une formule ayant au moins une variable libre et n'étant équivalente ni à vrai ni à faux dans T. En particulier, si ' est sans variables libres, D est soit la formule vrai soit la formule faux . Si D contient des variables libres, les solutions sur ces variables sont exprimées d'une façon explicite et D peut se transformer directement en une combinaison booléenne de conjonctions quantifiées de formules atomiques, qui n'acceptent pas d'élimination de quantificateurs. La correction de notre algorithme est une autre preuve de la complétude de la théorie T.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Résolution de contraintes du premier ordre dans la théorie des arbres évalués
Author / Organization Thi-Bich-Hanh Dao, Khalil Djelloul
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2006
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-166752
Original Source Link Visit Source Page on hal.science »