Unit:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Supervisors info:
Άγγελος Χαραλαμπίδης, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Χαροκόπειο Πανεπιστήμιο
Παναγιώτης Ροντογιάννης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Ε.Κ.Π.Α.
Original Title:
Bottom-Up Evaluation of Second-Order Datalog with Negation
Translated title:
Bottom-Up Evaluation of Second-Order Datalog with Negation
Summary:
Extending logic programming beyond the first-order paradigm has long been a challenge due to the complexity of handling higher-order constructs and negation. This thesis investigates the evaluation of second-order Datalog with negation, which extends the expressiveness of traditional logic programming while maintaining declarative semantics. Prior research introduced a three-valued immediate consequence operator to compute the well-founded model for higher-order programs, yet the computational overhead of this approach limits its scalability.
We propose a bottom-up evaluation framework that combines program transformation techniques with alternating fixpoint evaluation to systematically refine approximations of the well-founded model. This approach introduces a new way to handle negation in second-order logic programs and presents an alternative framework for evaluating the well-founded semantics. It contributes to a deeper understanding of higher-order logic programming and its potential use in complex reasoning tasks.
Main subject category:
Technology - Computer science
Keywords:
Logic Programming, Datalog, Bottom-Up evaluation, Well founded semantics
