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.

Constraint reasoning for differential models

The basic motivation of this work was the integration of biophysical models within the interval constraints framework for decision support. Comparing the major features of biophysical models with the expressive power of the existing interval constraints framework, it was clear that the most important inadequacy was related with the representation of differential equations. System dynamics is often modelled through differential equations but there was no way of expressing a differential equation as a constraint and integrate it within the constraints framework. Consequently, the goal of this work is focussed on the integration of ordinary differential equations within the interval constraints framework, which for this purpose is extended with the new formalism of Constraint Satisfaction Differential Problems. Such framework allows the specification of ordinary differential equations, together with related information, by means of constraints, and provides efficient propagation techniques for pruning the domains of their variables. This enabled the integration of all such information in a single constraint whose variables may subsequently be used in other constraints of the model. The specific method used for pruning its variable domains can then be combined with the pruning methods associated with the other constraints in an overall propagation algorithm for reducing the bounds of all model variables. The application of the constraint propagation algorithm for pruning the variable domains, that is, the enforcement of local-consistency, turned out to be insufficient to support decision in practical problems that include differential equations. The domain pruning achieved is not, in general, sufficient to allow safe decisions and the main reason derives from the non-linearity of the differential equations. Consequently, a complementary goal of this work proposes a new strong consistency criterion, Global Hull-consistency, particularly suited to decision support with differential models, by presenting an adequate trade-of between domain pruning and computational effort. Several alternative algorithms are proposed for enforcing Global Hull-consistency and, due to their complexity, an effort was made to provide implementations able to supply any-time pruning results. Since the consistency criterion is dependent on the existence of canonical solutions, it is proposed a local search approach that can be integrated with constraint propagation in continuous domains and, in particular, with the enforcing algorithms for anticipating the finding of canonical solutions. The last goal of this work is the validation of the approach as an important contribution for the integration of biophysical models within decision support. Consequently, a prototype application that integrated all the proposed extensions to the interval constraints framework is developed and used for solving problems in different biophysical domains.

Modern techniques for constraint solving the CASPER experience

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Informática, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Constraint-based modeling of minimum set covering: application to species differentation

Work presented in the context of the European Master in Computational Logics, as partial requisit for the graduation as Master in Computational Logics

Constraint-based verification of imperative programs

work presented in the context of the European Master’s program in Computational Logic, as the partial requirement for obtaining Master of Science degree in Computational Logic

Probabilistic constraint reasoning

Dissertação apresentada para obtenção do Grau de Doutor em Engenharia Informática, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Constraint-based modelling of mixed microbial populations: Application to polyhydroxyalkanoates production

Dissertação para obtenção do Grau de Doutor em Engenharia Química e Bioquímica

Constraint reasoning with local search for continuous optimization

Optimization is a very important field for getting the best possible value for the optimization function. Continuous optimization is optimization over real intervals. There are many global and local search techniques. Global search techniques try to get the global optima of the optimization problem. However, local search techniques are used more since they try to find a local minimal solution within an area of the search space. In Continuous Constraint Satisfaction Problems (CCSP)s, constraints are viewed as relations between variables, and the computations are supported by interval analysis. The continuous constraint programming framework provides branch-and-prune algorithms for covering sets of solutions for the constraints with sets of interval boxes which are the Cartesian product of intervals. These algorithms begin with an initial crude cover of the feasible space (the Cartesian product of the initial variable domains) which is recursively refined by interleaving pruning and branching steps until a stopping criterion is satisfied. In this work, we try to find a convenient way to use the advantages in CCSP branchand- prune with local search of global optimization applied locally over each pruned branch of the CCSP. We apply local search techniques of continuous optimization over the pruned boxes outputted by the CCSP techniques. We mainly use steepest descent technique with different characteristics such as penalty calculation and step length. We implement two main different local search algorithms. We use “Procure”, which is a constraint reasoning and global optimization framework, to implement our techniques, then we produce and introduce our results over a set of benchmarks.

Probabilistic constraint reasoning with Monte Carlo integration to robot localization

