Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Protocolo Mac para acesso multi-modo em redes de sensores sem fios móveis

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Estratégia multi-temporal para produção automática de cartografia de ocupação do solo com imagens AWiFS

Dissertação apresentada como requisito parcial para obtenção do grau de Mestre em Ciência e Sistemas de Informação Geográfica

Multi-region routing

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Wetland Habitat Studies using various Classification Techniques on Multi-Spectral Landsat Imagery: Case study: Tram chim National Park, Dong Thap Vietnam

Dissertation submitted in partial fulfilment of the requirements for the Degree of Master of Science in Geospatial Technologies

José e Jacinta nem sempre vivem nos mesmos lugares: reflexões em torno de uma experiência de etnografia multi-situada

Ethnologia - Antropologia dos processos identitários, Lisboa

Caracterização da ocupação do solo com recurso à aplicação de modelos de misturas espectrais em séries multi-temporais de imagens MODIS

Dissertação apresentada como requisito parcial para obtenção do grau de Mestre em Ciência e Sistemas de Informação Geográfica

Cartografia multi-escala de alterações do coberto florestal com imagens de satélite

Dissertação apresentada como requisito parcial para obtenção do grau de Mestre em Ciência e Sistemas de Informação Geográfica

Optimization of multi-stage amplifiers in deep-submicron CMOS using a distributed/parallel genetic algorithm

IEEE International Symposium on Circuits and Systems, pp. 724 – 727, Seattle, EUA

Multi-bit sigma-delta modulators with enhanced dynamic-range using non-linear DAC for hearing aids

15th IEEE International Conference on Electronics, Circuits and Systems, Malta

Context-aware multi-factor authentication

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

Framework para aplicações colaborativas multi-plataforma

Dissertação de Mestrado em Engenharia Informática

Investigar em educação: desafios da construção de conhecimento e da formação de investigadores num campo multi-referenciado

O livro que agora se apresenta decorre do trabalho desenvolvido num ciclo de seminários realizados no ano lectivio de 2008/09 e pretende explicitar e sistematizar alguns elementos em torno das principais questões organizadoras: o quê investigar em educação? Como se investiga em educação? Para quê investigar em educação? Porém, não são respostas definitivas ou acabadas que se pretendem alcançar, nem tão pouco podemos escamotear que se tratam de respostas situadas em função dos percursos formativos e profissionais dos investigadores, mestrandos e doutorandos envolvidos nos seminários. Procuramos, acima de tudo, explicitar o posicionamento que, no nosso caso, tem vindo a ser privilegiado em termos de trabalho científico no campo da investigação em educação

Biomarkers in Solea Senegalensis Kaup, 1858 exposed to contaminated estuarine sediments: a multi-level approach

Thesis submitted to the Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia for the degree of Doctor of Philosophy in Environmental Sciences