Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini
Hibti, M. ; Legeard, B. ; Lombardi, H.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 205-236 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_3_205_0,
     author = {Hibti, M. and Legeard, B. and Lombardi, H.},
     title = {Une proc\'edure de d\'ecision pour un probl\`eme de satisfiabilit\'e dans un univers ensembliste h\'er\'editairement fini},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {205-236},
     mrnumber = {1483257},
     zbl = {0889.68062},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_3_205_0}
}

Hibti, M.; Legeard, B.; Lombardi, H. Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 205-236. http://gdmltest.u-ga.fr/item/ITA_1997__31_3_205_0/

1. A. Aiken et E. Wimmers, Solving Systems of Set Constraints, In 7th Symposium on LICS, 1992.

2. A. Aiken, D. Kozen et E. Wimmers, Decidability of Systems of Set Constraints with Negative Constraints, Technical Report 93-1362, Computer Science Departement, Cornell University, June 1993.

3. F. Ambert, B. Legeard et E. Legros, Constraint Logic Programming on Sets and Multisets, Workshop on Constraint Languages and their usein Problem modelling, in conjunction with ILPS'94, Ithaca, USA, pp. 151-165, November 18, 1994.

4. C. Beeri, S. Naqvi, R. Ramakrishnan, O. Shmueli, S. Tsur, Sets and negation in a logic database language (LDL1), Proceedings of the 6th Annual ACM SIGMOD Symposium on principles of Database Systems, 1987, 16, N3, pp.21-37.

5. F. M. Brown, Towards the Automation of Set Theory and its Logic, Artificial Intelligence, 1978, 10, pp.281-316. | MR 514045 | Zbl 0395.68082

6. D. Cantone, A. Ferro et E. Omodeo, Computable Set Theory, Academic Press 1990. | Zbl 0755.03024

7. A. Colmerauer, An Introduction to PROLOG III, In Communication of the A.C.M., July 1990, 33, No. 7.

8. D. Cantone, E. Omodeo et A. Policriti, The Automation of Syllogistic II. Optimization and Complexity Issues, Journal of Automated Reasoning, 1990, 6, pp. 173-187. | MR 1066797 | Zbl 0744.03015

9. M. Dincbas, P. Van Henteryck, H. Simonis, A. Aggoun, T. Graf et F. Berthier, The Constraint Logic Programming Language CHIP, Proceeding of the International Conference on Fifth generation Computer System (Tokyo88).

10. A. Dovier, E. Omodeo, E. Pontelli et G. F. Rossi, log: A Logic Programming Language With Finite Sets, Proceedings of The Eighth International Conference in Logic Programming (K.Furukawa, ed), The MIT Press, 1991, p. 111-124.

11. A. Ferro, E. Omodeo et J. T. Schwartz, Decision Procedures for Elementary Sublanguages of Set Theory. I: Multi-level syllogistic andsome Extensions, Comm. Pure and Appl. Math., 1980, XXXIII, pp. 599-608. | MR 586413 | Zbl 0453.03009

12. R. Gilleron, S. Tison et M. Tommasi, Solving Systems of Set Constraints using Tree Automata, In Proc. STACS, LNCS 665, Février 1993, Springer-Verlag, p. 505-514. | MR 1249313 | Zbl 0797.68115

13. N. Heintz et J. Jaffar, A Decision Procedure fora Class of Set Constraints, LICS 90.

14. M. Hibti, NP-Complétude du langage MLS, Mémoire de DEA de Mathématiques, Université de Franche-Comté, Septembre 1991.

15. M. Hibti, Satisfiabilité dans certains langages ensemblistes, Actes de la journée ensemble, rapport de recherche LIFO Orléans, 9 avril 1992.

16. M. Hibti, Décidabilité et Complexité de systèmes de contraintes ensemblistes, Thèse de Doctorat de Mathématiques, Université de Franche-Comté, N d'ordre 464, juin 1995.

17. M. Hibti, H. Lombardi et B. Legeard, Deciding in HFS-Theory via Linear Integer Programming with Application to Set-Unification, in Proc. of the 4th International Conference on Logic Programming and Automated Reasoning LPAR 93, St Petersbourg, pp. 170-181, Springer LNCS 698. | MR 1251075 | Zbl 0790.90052

18. M. Hibti, B. Legeard et H. Lombardi, Decision Procedure for Constraintsover Sets Multisets and Sequences, Research report LAB-RRIAP 9402.

19. J. Jaffar et J. L. Lassez, Constraint Logic Programming, Proceedings of the 14th ACM Conference on Principle of Programming Languages, POPL, Munich, 1987, pp. 111-119.

20. J. Jaffar et M. K. Maher, Constraint Logic Programming: A Survey, J. of Logic Programming, May/July, 1994, 19/20, pp. 503-582. | MR 1279934

21. D. Kapur et P. Narendran, NP-Completeness of the Set Unification and Matching Problems, Proc. of the ICAD, Oxford, July 1986, Springer LNCS 230, 489-495. | MR 876524 | Zbl 0643.68054

22. G. M. Kuper, Logic Programming with Sets, Research Report IBM Yorktown Heights, RC 12378, Dec. 1987.

23. B. Legeard, H. Lombardi, E. Legros et M. Hibti, A Satisfaction Approach to Set Unification, in Proceedings of the 13th International Conference on Artificial Intelligence, Expert Systems and Natural Language, EC2, Avignon, 1993, 1, pp. 265-276.

24. A. K. Mackworth, "Consistency in Network of Relations", Journal of Artificial Intelligence, 1977, 8, n° 1, pp.99-118. | Zbl 0341.68061

25. B. A. Nadel, Constraints Satisfaction Algorithms, Journal of Computer Intelligence, 1989, 5, pp. 188-224.

26. A. Policriti, NP-completeness of MLS, technical report, University of Udine, 1990.

27. F. Parlamento et A. Policriti, Decision Procedures for Elementary Sub-languages of Set Theory. XIII: Model Graph, Reflexion and Decidability, Journal of Automated Reasoning, 1991, 7. | MR 1118329 | Zbl 0734.03006

28. F. Parlamento et A. Policriti, Undecidability Results for Restricted Universallu Quantified Formulae of Set Theory, Com. on Pure and Applied Mathematics, 1993, XLVI, pp. 57-73. | MR 1193343 | Zbl 0797.03005

29. D. Pastre, Automatic Theorem Proving in Set Theory, Artificial Intelligence, 1978, 10, pp. 1-27. | MR 496431 | Zbl 0374.68059

30. K. J. Perry, K. V. Palem, K. Mcaloon et G. M. Kuper, The Complexity of Logic Programming with Sets, Research Report IBM Yorktown Heights, RC 12887, 1987.

31. J. H. Siekmann, Unification Theory, in Unification, Edited by C. Kirchner, Academic Press, 1990, pp. 1-68. | MR 1090370

32. R. Sigal, Desiderata for Logic Programming with Sets, GULP Proceedings of the 4th National Conference on Logic Programming, 1989, pp. 127-141, Bologna.

33. Y. Sato, K. Sakai et S. Menju, SetCAL- a Solver of Set Constraints in CAL System, Technical Report TM-0963, ICOT, 1990.

34. J. T. Schwarts, R. B. Dewar, E. Dubinsky et E. Schonberg, Programming with Sets - An Introduction to SETL, 493 pages, Springer-Verlag Editions, Berlin, 1986. | Zbl 0604.68001

35. E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.

36. P. Van Hentenryck, Constraint Satisfaction in Logic Programming, The MIT Press, 224 pages, 1989. | MR 1013366