This work studies the combination of safe and probabilistic reasoning through the hybridization of Monte Carlo integration techniques with continuous constraint programming. In continuous constraint programming there are variables ranging over continuous domains (represented as intervals) together with constraints over them (relations between variables) and the goal is to find values for those variables that satisfy all the constraints (consistent scenarios). Constraint programming “branch-and-prune” algorithms produce safe enclosures of all consistent scenarios. Special proposed algorithms for probabilistic constraint reasoning compute the probability of sets of consistent scenarios which imply the calculation of an integral over these sets (quadrature). In this work we propose to extend the “branch-and-prune” algorithms with Monte Carlo integration techniques to compute such probabilities. This approach can be useful in robotics for localization problems. Traditional approaches are based on probabilistic techniques that search the most likely scenario, which may not satisfy the model constraints. We show how to apply our approach in order to cope with this problem and provide functionality in real time.

Pseudo-fractional ARMA modelling using a double Levinson recursion

IET Control Theory & Applications, Vol. 1, Nº 1

Integrating protein structural information

Dissertação apresentada para obtenção de Grau de Doutor em Bioquímica,Bioquímica Estrutural, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

Refinamento de diagramas de classes: análise e verificação

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

POST-PROCESSING TECHNIQUES SUITABILITY FOR MESOLEVEL FREE BOUNDARY FLOWS

Reliable flow simulation software is inevitable to determine an optimal injection strategy in Liquid Composite Molding processes. Several methodologies can be implemented into standard software in order to reduce CPU time. Post-processing techniques might be one of them. Post-processing a finite element solution is a well-known procedure, which consists in a recalculation of the originally obtained quantities such that the rate of convergence increases without the need for expensive remeshing techniques. Post-processing is especially effective in problems where better accuracy is required for derivatives of nodal variables in regions where Dirichlet essential boundary condition is imposed strongly. In previous works influence of smoothness of non-homogeneous Dirichlet condition, imposed on smooth front was examined. However, usually quite a non-smooth boundary is obtained at each time step of the infiltration process due to discretization. Then direct application of post-processing techniques does not improve final results as expected. The new contribution of this paper lies in improvement of the standard methodology. Improved results clearly show that the recalculated flow front is closer to the ”exact” one, is smoother that the previous one and it improves local disturbances of the “exact” solution.

Fisioterapia e reabilitação em Portugal : o financiamento como factor crítico do desempenho

RESUMO - Num contexto em que a prestação de cuidados de Fisioterapia e Reabilitação é identificada como apresentando uma desigualdade e desajustamento da oferta regional superior à dos restantes cuidados de saúde, assim como uma falta de adequação dos preços praticados, perante as condições de oferta e procura actualmente existentes, o presente trabalho tem por objectivo investigar, no domínio do Desempenho, a influência do Financiamento na definição da prestação destes cuidados, tendo como pressuposto genérico que as decisões estratégicas e a reestruturação produtiva das organizações de saúde são condicionadas pelo sistema de preços. Considera-se que o actual sistema de Financiamento/Pagamento provoca um constrangimento na qualidade da resposta destes cuidados a dois níveis: um primeiro nível, ao colocar o pagamento no âmbito dos Meios Complementares de Diagnóstico e Terapêutica (MCDTs) a contratar pelo Serviço Nacional de Saúde, com isso determinando a configuração organizativa do sistema; um segundo nível de constrangimento que incide sobre as estruturas das organizações prestadoras, pela modelação que induz, nomeadamente a nível da sua produção. Na impossibilidade de tratar as duas dimensões do problema, pela falta de indicadores de desempenho deste sector, analisou-se, relativamente ao segundo nível de constrangimento, a produção de fisioterapia de três organizações que, potencialmente, teriam o mesmo o mesmo perfil de oferta por se enquadrarem num mesmo perfil de procura. Os resultados reflectem o pressuposto genérico do trabalho e abrem espaço para colocar como futura hipótese de investigação a razão da(s) causa(s) que poderão estar subjacentes à discrepância encontrada na média de tratamentos por sessão (duas vezes e meia) na produção das duas organizações que foi possível comparar.------------------- ABSTRACT - In a context where the provision of Physical Therapy and Rehabilitation care is identified as having a regional mismatch of supply and inequality above all the others health cares, and a lack of adequacy of prices in the current conditions of supply and demand, the present work has, as main purpose, to investigate, in the field of Performance, the Payment’s influence in shaping the provision of such health care. The general assumption tracking this analysis is that the strategic decisions on productive structure of health care organizations are influenced by the price systems. It is considered that the current Finance / Payment system causes two levels of constraints on the quality of such health care: a first constraint, as it putts its payment under the Supplementary Means of Diagnosis and Therapy (MCDTs), witch ends up establishing the organizational setup of the system; a second level of constraint by modelling the internal structure of these organizations. The lack of indicators characterizing the performance of this sector, addressed the present study to the second dimension, in witch was analysed the physical therapy production in three organizations that, potentially, would have the same profile of supply responding to similar characteristics of demand. The results reflect the above mentioned general assumption that supported the work, and leave an open space for future research, about the reason (s) that lay behind the discrepancy found between the average of treatments per session (two and a half times) in

