Abstract
Inference in many probabilistic logic systems is based on representing the proofs of a query as a DNF Boolean formula. Assessing the probability of such a formula is known as a #P-hard task. In practice, a large DNF is given to a BDD software package to construct the corresponding BDD. The DNF has to be transformed into the input format of the package. This is the preprocessing step. In this paper we investigate and compare different preprocessing methods, including our new trie based approach. Our experiments within the ProbLog system show that the behaviour of the methods changes according to the amount of sharing in the original DNF. The decomposition method is preferred when there is not much sharing in the DNF, whereas DNFs with sharing benefit from our trie based method. While our methods are motivated and applied in the ProbLog context, our results are interesting for other applications that manipulate DNF Boolean formulae.

Abstract
Tabled evaluation is a recognized and powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. Tabling based systems use call similarity to determine if a tabled subgoal will produce their own answers or if it will consume from another subgoal. While call variance has been a very popular approach, call subsumption can yield superior time performance and space improvements as it allows greater reuse of answers. However, the call order of the subgoals can greatly affect the success and applicability of the call subsumption technique. In this work, we present an extension, named Retroactive Call Subsumption, that supports call subsumption by allowing full sharing of answers between subsumed/subsuming subgoals, independently on the order in which they are called. Our experiments using the YapTab tabling engine show considerable gains in evaluation time for some applications, at the expense of a very small overhead for the programs that cannot benefit from it.

Abstract
Tabling is a technique of resolution that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. In suspension-based tabling, a tabled evaluation can be seen as a sequence of sub-computations that suspend and later resume. Linear tabling mechanisms maintain a single execution tree where tabled subgoals always extend the current computation without requiring suspension and resumption of sub-computations. In this work, we present a new and efficient implementation of linear tabling, but for that we have extended an already existent suspension-based implementation, the YapTab engine. Our design is based on dynamic reordering of alternatives but it innovates by considering a strategy that schedules the re-evaluation of tabled calls in a similar manner to the suspension-based strategies of YapTab. Our implementation also shares the underlying execution environment and most of the data structures used to implement tabling in YapTab. We thus argue that all these common features allows us to make a first and fair comparison between suspension-based and linear tabling and, therefore, better understand the advantages and weaknesses of each.

Abstract
A critical component in the implementation of an efficient tabling system is the design of the data structures and algorithms to access and manipulate tabled data. Arguably, the most successful data structure for tabling is tries, which is regarded as a very compact and efficient; data structure for term representation. Despite these good properties, we found that, for list terms, we can design even more compact and efficient representations. We thus propose a, new representation of list terms for tries that avoids the recursive nature of the WAM representation of list terms in which tries are based. Our experimental results using the YapTab tabling system show a significant reduction in the memory usage for the trie data structures and considerable gains in the running time for storing and loading list terms.

Abstract
The execution model on which most tabling engines are based allocates a choice point whenever a new tabled subgoal is called. This happens even when the call is deterministic. however, sortie of the information from the choice point; is never used when evaluating deterministic tabled calls with batched scheduling. Moreover, when a deterministic answer is found for a. deterministic tabled call, the call can be completed early and the corresponding choice point can be removed. Thus, if applying batched scheduling to a long deterministic computation the system may end up consuming memory and evaluating calls unnecessarily. In this paper, we propose a solution that, tries to reduce this memory and execution overhead to a minimum. Our experimental results show that;, for deterministic tabled calls and tabled answers with batched scheduling, it; is possible not. only to reduce the memory usage overhead, but also the running time of tire execution.

Abstract
A critical component in the implementation of an efficient tabling system is the design of the data structures and algorithms to access and manipulate tabled data. Arguably, the most successful data structure for tabling is tries. However, when used in applications that pose many queries and/or have a large number of answers, tabling call build arbitrarily many and/or very large tables, quickly filling Lip memory. In this paper, we propose a new design for the table space organization where all terms in tabled subgoal calls and tabled answers are represented only once in a common global trie instead of being spread over several different trie data structures. Our initial experiments using the YapTab tabling system show significant reductions oil memory usage without compromising running time.