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.

Sequencing cutting patterns with colored interval graphs

The problem addressed here originates in the industry of flat glass cutting and wood panel sawing, where smaller items are cut from larger items accordingly to predefined cutting patterns. In this type of industry the smaller pieces that are cut from the patterns are piled around the machine in stacks according to the size of the pieces, which are moved to the warehouse only when all items of the same size have been cut. If the cutting machine can process only one pattern at a time, and the workspace is limited, it is desirable to set the sequence in which the cutting patterns are processed in a way to minimize the maximum number of open stacks around the machine. This problem is known in literature as the minimization of open stacks (MOSP). To find the best sequence of the cutting patterns, we propose an integer programming model, based on interval graphs, that searches for an appropriate edge completion of the given graph of the problem, while defining a suitable coloring of its vertices.

Data fusion with computational intelligence techniques: a case study of fuzzy inference for terrain assessment

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

International consensus conference on PFAPA syndrome: Evaluation of a new set of diagnostic criteria

The PFAPA syndrome is characterized by periodic fever, associated with pharyngitis, cervical adenitis and/or aphtous stomatitis and belongs to the auto-inflammatory diseases. Diagnostic criteria are based on clinical features and the exclusion of other periodic fever syndromes. An analysis of a large cohort of patients has shown weaknesses for these criteria and there is a lack of international consensus. An International Conference was held in Morges in November 2008 to propose a new set of classification criteria based on a consensus among experts in the field. We aimed to verify the applicability of the new set of classification criteria. 80 patients diagnosed with PFAPA syndrome from 3 centers (Genoa, Lausanne and Geneva) for pediatric rheumatology were included in the study. A detailed description of the clinical and laboratory features was obtained. The new classification criteria and the actual diagnostic criteria were applied to the patients. Only 43/80 patients (53.8%) fulfilled all criteria of the new classification. 31 patients were excluded because they didn't meet one of the 7 diagnostic criteria, 8 because of 2 criteria, and one because of 3 criteria. When we applied the current criteria to the same patients, 11/80 patients (13%) needed to be excluded. 8/80 patients (10%) were excluded from both sets. Exclusion was related only to some of the criteria. Number of patients for each not fulfilled criterion (new set of criteria/actual criteria): age (1/6), symptoms between episodes (2/2), delayed growth (3/3), main symptoms (21/0), periodicity, length of fever, interval between episodes, and length of disease (19/0). The application of some of the new criteria was not easy, as they were both very restrictive and needed precise information from the patients. Our work has shown that the new set of classification criteria can be applied to patients suspected for PFAPA syndrome, but it seems to be more restrictive than the actual diagnostic criteria. A further work of validation needs to be done for this new set of classification criteria in order to determine if these criteria allow a good discrimination between PFAPA patients and other causes of recurrent fever syndromes.

International consensus conference on PFAPA syndrome: evaluation of a new set of classification criteria

INTRODUCTION: PFAPA syndrome is characterized by periodic fever, associated with pharyngitis, cervical adenitis and/or aphthous stomatitis and belongs to the auto-inflammatory diseases. Diagnostic criteria are based on clinical features and the exclusion of other periodic fever syndromes. An analysis of a large cohort of patients has shown weaknesses for these criteria and there is a lack of international consensus. An International Conference was held in Morges in November 2008 to propose a new set of classification criteria based on a consensus among experts in the field.OBJECTIVE: We aimed to verify the applicability of the new set of classification criteria.PATIENTS & METHODS: 80 patients diagnosed with PFAPA syndrome from 3 centers (Genoa, Lausanne and Geneva) for pediatric rheumatology were included in the study. A detailed description of the clinical and laboratory features was obtained. The new classification criteria and the actual diagnostic criteria were applied to the patients.RESULTS: Only 40/80 patients (50%) fulfilled all criteria of the new classification. 31 patients were excluded because they didn't meet one of the 7 diagnostic criteria, 7 because of 2 criteria, and one because of 3 criteria. When we applied the current criteria to the same patients, 11/80 patients (13.7%) needed to be excluded. 8/80 patients (10%) were excluded from both sets. Exclusion was related only to some of the criteria. Number of patients for each not fulfilled criterion (new set of criteria/actual criteria): age (1/6), symptoms between episodes (2/2), delayed growth (4/1), main symptoms (21/0), periodicity, length of fever, interval between episodes, and length of disease (20/0). The application of some of the new criteria was not easy, as they were both very restrictive and needed precise information from the patients.CONCLUSION: Our work has shown that the new set of classification criteria can be applied to patients suspected for PFAPA syndrome, but it seems to be more restrictive than the actual diagnostic criteria. A further work of validation needs to be done in order to determine if this new set of classification criteria allow a good discrimination between PFAPA patients and other causes of recurrent fever syndromes.

