# Browsing by Subject "Logic programming"

Now showing 1 - 4 of 4

- Results Per Page
1 5 10 20 40 60 80 100

- Sort Options
Ascending Descending

Item Formal methods for answer set programming(2017-12) Harrison, Amelia J.; Lifschitz, Vladimir; Boyer, Robert S.; Dillig, Isil; Hunt, Jr. , Warren A.; Schaub, TorstenShow more Answer set programming (ASP) is a declarative programming paradigm for the design and implementation of knowledge-intensive applications, particularly useful for modeling problems involving combinatorial search. The input languages of the first ASP software systems had the attractive property of a simple, fully specified declarative semantics, making it possible to use formal methods to analyze ASP programs -- to verify correctness, for example, or to show that two programs were equivalent. Since that time, many useful new constructs have been added to input languages. The increase in usability, however, has come at the expense of a fully specified semantics, as the semantics of newer constructs has not quite kept pace with the most general syntax that solvers can handle. In this thesis, we will describe one approach to bridging the gap between mathematical formulations of the semantics of ASP languages and the current state of the languages themselves. Our approach is to view ASP programs as corresponding to infinitary formulas (formulas with infinitely long conjunctions and disjunctions).Show more Item Integrating top-down and bottom-up approaches in inductive logic programming: applications in natural language processing and relational data mining(2003) Tang, Lap Poon Rupert; Mooney, Raymond J. (Raymond Joseph)Show more Inductive Logic Programming (ILP) is the intersection of Machine Learning and Logic Programming in which the learner’s hypothesis space is the set of logic programs. There are two major ILP approaches: top-down and bottom-up. The former searches the hypothesis space from general to specific while the latter the other way round. Integrating both approaches has been demonstrated to be more effective. Integrated ILP systems were previously developed for two tasks: learning semantic parsers (Chillin), and mining relational data (Progol). Two new integrated ILP systems for these tasks that overcome limitations of existing methods will be presented. Cocktail is a new ILP algorithm for inducing semantic parsers. For this task, two features of a parse state, functional structure and context, provide important information for disambiguation. A bottom-up approach is more suitable for learning the former, while top-down is better for the latter. By allowing both approaches to induce program clauses and choosing the best combination of their results, Cocktail learns more effective parsers. Experimental results on learning natural-language interfaces for two databases demonstrate that it learns more accurate parsers than Chillin, the previous best method for this task. Beth is a new integrated ILP algorithm for relational data mining. The Inverse Entailment approach to ILP, implemented in the Progol and Aleph systems, starts with the construction of a bottom clause, the most specific hypothesis covering a seed example. When mining relational data with a large number of background facts, the bottom clause becomes intractably large, making learning very inefficient. A top-down approach heuristically guides the construction of clauses without building a bottom clause; however, it wastes time exploring clauses that cover no positive examples. By using a top-down approach to heuristically guide the construction of generalizations of a bottom clause, Beth combines the strength of both approaches. Learning patterns for detecting potential terrorist activity is a current challenge problem for relational data mining. Experimental results on artificial data for this task with over half a million facts show that Beth is significantly more efficient at discovering such patterns than Aleph and m-Foil, two leading ILP systems.Show more Item Representing actions in logic-based languages(2014-05) Yang, Fangkai; Lifschitz, VladimirShow more Knowledge about actions is an important part of commonsense knowledge studied in Artificial Intelligence. For decades, researchers have been developing methods for describing how actions affect states of the world and for automating reasoning about actions. In recent years, significant progress has been made. In particular, the frame problem has been solved using nonmonotonic knowledge representation formalisms, such as logic programming under the answer set semantics. New theories of causality have allowed us to express causal dependencies between fluents, which has proved essential for solving the ramification problem. It has been shown that reasoning about actions described by logic programs and causal theories can be automated using answer set programming. Action description languages are high level languages that allow us to represent knowledge about actions more concisely than when logic programs are used. Many action description languages have been described in the literature, including B, C, and C+. Reasoning about dynamic domains described in languages C and C+ can be performed automatically using the Causal Calculator (CCalc), which employs SAT solvers for search, and the systems coala and cplus2asp, which employ answer set solvers such as clingo. The dissertation addresses problems of three kinds. First, we study some mathematical properties of expressive action languages based on nonmonotonic causal logic that were not well understood until now. This includes causal rules expressing synonymy, nondefinite causal rules, and nonpropositional causal rules. We generalize existing translations from nonmonotonic causal theories to logic programming under the answer set semantics. This makes it possible to automate reasoning with a wider class of causal theories by calling answer set solvers. Second, we design and study a new action language BC, which is more expressive in some ways than the existing and previously proposed languages. We develop a framework that combines the most useful expressive features of the languages B and C+, and use program completion to characterize the effects of actions described in these languages. Third, we illustrate the possibilities of the new action language by two practical applications: to the dynamic domain of the Reactive Control System of the space shuttle, and to the task planning of mobile robots.Show more Item SAT-based answer set programming(2010-05) Lierler, Yuliya; Lifschitz, Vladimir; Boyer, Robert; Gal, Anna; Stone, Peter; Truszczynski, MiroslawShow more Answer set programming (ASP) is a declarative programming paradigm oriented towards difficult combinatorial search problems. Syntactically, ASP programs look like Prolog programs, but solutions are represented in ASP by sets of atoms, and not by substitutions, as in Prolog. Answer set systems, such as Smodels, Smodelscc, and DLV, compute answer sets of a given program in the sense of the answer set (stable model) semantics. This is different from the functionality of Prolog systems, which determine when a given query is true relative to a given logic program. ASP has been applied to many areas of science and technology, from the design of a decision support system for the Space Shuttle to graph-theoretic problems arising in zoology and linguistics. The "native" answer set systems mentioned above are based on specialized search procedures. Usually these procedures are described fairly informally with the use of pseudocode. We propose an alternative approach to describing algorithms of answer set solvers. In this approach we specify what "states of computation" are, and which transitions between states are allowed. In this way, we define a directed graph such that every execution of a procedure corresponds to a path in this graph. This allows us to model algorithms of answer set solvers by a mathematically simple and elegant object, graph, rather than a collection of pseudocode statements. We use this abstract framework to describe and prove the correctness of the answer set solver Smodels, and also of Smodelscc, which enhances the former using learning and backjumping techniques. Answer sets of a tight program can be found by running a SAT solver on the program's completion, because for such a program answer sets are in a one-to-one correspondence with models of completion. SAT is one of the most widely studied problems in computational logic, and many efficient SAT procedures were developed over the last decade. Using SAT solvers for computing answer sets allows us to take advantage of the advances in the SAT area. For a nontight program it is still the case that each answer set corresponds to a model of program's completion but not vice versa. We show how to modify the search method typically used in SAT solvers to allow testing models of completion and employ learning to utilize testing information to guide the search. We develop a new SAT-based answer set solver, called Cmodels, based on this idea. We develop an abstract graph based framework for describing SAT-based answer set solvers and use it to represent the Cmodels algorithm and to demonstrate its correctness. Such representations allow us to better understand similarities and differences between native and SAT-based answer set solvers. We formally compare the Smodels algorithm with a variant of the Cmodels algorithm without learning. Abstract frameworks for describing native and SAT-based answer set solvers facilitate the development of new systems. We propose and implement the answer set solver called SUP that can be seen as a combination of computational ideas behind Cmodels and Smodels. Like Cmodels, solver SUP operates by computing a sequence of models of completion of the given program, but it does not form the completion. Instead, SUP runs the Atleast algorithm, one of the main building blocks of the Smodels procedure. Both systems Cmodels and SUP, developed in this dissertation, proved to be competitive answer set programming systems.Show more