محبوبترین نویسندگان :
نویسندگان مقالات پربازدید :
مجله استدلال خودکار 2013
جزئیات رویداد
همایش ، رویداد ، ژورنال
اینستاگرام تی پی بین

  • dealing with satisfiability and n-ary csps in a logical framework

    نویسندگان :
    کلمات کلیدی :
    جزئیات بیشتر مقاله
    • تاریخ ارائه: 1392/07/24
    • تاریخ انتشار در تی پی بین: 1392/07/24
    • تعداد بازدید: 756
    • تعداد پرسش و پاسخ ها: 0
    • شماره تماس دبیرخانه رویداد: -
     we investigate in this work a generalization of the known cnf representation that we call general normal form (gnf) and extend the resolution rule of robinson to design a new sound and complete resolution proof system for the gnf. we show that by using a cardinality operator in the gnf we obtain the new representation cgnf that allows a natural and efficient boolean encoding for n-ary finite discrete extensional csps. we prove that the space complexity of a csp encoded in thecgnf is identical to its space complexity when it is expressed in the classical csp representation. we prove that the generalized resolution rule applies for the cgnf encoding and introduce a new inference rule whose application until saturation achieves arc-consistency in a linear time complexity for n-ary csp expressed in the cgnf encoding. two enumerative methods for solving csp instances encoded in this boolean framework are studied: the first one (equivalent to mac in csps) maintains full arc-consistency at each node of the search tree while the second (equivalent to fc in csps) performs partial arc-consistency on each node. both methods are experimented and compared on some instances of the ramsey problem, randomly generated 3/4-ary csps and promising results are obtained. we also adapted the notion of clause learning defined in sat for thecgnf encoding. finally, we show how the proposed inference rule can be used to achieve path-consistency in the case of binary csps encoded in cgnf, and how it can be used to enforce strong path consistency when it is combined with the generalized resolution rule.

سوال خود را در مورد این مقاله مطرح نمایید :

با انتخاب دکمه ثبت پرسش، موافقت خود را با قوانین انتشار محتوا در وبسایت تی پی بین اعلام می کنم
مقالات جدیدترین رویدادها
مقالات جدیدترین ژورنال ها