Cookies
O website necessita de alguns cookies e outros recursos semelhantes para funcionar. Caso o permita, o INESC TEC irá utilizar cookies para recolher dados sobre as suas visitas, contribuindo, assim, para estatísticas agregadas que permitem melhorar o nosso serviço. Ver mais
Aceitar Rejeitar
  • Menu
Publicações

Publicações por Vítor Santos Costa

2004

Pruning in the extended Andorra model

Autores
Lopes, R; Costa, VS; Silva, F;

Publicação
PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES

Abstract
One of the major problems that actual logic programming systems have to address is whether and how to prune undesirable parts of the search space. A region of the search space would definitely be undesirable if it can only repeat previously found solutions, or if it is well-known that the whole computation will fail. Or it may be the case that we are interested in a subset of solutions. In this work we discuss how the BEAM addresses pruning issues. The BEAM is an implementation of David Warren's Extended Andorra Model. Because the BEAM relies on a very flexible execution mechanism, all cases of pruning discussed above should be considered. We show that all these different forms of pruning can be supported, and study their impact in applications.

2004

Speculative computations in or-parallel tabled logic programs

Autores
Rocha, R; Silva, F; Costa, VS;

Publicação
LOGIC PROGRAMMING, PROCEEDINGS

Abstract
Pruning operators, such as cut, are important to develop efficient logic programs as they allow programmers to reduce the search space and thus discard unnecessary computations. For parallel systems, the presence of pruning operators introduces the problem of speculative computations. A computation is named speculative if it can be pruned during parallel evaluation, therefore resulting in wasted effort when compared to sequential execution. In this work we discuss the problems behind the management of speculative computations in or-parallel tabled logic programs. In parallel tabling, not only the answers found for the query goal may not be valid, but also answers found for tabled predicates may be invalidated. The problem here is even more serious because to achieve an efficient implementation it is required to have the set of valid tabled answers released as soon as possible. To deal with this, we propose a strategy to deliver tabled answers as soon as it is found that they are safe from being pruned, and present its implementation in the OPTYap parallel tabling system.

2004

On avoiding redundancy in inductive logic programming

Autores
Fonseca, N; Costa, VS; Silva, F; Camacho, R;

Publicação
INDUCTIVE LOGIC PROGRAMMING, PROCEEDINGS

Abstract
ILP systems induce first-order clausal theories performing a search through very large hypotheses spaces containing redundant hypotheses. The generation of redundant hypotheses may prevent the systems from finding good models and increases the time to induce them. In this paper we propose a classification of hypotheses redundancy and show how expert knowledge can be provided to an ILP system to avoid it. Experimental results show that the number of hypotheses generated and execution time are reduced when expert knowledge is used to avoid redundancy.

2004

Concurrent table accesses in parallel tabled logic programs

Autores
Rocha, R; Silva, F; Costa, VS;

Publicação
EURO-PAR 2004 PARALLEL PROCESSING, PROCEEDINGS

Abstract
Tabling is an implementation technique that improves the declarativeness and expressiveness of Prolog by reusing answers to subgoals. The declarative nature of tabled logic programming suggests that it might be amenable to parallel execution. On the other hand, the complexity of the tabling mechanism, and the existence of a shared resource, the table, may suggest that parallelism might be limited and never scale for real applications. In this work, we propose three alternative locking schemes to deal with concurrent table accesses, and we study their impact on the OPTYap parallel tabling system using a set of tabled programs.

2005

On applying or-parallelism and tabling to logic programs

Autores
Rocha, R; Silva, F; Costa, VS;

Publicação
THEORY AND PRACTICE OF LOGIC PROGRAMMING

Abstract
Logic programming languages, such as Prolog, provide a high-level, declarative approach to programming. Logic Programming offers great potential for implicit parallelism, thus allowing parallel systems to often reduce a program's execution time without programmer intervention. We believe that for complex applications that take several hours, if not days, to return an answer, even limited speedups from parallel execution can directly translate to very significant productivity gains. It has been argued that Prolog's evaluation strategy - SLD resolution often limits the potential of the logic programming paradigm. The past years have therefore seen widening efforts at increasing Prolog's declarativeness and expressiveness. Tabling has proved to be a viable technique to efficiently overcome SLD's susceptibility to infinite loops and redundant subcomputations. Our research demonstrates that implicit or-parallelism is a natural fit for logic programs with tabling. To substantiate this belief, we have designed and implemented an or-parallel tabling engine - OPTYap - and we used a shared-memory parallel machine to evaluate its performance. To the best of our knowledge, OPTYap is the first implementation of a parallel tabling engine for logic programming systems. OPTYap builds on Yap's efficient sequential Prolog engine. Its execution model is based on the SLG-WAM for tabling, and on the environment copying for or-parallelism. Preliminary results indicate that the mechanisms proposed to parallelize search in the context of SLD resolution can indeed be effectively and naturally generalized to parallelize tabled computations, and that the resulting systems can achieve good performance on shared-memory parallel machines. More importantly, it emphasizes our belief that through applying or-parallelism and tabling to logic programs the range of applications for Logic Programming can be increased.

2005

IMPACT: Innovative models for prolog with advanced control and tabling

Autores
Rocha, R; Lopes, R; Silva, F; Costa, VS;

Publicação
LOGIC PROGRAMMING, PROCEEDINGS

Abstract

  • 31
  • 34