Gap probabilities for the cardinal sine

We study the zero set of random analytic functions generated by a sum of the cardinal sine functions which form an orthogonal basis for the Paley-Wiener space. As a model case, we consider real-valued Gaussian coefficients. It is shown that the asymptotic probability that there is no zero in a bounded interval decays exponentially as a function of the length.

Measures of fit in multiple correspondence analysis of crisp and fuzzy coded data

When continuous data are coded to categorical variables, two types of coding are possible: crisp coding in the form of indicator, or dummy, variables with values either 0 or 1; or fuzzy coding where each observation is transformed to a set of "degrees of membership" between 0 and 1, using co-called membership functions. It is well known that the correspondence analysis of crisp coded data, namely multiple correspondence analysis, yields principal inertias (eigenvalues) that considerably underestimate the quality of the solution in a low-dimensional space. Since the crisp data only code the categories to which each individual case belongs, an alternative measure of fit is simply to count how well these categories are predicted by the solution. Another approach is to consider multiple correspondence analysis equivalently as the analysis of the Burt matrix (i.e., the matrix of all two-way cross-tabulations of the categorical variables), and then perform a joint correspondence analysis to fit just the off-diagonal tables of the Burt matrix - the measure of fit is then computed as the quality of explaining these tables only. The correspondence analysis of fuzzy coded data, called "fuzzy multiple correspondence analysis", suffers from the same problem, albeit attenuated. Again, one can count how many correct predictions are made of the categories which have highest degree of membership. But here one can also defuzzify the results of the analysis to obtain estimated values of the original data, and then calculate a measure of fit in the familiar percentage form, thanks to the resultant orthogonal decomposition of variance. Furthermore, if one thinks of fuzzy multiple correspondence analysis as explaining the two-way associations between variables, a fuzzy Burt matrix can be computed and the same strategy as in the crisp case can be applied to analyse the off-diagonal part of this matrix. In this paper these alternative measures of fit are defined and applied to a data set of continuous meteorological variables, which are coded crisply and fuzzily into three categories. Measuring the fit is further discussed when the data set consists of a mixture of discrete and continuous variables.

Biplots of fuzzy coded data

A biplot, which is the multivariate generalization of the two-variable scatterplot, can be used to visualize the results of many multivariate techniques, especially those that are based on the singular value decomposition. We consider data sets consisting of continuous-scale measurements, their fuzzy coding and the biplots that visualize them, using a fuzzy version of multiple correspondence analysis. Of special interest is the way quality of fit of the biplot is measured, since it is well-known that regular (i.e., crisp) multiple correspondence analysis seriously under-estimates this measure. We show how the results of fuzzy multiple correspondence analysis can be defuzzified to obtain estimated values of the original data, and prove that this implies an orthogonal decomposition of variance. This permits a measure of fit to be calculated in the familiar form of a percentage of explained variance, which is directly comparable to the corresponding fit measure used in principal component analysis of the original data. The approach is motivated initially by its application to a simulated data set, showing how the fuzzy approach can lead to diagnosing nonlinear relationships, and finally it is applied to a real set of meteorological data.

On the concept of optimality interval

The approximants to regular continued fractions constitute `best approximations' to the numbers they converge to in two ways known as of the first and the second kind.This property of continued fractions provides a solution to Gosper's problem of the batting average: if the batting average of a baseball player is 0.334, what is the minimum number of times he has been at bat? In this paper, we tackle somehow the inverse question: given a rational number P/Q, what is the set of all numbers for which P/Q is a `best approximation' of one or the other kind? We prove that inboth cases these `Optimality Sets' are intervals and we give aprecise description of their endpoints.

Coalitionally monotonic set-solutions for cooperative TU games

