Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini

M. Hibti; B. Legeard; H. Lombardi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)

  • Volume: 31, Issue: 3, page 205-236
  • ISSN: 0988-3754

How to cite


Hibti, M., Legeard, B., and 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 31.3 (1997): 205-236. <http://eudml.org/doc/92559>.

author = {Hibti, M., Legeard, B., Lombardi, H.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {hereditarily finite sets},
language = {fre},
number = {3},
pages = {205-236},
publisher = {EDP-Sciences},
title = {Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini},
url = {http://eudml.org/doc/92559},
volume = {31},
year = {1997},

AU - Hibti, M.
AU - Legeard, B.
AU - Lombardi, H.
TI - Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1997
PB - EDP-Sciences
VL - 31
IS - 3
SP - 205
EP - 236
LA - fre
KW - hereditarily finite sets
UR - http://eudml.org/doc/92559
ER -


  1. 1. A. AIKEN et E. WIMMERS, Solving Systems of Set Constraints, In 7th Symposium on LICS, 1992. Zbl0834.68105
  2. 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. Zbl0834.68105
  3. 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. 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. 5. F. M. BROWN, Towards the Automation of Set Theory and its Logic, Artificial Intelligence, 1978, 10, pp.281-316. Zbl0395.68082MR514045
  6. 6. D. CANTONE, A. FERRO et E. OMODEO, Computable Set Theory, Academic Press 1990. Zbl0755.03024
  7. 7. A. COLMERAUER, An Introduction to PROLOG III, In Communication of the A.C.M., July 1990, 33, No. 7. Zbl0679.68045
  8. 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. Zbl0744.03015MR1066797
  9. 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. 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. Zbl0874.68056
  11. 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. Zbl0453.03009MR586413
  12. 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. Zbl0797.68115MR1249313
  13. 13. N. HEINTZ et J. JAFFAR, A Decision Procedure fora Class of Set Constraints, LICS 90. 
  14. 14. M. HIBTI, NP-Complétude du langage MLS, Mémoire de DEA de Mathématiques, Université de Franche-Comté, Septembre 1991. 
  15. 15. M. HIBTI, Satisfiabilité dans certains langages ensemblistes, Actes de la journée ensemble, rapport de recherche LIFO Orléans, 9 avril 1992. 
  16. 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. 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. Zbl0790.90052MR1251075
  18. 18. M. HIBTI, B. LEGEARD et H. LOMBARDI, Decision Procedure for Constraintsover Sets Multisets and Sequences, Research report LAB-RRIAP 9402. Zbl0889.68062
  19. 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. 20. J. JAFFAR et M. K. MAHER, Constraint Logic Programming: A Survey, J. of Logic Programming, May/July, 1994, 19/20, pp. 503-582. Zbl0900.68127MR1279934
  21. 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. Zbl0643.68054MR876524
  22. 22. G. M. KUPER, Logic Programming with Sets, Research Report IBM Yorktown Heights, RC 12378, Dec. 1987. 
  23. 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. 24. A. K. MACKWORTH, "Consistency in Network of Relations", Journal of Artificial Intelligence, 1977, 8, n° 1, pp.99-118. Zbl0341.68061
  25. 25. B. A. NADEL, Constraints Satisfaction Algorithms, Journal of Computer Intelligence, 1989, 5, pp. 188-224. 
  26. 26. A. POLICRITI, NP-completeness of MLS, technical report, University of Udine, 1990. 
  27. 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. Zbl0734.03006MR1118329
  28. 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. Zbl0797.03005MR1193343
  29. 29. D. PASTRE, Automatic Theorem Proving in Set Theory, Artificial Intelligence, 1978, 10, pp. 1-27. Zbl0374.68059MR496431
  30. 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. Zbl0784.68042
  31. 31. J. H. SIEKMANN, Unification Theory, in Unification, Edited by C. Kirchner, Academic Press, 1990, pp. 1-68. Zbl0704.68096MR1090370
  32. 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. 33. Y. SATO, K. SAKAI et S. MENJU, SetCAL- a Solver of Set Constraints in CAL System, Technical Report TM-0963, ICOT, 1990. 
  34. 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. Zbl0604.68001
  35. 35. E. TSANG, Foundations of Constraint Satisfaction, Academic Press, 1993. 
  36. 36. P. VAN HENTENRYCK, Constraint Satisfaction in Logic Programming, The MIT Press, 224 pages, 1989. MR1013366

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.