1.

A decision procedure for satisfiability in separation logic with inductive predicates
- Brotherston, J; Fuhs, C; Pérez, JAN; Gorogiannis, N
We show that the satisfiability problem for the "symbolic heap" fragment of separation logic with general inductively defined predicates- which includes most fragments employed in program verification - is decidable. Our decision procedure is based on the computation of a certain fixed point from the definition of an inductive predicate, called its "base", that exactly characterises its satisfiability. A complexity analysis of our decision procedure shows that it runs, in the worst case, in exponential time. In fact, we show that the satisfiability problem for our inductive predicates is EXPTIME- complete, and becomes NP-complete when the maximum arity over all...

2.

Logic, deductive and inductive /
- Bain, Alexander,
1818-1903.
Mode of access: Internet.

3.

Foundations for decision problems in separation logic with general inductive predicates
- Antonopoulos, T; Ouaknine, J; Gorogiannis, N; Haase, C; Kanovich, M
We establish foundational results on the computational complexity of deciding entailment in Separation Logic with general inductive predicates whose underlying base language allows for pure formulas, pointers and existentially quantified variables. We show that entailment is in general undecidable, and ExpTime-hard in a fragment recently shown to be decidable by Iosif et al. Moreover, entailment in the base language is Π -complete, the upper bound even holds in the presence of list predicates. We additionally show that entailment in essentially any fragment of Separation Logic allowing for general inductive predicates is intractable even when strong syntactic restrictions are imposed. ©...

4.

A Note on Binary Inductive Logic
- C. J. Nix; J. B. Paris
5.

Parallel ILP for Distributed-Memory Architectures
- Nuno A. Fonseca; Ashwin Srinivasan; Fernando Silva; Rui Camacho
The growth of machine-generated relational databases, both in thesciences and in industry, is rapidly outpacing our ability to extract useful information from them by manual means. This has brought into focus machine learning techniques like Inductive Logic Programming (ILP) that are able to extract humancomprehensible models for complex relational data. The price to pay is that ILP techniques are not ecient: they can be seen as performing a form of discrete optimisation, which is known to be computationally hard; and the complexity is usually some non-linear function of the number of examples. While little can be done to alter the...

6.

Quantitative Pharmacophore Models with Inductive Logic Programming
- Ashwin Srinivasan; David Page; Rui Camacho; Ross King
Three-dimensional models, or pharmacophores, describing Euclidean constraints on the location on small molecules of functional groups (like hydrophobic groups, hydrogen acceptors and donors, etc.), are often used in drug design to describe the medicinal activity of potential drugs (or ligands). This medicinal activity is produced by interaction of the functional groups on the ligand with a binding site on a target protein. In identifying structure-activity relations of this kind there are three principal issues: (1) It is often dicult to \alignquot; the ligands in order to identify common structural properties that may be responsible for activity; (2) Ligands in solution...

7.

Improving the efficiency of ILP systems
- Rui Camacho
Inductive Logic Programming (ILP) is a promising technol-ogy for knowledge extraction applications. ILP has produced intelligiblesolutions for a wide variety of domains where it has been applied. TheILP lack of eciency is, however, a major impediment for its scalabilityto applications requiring large amounts of data. In this paper we pro-pose a set of techniques that improve ILP systems eciency and makethen more likely to scale up to applications of knowledge extraction fromlarge datasets. We propose and evaluate the lazy evaluation of examples,to improve the eciency of ILP systems. Lazy evaluation is essentiallya way to avoid or postpone the evaluation of...

8.

A parallel ILP algorithm that incorporates incremental batch learning
- Nuno A Fonseca; Rui Camacho; Fernado Silva
In this paper we tackle the problems of eciency and scala-bility faced by Inductive Logic Programming (ILP) systems. We proposethe use of parallelism to improve eciency and the use of an incrementalbatch learning to address the scalability problem. We describe a novelparallel algorithm that incorporates into ILP the method of incremen-tal batch learning. The theoretical complexity of the algorithm indicatesthat a linear speedup can be achieved.

9.

