-
generalising unit-refutation completeness and slur via nested input resolution
جزئیات بیشتر مقاله- تاریخ ارائه: 1392/07/24
- تاریخ انتشار در تی پی بین: 1392/07/24
- تعداد بازدید: 869
- تعداد پرسش و پاسخ ها: 0
- شماره تماس دبیرخانه رویداد: -
the class slur (single lookahead unit resolution) was introduced in schlipf et al. (inf process lett 54:133–137, 1995) as an umbrella class for efficient (poly-time) sat solving, with linear-time sat decision, while the recognition problem was not considered. čepek et al. (2012) and balyo et al. (2012) extended this class in various ways to hierarchies covering all of cnf (all clause-sets). we introduce a hierarchy slurk which we argue is the natural “limit” of such approaches. the second source for our investigations is the class uc of unit-refutation complete clause-sets, introduced in del val (1994) as a target class for knowledge compilation. via the theory of “hardness” of clause-sets as developed in kullmann (1999), kullmann (ann math artif intell 40(3–4):303–352, 2004) and ansótegui et al. (2008) we obtain a natural generalisation uck, containing those clause-sets which are “unit-refutation complete of level k”, which is the same as having hardness at most k. utilising the strong connections to (tree-)resolution complexity and (nested) input resolution, we develop basic methods for the determination of hardness (the level k in uck). a fundamental insight now is that slurk=uck holds for all k. we can thus exploit both streams of intuitions and methods for the investigations of these hierarchies. as an application we can easily show that the hierarchies from čepek et al. (2012) and balyo et al. (2012) are strongly subsumed by slurk. finally we consider the problem of “irredundant” clause-sets in uck. for 2-cnf we show that strong minimisations are possible in polynomial time, while already for (very special) horn clause-sets minimisation is np-complete. we conclude with an extensive discussion of open problems and future directions. we envisage the concepts investigated here to be the starting point for a theory of good sat translations, which brings together the good sat-solving aspects from slur together with the knowledge-representation aspects from uc, and expands this combination via notions of “hardness”.
مقالات جدیدترین رویدادها
-
استفاده از تحلیل اهمیت-عملکرد در ارائه الگوی مدیریت خلاقیت سازمانی و ارائه راهکار جهت بهبود
-
بررسی تاثیر ارزش وجوه نقد مازاد بر ساختار سرمایه شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر سطح افشای ریسک بر قرارداد بدهی شرکت های پذیرفته شده در بورس اوراق بهادار تهران
-
بررسی تأثیر رتبه بندی اعتباری مبتنی بر مدل امتیاز بازار نوظهور بر نقد شوندگی سهام با تأکید بر خصوصی سازی شرکت ها
-
تأثیر آمیخته بازاریابی پوشاک ایرانی بر تصویر ذهنی مشتری پوشاک ایرانی (هاکوپیان)
-
بررسی نقش فعالیت بدنی در سلامت جسمانی، روانی و اجتماعی خانواده از دیدگاه اسلام
-
بررسی تاثیر زاویه موج و ضخامت مقطع در رفتار چرخه ای مهاربندهای فولادی موج دار ذوزنقه ای
-
آیا درجه ی ارزشیابی بیمارستان های تحت پوشش دانشگاه علوم پزشکی تهران با عملکرد آن ها رابطه دارد؟
-
بررسی ارتباط ژئوشیمی عناصر جزئی و نادر خاکی با کانی های مزاحم فسفاته در معدن شماره 1 شرکت صنعتی و معدنی گل گهر سیرجان استان کرمان
-
tachyonic teleparallel dark energy
مقالات جدیدترین ژورنال ها
-
مدیریت و بررسی افسردگی دانش آموزان دختر مقطع متوسطه دوم در دروان کرونا در شهرستان دزفول
-
مدیریت و بررسی خرد سیاسی در اندیشه ی فردوسی در ادب ایران
-
واکاوی و مدیریت توصیفی قلمدان(جاکلیدی)ضریح در موزه آستان قدس رضوی
-
بررسی تاثیر خلاقیت، دانش و انگیزه کارکنان بر پیشنهادات نوآورانه کارکنان ( مورد مطالعه: هتل های 3 و 4 ستاره استان کرمان)
-
بررسی تاثیر کیفیت سیستم های اطلاعاتی بر تصمیم گیری موفق در شرکتهای تولیدی استان اصفهان (مورد مطالعه: مدیران شرکتهای تولیدی استان اصفهان)
-
بررسی نتایج حمایت های مالی دولت بر عملکرد و موفقیت شرکت های پارک علم و فناوری زاهدان
-
اثر بخشی آموزش ذهن آگاهی بر اضطراب امتحان دانش آموزان دختر دبیرستانی
-
بررسی مفاهیم شخصیت و نظریه های مختلف مرتبط با آن
-
ارائه الگوی توسعه صادرات فرش ایران در دوره پسابرجام
-
نقش فناوری نوظهور دیجیتالی در هوشمند سازی فرایندهای کسب و کار بازاریابی
سوال خود را در مورد این مقاله مطرح نمایید :