Recently proposed models which learn to write computer programs from data use either input/output examples or rich execution traces. Instead, we argue that a novel alternative is to use a glass-box scoring function, given as a program itself that can be directly inspected. Glass-box optimization covers a wide range of problems, from computing the greatest common divisor of two integers, to learning-to-learn problems. In this paper, we present an intelligent search system which learns, given the partial program and the glass-box problem, the probabilities over the space of programs. We empirically demonstrate that our informed search procedure leads to significant improvements compared to brute-force program search, both in terms of accuracy and time. For our experiments we use rich context free grammars inspired by number theory, text processing, and algebra. Our results show that (i) running our framework iteratively can considerably increase the number of problems solved, (ii) our framework can improve itself even in domain agnostic scenarios, and (iii) it can solve problems that would be otherwise too slow to solve with brute-force search.

We study abduction in First Order Horn logic theories where all atoms can be abduced and we are looking for preferred solutions with respect to three objective functions: cardinality minimality, coherence, and weighted abduction. We represent this reasoning problem in Answer Set Programming (ASP), in order to obtain a flexible framework for experimenting with global constraints and objective functions, and to test the boundaries of what is possible with ASP. Realizing this problem in ASP is challenging as it requires value invention and equivalence between certain constants, because the Unique Names Assumption does not hold in general. To permit reasoning in cyclic theories, we formally describe fine-grained variations of limiting Skolemization. We identify term equivalence as a main instantiation bottleneck, and improve the efficiency of our approach with on-demand constraints that were used to eliminate the same bottleneck in state-of-the-art solvers. We evaluate our approach experimentally on the ACCEL benchmark for plan recognition in Natural Language Understanding. Our encodings are publicly available, modular, and our approach is more efficient than state-of-the-art solvers on the ACCEL benchmark.

Bisimulation provides structural conditions to characterize indistinguishability from an external observer between nodes on labeled graphs. It is a fundamental notion used in many areas, such as verification, graph-structured databases, and constraint satisfaction. However, several current applications use graphs where nodes also contain data (the so called "data graphs"), and where observers can test for equality or inequality of data values (e.g., asking the attribute 'name' of a node to be different from that of all its neighbors). The present work constitutes a first investigation of "data aware" bisimulations on data graphs. We study the problem of computing such bisimulations, based on the observational indistinguishability for XPath ---a language that extends modal logics like PDL with tests for data equality--- with and without transitive closure operators. We show that in general the problem is PSpace-complete, but identify several restrictions that yield better complexity bounds (coNP, PTime) by controlling suitable parameters of the problem, namely the amount of non-locality allowed, and the class of models considered (graphs, DAGs, trees). In particular, this analysis yields a hierarchy of tractable fragments.

Artificial Neural Networks are powerful function approximators capable of modelling solutions to a wide variety of problems, both supervised and unsupervised. As their size and expressivity increases, so too does the variance of the model, yielding a nearly ubiquitous overfitting problem. Although mitigated by a variety of model regularisation methods, the common cure is to seek large amounts of training data--which is not necessarily easily obtained--that sufficiently approximates the data distribution of the domain we wish to test on. In contrast, logic programming methods such as Inductive Logic Programming offer an extremely data-efficient process by which models can be trained to reason on symbolic domains. However, these methods are unable to deal with the variety of domains neural networks can be applied to: they are not robust to noise in or mislabelling of inputs, and perhaps more importantly, cannot be applied to non-symbolic domains where the data is ambiguous, such as operating on raw pixels. In this paper, we propose a Differentiable Inductive Logic framework, which can not only solve tasks which traditional ILP systems are suited for, but shows a robustness to noise and error in the training data which ILP cannot cope with. Furthermore, as it is trained by backpropagation against a likelihood objective, it can be hybridised by connecting it with neural networks over ambiguous data in order to be applied to domains which ILP cannot address, while providing data efficiency and generalisation beyond what neural networks on their own can achieve.

R B. Abhyankar Emphasizing theory and implementation issues more than specific applications and Prolog programming techniques, Computing with Logic Logic Programming with Prolog (The Benjamin Cummings Publishing Company, Menlo Park, Calif., 1988, 535 pp., $27 95) by David Maier and David S. Warren, respected researchers in logic programming, is a superb book Offering an in-depth treatment of advanced topics, the book also includes the necessary background material on logic and automatic theorem proving, making it self-contained. The only real prerequisite is a first course in data structures, although it would be helpful if the reader has also had a first course in program translation. The book has a wealth of exercises and would make an excellent textbook for advanced undergraduate or graduate students in computer science; it is also appropriate for programmers interested in the implementation of Prolog The book presents the concepts of logic programming using theory presentation, implementation, and application of Proplog, Datalog, and Prolog, three logic programming languages of increasing complexity that are based on horn clause subsets of propositional, predicate, and functional logic, respectively This incremental approach, unique to this book, is effective in conveying a thorough understanding of the subject The book consists of 12 chapters grouped into three parts (Part 1 chapters 1 to 3, Part 2. chapters 4 to 6, and Part 3 chapters 7 to 12), an appendix, and an index The three parts, each dealing with one of these logic programming languages, are organized the same First, the authors informally present the language using examples; an interpreter is also presented. Then the formal syntax and semantics for the language and logic are presented, along with soundness and completeness results for the logic and the effects of various search strategies Next, they give optimization techniques for the interpreter Each chapter ends with exercises, brief comments regarding the material in the chapter, and a bibliography Chapter I presents top-down and bottom-up interpreters for Proplog Chapter 2 offers a good discussion of the related notions: negation as failure, closed-world assumption, minimal models, and stratified programs Chapter 3 considers clause indexing and lazy concatenation as optimization techniques for the Proplog interpreter in chapter 1 Chapter 4 explains the connection between Datalog and relational algebra. Chapter 5 contains a proof of Herbrand's theorem for predicate logic.