A pipelined data-parallel algorithm for ILP
- fonseca, nuno a.; silva, fernando; costa, vitor santos; camacho, rui
The amount of data collected and stored in databases is growing considerably for almost all areas of human activity. Processing this amount of data is very expensive, both humanly and computationally. This justifies the increased interest both on the automatic discovery of useful knowledge from databases, and on using parallel processing for this task. Multi Relational Data Mining (MRDM) techniques, such as Inductive Logic Programming (ILP), can learn rules from relational databases consisting of multiple tables. However current ILP systems are designed to run in main memory and can have long running times. We propose a pipelined data-parallel algorithm for...

10.

A pipelined data-parallel algorithm for ILP
- fonseca, nuno a.; silva, fernando; costa, vitor santos; camacho, rui
The amount of data collected and stored in databases is growing considerably for almost all areas of human activity. Processing this amount of data is very expensive, both humanly and computationally. This justifies the increased interest both on the automatic discovery of useful knowledge from databases, and on using parallel processing for this task. Multi Relational Data Mining (MRDM) techniques, such as Inductive Logic Programming (ILP), can learn rules from relational databases consisting of multiple tables. However current ILP systems are designed to run in main memory and can have long running times. We propose a pipelined data-parallel algorithm for...

11.

Strategies to parallelize ILP systems
- Nuno A Fonseca; Fernado Silva; Rui Camacho
It is well known by Inductive Logic Programming (ILP) practionersthat ILP systems usually take a long time to nd valuable models(theories). The problem is specially critical for large datasets, preventingILP systems to scale up to larger applications. One approach to reducethe execution time has been the parallelization of ILP systems. In thispaper we overview the state-of-the-art on parallel ILP implementationsand present work on the evaluation of some major parallelization strategiesfor ILP. Conclusions about the applicability of each strategy arepresented.

12.

Efficient Data Structures for Inductive Logic Programming
- Nuno A Fonseca; Ricardo Rocha; Rui Camacho; Fernado Silva
This work aims at improving the scalability of memory usagein Inductive Logic Programming systems. In this context, we propose twoecient data structures: the Trie, used to represent lists and clauses;and the RL-Tree, a novel data structure used to represent the clausescoverage. We evaluate their performance in the April system using wellknown datasets. Initial results show a substantial reduction in memoryusage without incurring extra execution time overheads. Our proposal isapplicable in any ILP system.

13.

From sequential to Parallel Inductive LogicProgramming
- Rui Camacho
Inductive Logic Programming (ILP) has achieved considerablesuccess in a wide range of domains. It is recognized however thateciency is a major obstacle to the use of ILP systems in applicationsrequiring large amounts of data. In this paper we address the problem ofeciency in ILP in three steps: i) we survey speedup techniques proposedfor sequential execution of ILP systems; ii) we survey dierent ways ofparallelizing an ILP system and; ii) adapt and combine the sequentialexecution speedup techniques in the parallel implementations of an ILPsystem. We also propose a novel technique to partition the search spaceinto independent sub-spaces that may be adequately...

14.

A commodity platform for Distributed Data Mining -- the HARVARD System
- Ruy Ramos; Rui Camacho; Pedro Ferreira Do Souto
Systems performing Data Mining analysis are usually dedicated and expensive. They often require special purpose machines to run the data analysis tool. In this paper we propose an architecture for distributed Data Mining running on general purpose desktop computers. The proposed architecture was deployed in the HARVesting Architecture of idle machines foR Data mining (HARVARD) system.The Harvard system has the following features. Does not require specialpurpose or expensive machines as it runs in general purpose PCs. It isbased on distributed computing using a set of PCs connected in a network. In a Condor fashion it takes advantage of a distributed...

15.

A system of logic, ratiocinative and inductive : being a connected view of the principles of evidence and the methods of scientific investigation /
- Mill, John Stuart,
1806-1873.
Mode of access: Internet.

16.

Logic, deductive and inductive,
- Fowler, Thomas,
1832-1904.
Each part has special t.-p.

17.

Logic, deductive and inductive.
- Read, Carveth,
1848-
Mode of access: Internet.

18.

Elementary lessons in logic; deductive and inductive. With copious questions and examples and a vocabulary of logical terms.
- Jevons, William Stanley,
1835-1882.
Mode of access: Internet.

19.

A system of logic, ratiocinative and inductive : being a connected view of the principles of evidence and the methods of scientific investigation /
- Mill, John Stuart,
1806-1873.
Includes bibliographical references.

20.

Sistema logiki /
- Mill, John Stuart,
1806-1873.
Translation of: System of logic, ratiocinative and inductive.