A static comparative study on set-solutions for cooperative TU games is carried out. The analysis focuses on studying the compatibility between two classical and reasonable properties introduced by Young (1985) in the context of single valued solutions, namely core-selection and coalitional monotonicity. As the main result, it is showed that coalitional monotonicity is not only incompatible with the core-selection property but also with the bargaining-selection property. This new impossibility result reinforces the tradeoff between these kinds of interesting and intuitive economic properties. Positive results about compatibility between desirable economic properties are given replacing the core selection requirement by the core-extension property.

Coalitionally monotonic set-solutions for cooperative TU games

A static comparative study on set-solutions for cooperative TU games is carried out. The analysis focuses on studying the compatibility between two classical and reasonable properties introduced by Young (1985) in the context of single valued solutions, namely core-selection and coalitional monotonicity. As the main result, it is showed that coalitional monotonicity is not only incompatible with the core-selection property but also with the bargaining-selection property. This new impossibility result reinforces the tradeoff between these kinds of interesting and intuitive economic properties. Positive results about compatibility between desirable economic properties are given replacing the core selection requirement by the core-extension property.

Comparing interval breast cancer rates in Norway and North Carolina: results and challenges.

OBJECTIVE: To compare interval breast cancer rates (ICR) between a biennial organized screening programme in Norway and annual opportunistic screening in North Carolina (NC) for different conceptualizations of interval cancer. SETTING: Two regions with different screening practices and performance. METHODS: 620,145 subsequent screens (1996-2002) performed in women aged 50-69 and 1280 interval cancers were analysed. Various definitions and quantification methods for interval cancers were compared. RESULTS: ICR for one year follow-up were lower in Norway compared with NC both when the rate was based on all screens (0.54 versus 1.29 per 1000 screens), negative final assessments (0.54 versus 1.29 per 1000 screens), and negative screening assessments (0.53 versus 1.28 per 1000 screens). The rate of ductal carcinoma in situ was significantly lower in Norway than in NC for cases diagnosed in both the first and second year after screening. The distributions of histopathological tumour size and lymph node involvement in invasive cases did not differ between the two regions for interval cancers diagnosed during the first year after screening. In contrast, in the second year after screening, tumour characteristics remained stable in Norway but became prognostically more favorable in NC. CONCLUSION: Even when applying a common set of definitions of interval cancer, the ICR was lower in Norway than in NC. Different definitions of interval cancer did not influence the ICR within Norway or NC. Organization of screening and screening performance might be major contributors to the differences in ICR between Norway and NC.

Fuzzy Principal Components Analysis

Due to the large number of characteristics, there is a need to extract the most relevant characteristicsfrom the input data, so that the amount of information lost in this way is minimal, and the classification realized with the projected data set is relevant with respect to the original data. In order to achieve this feature extraction, different statistical techniques, as well as the principal components analysis (PCA) may be used. This thesis describes an extension of principal components analysis (PCA) allowing the extraction ofa finite number of relevant features from high-dimensional fuzzy data and noisy data. PCA finds linear combinations of the original measurement variables that describe the significant variation in the data. The comparisonof the two proposed methods was produced by using postoperative patient data. Experiment results demonstrate the ability of using the proposed two methods in complex data. Fuzzy PCA was used in the classificationproblem. The classification was applied by using the similarity classifier algorithm where total similarity measures weights are optimized with differential evolution algorithm. This thesis presents the comparison of the classification results based on the obtained data from the fuzzy PCA.

A Topological Approach to Fuzzy Sets

This thesis presents a topological approach to studying fuzzy setsby means of modifier operators. Modifier operators are mathematical models, e.g., for hedges, and we present briefly different approaches to studying modifier operators. We are interested in compositional modifier operators, modifiers for short, and these modifiers depend on binary relations. We show that if a modifier depends on a reflexive and transitive binary relation on U, then there exists a unique topology on U such that this modifier is the closure operator in that topology. Also, if U is finite then there exists a lattice isomorphism between the class of all reflexive and transitive relations and the class of all topologies on U. We define topological similarity relation "≈" between L-fuzzy sets in an universe U, and show that the class LU/ ≈ is isomorphic with the class of all topologies on U, if U is finite and L is suitable. We consider finite bitopological spaces as approximation spaces, and we show that lower and upper approximations can be computed by means of α-level sets also in the case of equivalence relations. This means that approximations in the sense of Rough Set Theory can be computed by means of α-level sets. Finally, we present and application to data analysis: we study an approach to detecting dependencies of attributes in data base-like systems, called information systems.