The workshop was organized by Jack Minker and John McCarthy. The Program Committee members were Krzysztof Apt, John Horty, Sarit Kraus, Vladimir Lifschitz, John McCarthy, Jack Minker, Don Perlis, and Ray Reiter. The purpose of the workshop was to bring together researchers who use logic as a fundamental tool in AI to permit them to review accomplishments, assess future directions, and share their research in LBAI. This article is a summary of the workshop. The areas selected for discussion at the workshop were abductive and inductive reasoning, applications of theorem proving, commonsense reasoning, computational logic, constraints, logic and high-level robotics, logic and language, logic and planning, logic for agents and actions, logic of causation and action, logic, probability and decision theory, nonmonotonic reasoning, theories of belief, and knowledge representation.

To read the book Automated Reasoning: Thirty-Three Basic Research Problems (Prentice Hall, Englewood Cliffs, N.J., 1987, 300 pp., $11.00) by Larry Wos "it is not necessary to be an expert in mathematics or logic or computer science" (from the preface). However, even if you are such an expert, you will read it with interest, and likely, with enjoyment. The book is outstanding for its presentation of the theme. Following the introductory chapter, Wos discusses some obstacles to the automation of reasoning in Chapter 2. In Chapter 3, he lists the research problems (with short descriptions) in nine groups: six problems on strategy, five on inference rules, six on demodulation, one on subsumption, three on knowledge representation, two on global approach, one on logic programming, two on self-analysis, and six on other areas. After a short review of automated reasoning (AR) in Chapter 4, these problems are discussed in detail in Chapter 5. Chapter 6 gives some sets of test problems, all concerning a mathematical discipline.

To read the book Automated Reasoning: Thirty-Three Basic Research Problems (Prentice Hall, Englewood Cliffs, N.J., 1987, 300 pp., $11.00) by Larry Wos "it is not necessary to be an expert in mathematics or logic or computer science" (from the preface). However, even if you are such an expert, you will read it with interest, and likely, with enjoyment. The book is outstanding for its presentation of the theme. Following the introductory chapter, Wos discusses some obstacles to the automation of reasoning in Chapter 2. In Chapter 3, he lists the research problems (with short descriptions) in nine groups: six problems on strategy, five on inference rules, six on demodulation, one on subsumption, three on knowledge representation, two on global approach, one on logic programming, two on self-analysis, and six on other areas. After a short review of automated reasoning (AR) in Chapter 4, these problems are discussed in detail in Chapter 5. Chapter 6 gives some sets of test problems, all concerning a mathematical discipline.

To read the book Automated Reasoning: Thirty-Three Basic Research Problems (Prentice Hall, Englewood Cliffs, N.J., 1987, 300 pp., $11.00) by Larry Wos "it is not necessary to be an expert in mathematics or logic or computer science" (from the preface). However, even if you are such an expert, you will read it with interest, and likely, with enjoyment. The book is outstanding for its presentation of the theme. Following the introductory chapter, Wos discusses some obstacles to the automation of reasoning in Chapter 2. In Chapter 3, he lists the research problems (with short descriptions) in nine groups: six problems on strategy, five on inference rules, six on demodulation, one on subsumption, three on knowledge representation, two on global approach, one on logic programming, two on self-analysis, and six on other areas. After a short review of automated reasoning (AR) in Chapter 4, these problems are discussed in detail in Chapter 5. Chapter 6 gives some sets of test problems, all concerning a mathematical discipline.

What Ray Reiter has done has taken a set of ideas worked out by him and his collaborators over the last 11 years and recrystallized them into a sustained and consistent presentation. This is not a collection of those papers but a complete rewrite that avoids the usual repetition and notational inconsistency that one might expect. It makes one wish everyone as prolific as Reiter would copy his example--but because that's unlikely, we must be grateful for what he has given us. In case you haven't heard, Reiter and his crew, starting with the publication of Reiter (1991), breathed new life into the situation calculus (Mc-Carthy and Hayes 1969) that had gotten the reputation of being of limited expressiveness. The basic concept of the calculus is, of course, the situation, which we can think of as a state of affairs, that is, a complete specification of the truth values of all propositions (in a suitable logical language), although that's closer to McCarthy's and Hayes's traditional formulation than the analysis Reiter settles on (which I describe later).