Adherence to health-related behaviors: effectiveness of implementation intentions and posthypnotic suggestion in college students

Resumo: Com base no conceito de implementação de intenções (Gollwitzer, 1993, 1999) e na teoria do contexto de resposta de Kirsch & Lynn (1997), o presente trabalho testou a eficácia de uma intervenção combinada de implementação de intenções com hipnose e sugestão pós-hipnótica na promoção da adesão a uma tarefa simples (avaliação do humor) e uma tarefa difícil (actividade física). Os participantes são estudantes universitários de uma universidade na Nova Jérsia, (N=124, Estudo 1, EUA) e em Lisboa (N=323, Estudo 2, Portugal). Em ambos os estudos os participantes foram seleccionados a partir de uma amostra mais vasta baseado num escrutínio da sua sugestibilidade hipnótica avaliada por meio da Escala de Grupo de Sugestibilidade Hipnótica de Waterloo-Stanford (WSGC): Forma C. O Estudo 1 usou um desenho factorial do tipo 2x2x3 (tipo de intenção formada x hipnose x nível de sugestionabilidade) e o Estudo 2 usou um desenho factorial do tipo 2 x 2x 2 x 4 (tipo de tarefa x tipo de intenção formada x hipnose x nível de sugestionabilidade). No Estudo 1 foi pedido aos participantes que corressem todos os dias e durante três semanas durante 5 minutos, que medissem a sua pulsação antes e depois da actividade física e que mandassem um e-mail ao experimentador, fornecendo assim uma medida comportamental e uma medida de auto-relato. Aos participantes no grupo de intenções de meta foi apenas pedido que corressem todos os dias. Aos participantes no grupo de implementação de intenções foi pedido que especificasses com exactidão quando e onde iriam correr e enviar o e-mail. Para além disso, cerca de metade dos participantes foram hipnotizados e receberam uma sugestão pós-hipnótica em que lhes foi sugerido que o pensamento de correr todos os dias lhes viria à mente sem esforço no momento apropriado. A outra metade dos participantes não recebeu qualquer sugestão hipnótica. No Estudo 2 foi seguido o mesmo procedimento, mas a cerca de metade dos participantes foi atribuída uma tarefa fácil (enviar um Adherence to health-related behaviors ix SMS com a avaliação diária do seu estado de humor naquele momento) e à outra metade da amostra foi atribuída a tarefa de exercício físico atrás descrita (tarefa difícil). Os resultados do estudo 1 mostraram uma interacção significativa entre o nível de sugestionabilidade dos participantes e a sugestão pós-hipnótica (p<.01) indicando que a administração da sugestão pós-hipnótica aumentou a adesão nos participantes muito sugestionáveis, mas baixou a adesão nos participantes pouco sugestionáveis. Não se encontraram diferenças entre os grupos que formaram intenções de meta e os que formaram implementação de intenções. No Estudo 2 os resultados indicaram que os participantes aderiram significativamente mais à tarefa fácil do que à tarefa difícil (p<.001). Os resultados não revelaram diferenças significativas entre as condições implementações de intenções, hipnose e as duas estratégias combinadas, indicando que a implementação de intenções não foi eficaz no aumento da adesão às duas tarefas propostas e não beneficiou da combinação com as sugestões pós-hipnóticas. A utilização da hipnose com sugestão pós-hipnótica significativamente reduziu a adesão a ambas as tarefas. Dado que não existiam instrumentos em Português destinados a avaliar a sugestionabilidade hipnótica, traduziu-se e adaptou-se para Português Escala de Grupo de sugestibilidade hipnótica de Waterloo-Stanford (WSGC): Forma C. A amostra Portuguesa (N=625) apresentou resultados semelhantes aos encontrados nas amostras de referência em termos do formato da distribuição dos padrões da pontuação e do índice de dificuldade dos itens. Contudo, a proporção de estudantes portugueses encontrada que pontuaram na zona superior de sugestionabilidade foi significativamente inferior à proporção de participantes na mesma zona encontrada nas amostras de referência. No sentido de lançar alguma luz sobre as razões para este resultado, inquiriu-se alguns dos participantes acerca das suas atitudes face à hipnose utilizando uma versão portuguesa da Escala de Valência de Atitudes e Crenças face à Hipnose e comparou-se com a opinião de Adherence to health-related behaviors xAbstract: On the basis of Gollwitzer’s (1993, 1999) implementation intentions’ concept, and Kirsch & Lynn’s (1997) response set theory, this dissertation tested the effectiveness of a combined intervention of implementation intentions with hypnosis with posthypnotic suggestions in enhancing adherence to a simple (mood report) and a difficult (physical activity) health-related task. Participants were enrolled in a university in New Jersey (N=124, Study 1, USA) and in two universities in Lisbon (N=323, Study 2, Portugal). In both studies participants were selected from a broader sample based on their suggestibility scores using the Waterloo-Stanford Group C (WSGC) scale of hypnotic susceptibility and then randomly assigned to the experimental groups. Study 1 used a 2x2x3 factorial design (instruction x hypnosis x level of suggestibility) and Study 2 used a 2 x 2x 2 x 4 factorial design (task x instructions x hypnosis x level of suggestibility). In Study 1 participants were asked to run in place for 5 minutes each day for a three-week period, to take their pulse rate before and after the activity, and to send a daily email report to the experimenter, thus providing both a self-report and a behavioral measure of adherence. Participants in the goal intention condition were simply asked to run in place and send the e-mail once a day. Those in the implementation intention condition were further asked to specify the exact place and time they would perform the physical activity and send the e-mail. In addition, half of the participants were given a post-hypnotic suggestion indicating that the thought of running in place would come to mind without effort at the appropriate moment. The other half did not receive a posthypnotic suggestion. Study 2 followed the same procedure, but additionally half of the participants were instructed to send a mood report by SMS (easy task) and half were assigned to the physical activity task described above (difficult task). Adherence to health-related behaviors vii Study 1 result’s showed a significant interaction between participant’s suggestibility level and posthypnotic suggestion (p<.01) indicating that posthypnotic suggestion enhanced adherence among highly suggestible participants, but lowered it among low suggestible individuals. No differences between the goal intention and the implementation intentions groups were found. In Study 2, participants adhered significantly more (p<.001) to the easy task than to the difficult task. Results did not revealed significant differences between the implementation intentions, hypnosis and the two conditions combined, indicating that implementation intentions was not enhanced by hypnosis with posthypnotic suggestion, neither was effective as single intervention in enhancing adherence to any of the tasks. Hypnosis with posthypnotic suggestion alone significantly reduced adherence to both tasks in comparison with participants that did not receive hypnosis. Since there were no instruments in Portuguese language to asses hypnotic suggestibility, the Waterloo-Stanford Group C (WSGC) scale of hypnotic susceptibility was translated and adapted to Portuguese and was used in the screening of a sample of college students from Lisbon (N=625). Results showed that the Portuguese sample has distribution shapes and difficulty patterns of hypnotic suggestibility scores similar to the reference samples, with the exception of the proportion of Portuguese students scoring in the high range of hypnotic suggestibility, that was found lower than the in reference samples. In order to shed some light on the reasons for this finding participant’s attitudes toward hypnosis were inquired using a Portuguese translation and adaptation of the Escala de Valencia de Actitudes y Creencias Hacia la Hipnosis, Versión Cliente, and compared with participants with no prior hypnosis experience (N=444). Significant differences were found between the two groups with participants without hypnosis experience scoring higher in factors indicating misconceptions and negative attitudes about hypnosis.