Tez No	İndirme	Tez Künye	Durumu
255311		Using model generation theorem provers for the computation of answer sets / Yanıt kümelerinin hesaplanmasında model oluşturabilen teorem ispatlayıcılarının kullanılması Yazar:ORKUNT SABUNCU Danışman: DOÇ. DR. FERDA NUR ALPASLAN Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Bilgi gösterimi = Information display ; Mantıksal programlama = Logic programming ; Teorem ispatlayıcı = Theorem prover	Onaylandı Doktora İngilizce 2009 114 s.
Yanıt kümesi programlama, arama problemlerinin çözülmesinde kullanılan bildirimsel bir yaklaşımdır. Sonuçların yerine koyma yöntemiyle alındığı ispat tabanlı bir yaklaşım değildir. Problemi temsil eden mantık program öyle oluşturulur ki programın yanıt kümesi anlam bilimine göre bulunan modelleri, problemin çözümlerine karşılık gelir.Mantık programının yanıt kümeleri yanıt kümesi çözümleyicisi (Smodels, Cmodels, Clasp ve Dlv) tarafından bulunur. Kullanıcılar kullanım rahatlığı açısından değişkenlerin olduğu programlar yazsalar da, şimdiki yanıt kümesi çözümleyiciler değişkenlerin olmadığı yalın programlarla çalışmaktadır. Yanıt kümesi programlamanın indirgeme süreci, değişkenlerin olduğu bir programın sadece önermelerden oluşan halini oluşturur. İndirgeme süreci çok büyük bir program oluşturabilir. Bu da yanıt kümesi çözümleyicilerinin işini zorlaştırabilir.Model oluşturabilen teorem ispatlayıcılar (Paradox, Darwin ve FM-Darwin) niceleme mantığında verilen bir teori doğru olduğu zaman, teoriyi doğrulayan modeli oluşturabilme yeteneğine sahiptir. Bu çalışmada model oluşturabilen teorem ispatlayıcılarının yanıt kümesi programlamada hesaplayıcı sistem olarak kullanılması önerilmektedir. Ana motivasyon yanıt kümesi programlamada bulunan indirgeme sürecinin kaldırılmasını ya da model oluşturabilen sistemler tarafından daha verimli bir şekilde yapılmasını sağlamaktır. Ayrıca, indirgeme süreci dışında, model oluşturabilen teorem ispatlayıcılar şimdiki yanıt kümesi çözümleyicilerinden daha iyi performans gösterebilir. Önerilen yöntem yanıt kümelerini doğruluk çözümleyicilerini kullanarak bulmaya çalışan yöntemin niceleme mantığı seviyesine çıkarılması olarak görülebilir.Bu çalışmada bir mantık programını niceleme mantığı önermelerine çeviren tamamlamaişleminden yararlanılmıştır. Tamamlama dışında, model oluşturabilen teorem ispatlayıcılara uygun girdiyi oluşturmak için gerekli dönüşümler de incelenmiştir. Tüm bu dönüşümleri gerçekleştirebilen Completor adında bir sistem geliştirilmiştir. Deneysel sonuçlar Completor ve teorem ispatlayıcılarını birlikte kullanmanın yanıt kümelerininhesaplanmasında etkili bir yöntem olduğunu göstermiştir. Özellikle Paradox'un deneylerdeki zaman sonuçları Completor ve Paradox'u birlikte yanıt kümesi çözümleyiciler yerine kullanmanın daha avantajlı olacağını göstermiştir. Bu avantaj sadece önermelerden oluşan halinin çok büyük olduğu programlar için daha açık olarak gözlenmiştir; çünkü bu tür programlar için indirgeme süreci darboğaz teşkil etmektedir.
Answer set programming (ASP) is a declarative approach to solving search problems. Logic programming constitutes the foundation of ASP. ASP is not a proof-theoretical approach where you get solutions by answer substitutions. Instead, the problem is represented by a logic program in such a way that models of the program according to the answer set semantics correspond to solutions of the problem.Answer set solvers (Smodels, Cmodels, Clasp, and Dlv) are used for finding answer sets of a given program. Although users can write programs with variables for convenience, current answer set solvers work on ground logic programs where there are no variables. The grounding step of ASP generates a propositional instance of a logic program with variables. It may generate a huge propositional instance and make the search process of answer set solvers more difficult.Model generation theorem provers (Paradox, Darwin, and FM-Darwin) have the capability of producing a model when the first-order input theory is satisfiable. This work proposes the use of model generation theorem provers as computational engines for ASP. The main motivation is to eliminate the grounding step of ASP completely or to perform it more intelligently using the model generation system. Additionally, regardless of grounding, model generation systems may display better performance than the current solvers. The proposed method can be seen as lifting SAT-based ASP, where SAT solvers are used to compute answer sets, to the first-order level for tight programs.A completion procedure which transforms a logic program to formulas of first-order logic is utilized. Besides completion, other transformations which are necessary for forming a firstorder theory suitable for model generation theorem provers are investigated. A system called Completor is implemented for handling all the necessary transformations. The empirical results demonstrate that the use of Completor and the theorem provers together can be an efective way of computing answer sets. Especially, the run time results of Paradox in the experiments has showed that using Completor and Paradox together is favorable compared to answer set solvers. This advantage has been more clearly observed for programs with large propositional instances, since grounding can be a bottleneck for such programs.