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.

Semantics of logic programs with explicit negation

After a historical introduction, the bulk of the thesis concerns the study of a declarative semantics for logic programs. The main original contributions are: ² WFSX (Well–Founded Semantics with eXplicit negation), a new semantics for logic programs with explicit negation (i.e. extended logic programs), which compares favourably in its properties with other extant semantics. ² A generic characterization schema that facilitates comparisons among a diversity of semantics of extended logic programs, including WFSX. ² An autoepistemic and a default logic corresponding to WFSX, which solve existing problems of the classical approaches to autoepistemic and default logics, and clarify the meaning of explicit negation in logic programs. ² A framework for defining a spectrum of semantics of extended logic programs based on the abduction of negative hypotheses. This framework allows for the characterization of different levels of scepticism/credulity, consensuality, and argumentation. One of the semantics of abduction coincides with WFSX. ² O–semantics, a semantics that uniquely adds more CWA hypotheses to WFSX. The techniques used for doing so are applicable as well to the well–founded semantics of normal logic programs. ² By introducing explicit negation into logic programs contradiction may appear. I present two approaches for dealing with contradiction, and show their equivalence. One of the approaches consists in avoiding contradiction, and is based on restrictions in the adoption of abductive hypotheses. The other approach consists in removing contradiction, and is based in a transformation of contradictory programs into noncontradictory ones, guided by the reasons for contradiction.

Water treatments in semi-closed cooling circuits and their impact on the quality of effluents discharged by CERN

Dissertação apresentada à Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia do Ambiente, Gestão de Sistemas Ambientais

Water treatments in semi-closed cooling circuits and their impact on the quality of effluents discharged by CERN

Mestrado integrado em Engenharia do Ambiente, perfil: Gestão de Sistemas Ambientais

A Logic and tool for local reasoning about security protocols

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

Novel techniques for the design and practical realization of switched-capacitor circuits in deep-submicron CMOS technologies

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Electrotécnica e de Computadores pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Low-voltage low-power CMOS analogue circuits for Gaussian and uniform noise generation

IEEE International Symposium on Circuits and Systems, MAY 25-28, 2003, Bangkok, Thailand. (ISI Web of Science)

Digitally programmable delay-locked-loop with adaptive charge pump current for UWB radar system

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

Petri nets based components within globally asynchronous locally synchronous systems

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

Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations

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

Verification of analog circuits in power-down mode

Dissertação para obtenção do Grau de Mestre em Engenharia Eletrotécnica e Computadores

Revision based total semantics for extended normal logic programs

Dissertação para obtenção do Grau de Doutor em Matemática - Lógica e Fundamentos da Matemática

Computational modeling of prefrontal cortex circuits

Dissertation presented to obtain the Ph.D degree in Biology

CMOS indoor light energy harvesting system for wireless sensing applications

Dissertação para obtenção do Grau de Doutor em Engenharia Electrotécnica e de Computadores

Petri net based development of globally-asynchronous locally-synchronous distributed embedded systems

Dissertação para obtenção do Grau de Doutor em Engenharia Electrotécnica e de Computadores