Search

I sistemi software per l'automazione di attività safety-critical in domini applicativi (ad esempio avionica, ferrovie, automotive, industria 4.0 e assistenza sanitaria) devono essere altamente affidabili. In questa tesi, ci concentriamo sul software safety-critical scritto in Scade, un linguaggio di programmazione model-based ampiamente adottato nell'industria, da noi utilizzato per lo sviluppo di programmi Scade safety-critical per il dominio ferroviario. La generazione automatica di test (stato dell'arte) basata sull'esecuzione simbolica e sul bounded model checking può essere utile per testare sistematicamente il software safety-critical al fine di facilitare gli ingegneri nel rispettare i severi requisiti di test imposti dagli standard di certificazione, controllando al contempo il costo del processo di testing. Allo stesso tempo, lo sviluppo di software safety-critical è spesso vincolato da linguaggi di programmazione o convenzioni di codifica che vietano caratteristiche del codice che si ritiene riducano la sicurezza dei programmi, ad esempio, non consentono l'allocazione dinamica della memoria e array di lunghezza variabile, limitano il modo in cui vengono utilizzati i cicli, proibiscono la ricorsione e limitano la complessità delle condizioni di controllo. Abbiamo sfruttato generatori di test allo stato dell’arte basati sull’esecuzione simbolica e il bounded model checking al fine di definire una toolchain originale per la generazione di casi test per programmi Scade. Abbiamo valutato l’efficacia della nostra toolchain nel generare i casi di test automaticamente con un benchmark di 37 programmi Scade sviluppati come parte di un sistema di segnalazione di bordo per sistemi ferroviari ad alta velocità sviluppato in collaborazione con un partner industriale., Software systems for automating safety-critical tasks in application domains like, avionics, railways, automotive, industry 4.0, and healthcare must be highly reliable. In this thesis, we focus on safety-critical software written in Scade, a model-based programming language largely adopted in industry, that we used for developing safety-critical Scade programs for the railway domain. Automated test generation (state-of-the-art) based on symbolic execution and bounded model checking can be beneficial for systematically testing safety-critical software to facilitate test engineers in pursuing the strict testing requirements mandated by the certification standards while controlling the cost of the testing process. At the same time, the development of safety-critical software is often constrained by programming languages or coding conventions that ban linguistic features believed to downgrade the safety of programs, e.g., they do not allow dynamic memory allocation and variable-length arrays, limit the way in which loops are used, forbid recursion, and limit the complexity of control conditions. We leverage state-of-the-art test generators based on symbolic execution and bounded model checking in order to define an original toolchain for generating test cases for Scade programs. We evaluate the effectiveness of our toolchain for automatic test generation with a benchmark of 37 Scade programs developed as part of an onboard signalling unit for high-speed railway systems developed in collaboration with an industrial partner.

La rappresentazione, quantificazione e gestione dell'incertezza è uno dei problemi centrali nell'Intelligenza Artificiale, ed in particolare nel Machine Learning, in cui l'incertezza è intrinsecamente collegata alla natura induttiva dell'apprendimento. Tra diverse forme d'incertezza, la modellazione dell'imprecisione, cioè il problem di gestire dati o conoscenza imperfetta o incompleta, ha recentemente attratto molto interesse nella comunità di ricerca, per via delle sue implicazione teoriche e applicate sull'uso di strumenti basati sul Machine Learning. Questo lavoro si concentra sul problema di gestire l'imprecision nel Machine Learning, sotto due diverse prospettive. Da un lato, l'imprecisione che riguarda i dati di input alla pipeline di Machine Learning, da cui si origina il problema dell'apprendimento da dati imprecisi. Dall'altro, l'imprecisione come strumento per implementare processi di quantificazione dell'incertezza nel Machine Learning, al fine di permettere a questi ultimi di fornire previsioni set-valued e portare quindi alla definizione di metodi di inferenza cauta. Lo scopo di questo lavoro, quindi, riguarda lo studio teorico ed empirico dei due scenari summenzionati. Per quanto riguarda il problema dell'apprendimento da dati imprecisi, il focus principale riguarda l'investigazione del problema dell'apprendimento da fuzzy label, sia da un punto di visto teorico che algoritmo. I contributi principali includono: la proposta di una caratterizzazione teorica del problema; la proposta di un nuovo algoritmo di ensemble, basato su pseudo-label, e il suo studio dal punto di visto teorico ed empirico; l'applicazione del summenzionato algoritmo in tre problemi medici reali; ed infine la proposta e lo studio di algoritmi di feature selection per ridurre la complessità computazionale e limitare la "curse of dimensionality" per algoritmi di apprendimento da fuzzy label. Per quanto riguarda l'inferenza cauta, il focus principale riguarda lo studio teorico di, The representation, quantification and proper management of uncertainty is one of the central problems in Artificial Intelligence, and particularly so in Machine Learning, in which uncertainty is intrinsically tied to the inductive nature of the learning problem. Among different forms of uncertainty, the modeling of imprecision, that is the problem of dealing with data or knowledge that are imperfect} and incomplete, has recently attracted interest in the research community, for its theoretical and application-oriented implications on the practice and use of Machine Learning-based tools and methods. This work focuses on the problem of dealing with imprecision in Machine Learning, from two different perspectives. On the one hand, when imprecision affects the input data to a Machine Learning pipeline, leading to the problem of learning from imprecise data. On the other hand, when imprecision is used a way to implement uncertainty quantification for Machine Learning methods, by allowing these latter to provide set-valued predictions, leading to so-called cautious inference methods. The aim of this work, then, will be to investigate theoretical as well as empirical issues related to the two above mentioned settings. Within the context of learning from imprecise data, focus will be given on the investigation of the learning from fuzzy labels setting, both from a learning-theoretical and algorithmic point of view. Main contributions in this sense include: a learning-theoretical characterization of the hardness of learning from fuzzy labels problem; the proposal of a novel, pseudo labels-based, ensemble learning algorithm along with its theoretical study and empirical analysis, by which it is shown to provide promising results in comparison with the state-of-the-art; the application of this latter algorithm in three relevant real-world medical problems, in which imprecision occurs, respectively, due to the presence of conflicting expert opinions, the use of vague technical

Our article “A map of dependencies among three-valued logics” (Information Sciences, vol. 250, 161–177, 2013) contains some typing mistakes that may affect a proper understanding of the paper. They are corrected here.

The departing point of this study is a data table with certainty values associated to attribute values. These values are deeply rooted in possibility theory, they can be obtained with standard procedures and they are efficiently manageable in databases. Our aim is to study rough set approximations and reducts in this framework. We define three categories of approximations that make use of the certainty value and generalize different aspects of the approximations: their equation, the binary relation used and the granulation. Further, new kinds of reducts aimed to make use or reduce the information provided by the certainty values are given.

In many situations information comes in bipolar form. Orthopairs are a simple tool to represent and study this kind of information, where objects are classified in three different classes: positive, negative and boundary. The scope of this work is to introduce some uncertainty measures on orthopairs. Two main cases are investigated: a single orthopair and a collection of orthopairs. Some ideas are taken from neighbouring disciplines, such as fuzzy sets, intuitionistic fuzzy sets, rough sets and possibility theory.

This paper proposes a conceptually simple but expressive framework for handling propositional information stemming from several sources, namely a two-tiered propositional logic augmented with classical modal axioms (BC-logic), a fragment of the non-normal modal logic EMN, whose semantics is expressed in terms of two-valued monotonic set-functions called Boolean capacities. We present a theorem-preserving translation of Belnap logic in this setting. As special cases, we can recover previous translations of three-valued logics such as Kleene and Priest logics. Our translation bridges the gap between Belnap logic, epistemic logic, and theories of uncertainty like possibility theory or belief functions, and paves the way to a unified approach to various inconsistency handling methods.

There are several notions and terms in Rough Set Theory not having a crystal clear definition. I discuss here two basic ones: Rough Set and Information System. The discussion will be lead by the two founding papers by Z. Pawlak. We will see that the term Information System has a narrow sense (the most used one in the rough set community) and a wide one (the world wide common use of information system and also Pawlak’s one). In case of the term Rough Set, several definitions are possible, none of them without problems. Some other minor issues related to Pawlak’s papers will be highlighted.

In rough set theory (RST), and more generally in granular computing on information tables (GRC-IT), a central tool is the Pawlak's indiscernibility relation between objects of a universe set with respect to a fixed attribute subset. Let us observe that Pawlak's relation induces in a natural way an equivalence relation ≈ on the attribute power set that identifies two attribute subsets yielding the same indiscernibility partition. We call indistinguishability relation of a given information table I the equivalence relation ≈, that can be considered as a kind of global indiscernibility. In this paper we investigate the mathematical foundations of indistinguishability relation through the introduction of two new structures that are, respectively, a complete lattice and an abstract simplicial complex. We show that these structures can be studied at both a micro granular and a macro granular level and that are naturally related to the core and the reducts of I. We first discuss the role of these structures in GrC-IT by providing some interpretations, then we prove several mathematical results concerning the fundamental properties of such structures.

Two methods are proposed for collective knowledge extraction from questionnaires with ordinal scales and dichotomous questions. Both methods are based on a three-way decision procedure and a statistical method aimed at attaining statistical significance of the above decision. One method is aimed at giving an (absolute) assessment of “objects” according to a given “criterion” and the other one at producing a relative ranking of the “objects”. A criterion can be related to one or more questionnaire items (usually questions or statements). In this latter case a method to compose ordinal items in aggregate scores is also given. The paper also presents two various case studies that illustrate the methods and give motivations for their application in different domains where the knowledge of a community or any distributed group of experts can be externalized (in terms of users' perceptions, attitudes, opinions, choices) with a structured closed-ended questionnaire.

Pairs of disjoint sets (orthopairs) naturally arise or have points in common with many tools to manage uncertainty: rough sets, shadowed sets, version spaces, three-valued logics, etc. Indeed, they can be used to model partial knowledge, borderline cases, consensus, examples and counter-examples pairs. Moreover, generalized versions of orthopairs are the well known theories of Atanassov intuitionistic fuzzy sets and possibility theory and the newly established three-way decision theory. Thus, it is worth studying them on an abstract level in order to outline general properties that can then be casted to the different paradigms they are in connection with. In this paper, we will review how to define orthopairs and a hierarchy on them in the light of granular computing. Aggregation operators will also be discussed as well as possible generalizations and connections with different paradigms. This will permit us to point out new facets of these paradigms and outline some possible future developments.

Given a graph, we interpret its adjacency matrix as an information table. We study this correspondence in two directions. Firstly, on the side of graphs by applying to it standard techniques from granular computing. In this way, we are able to connect automorphisms on graphs to the so-called indiscernibility relation and a particular hypergraph built from the starting graph to core and reducts. On the other hand, new concepts are introduced on graphs that have an interesting correspondence on information tables. In particular, some new topological interpretations of the graph and the concept of extended core are given.

We present a unique framework for connecting different topics: hypergraphs from one side and Formal Concept Analysis and Rough Set Theory from the other. This is done through the formal equivalence among Boolean information tables, formal contexts and hypergraphs. Links with generic (i.e., not Boolean) information tables are established, through so-called nominal scaling. The particular case of k-uniform complete hypergraphs will then be studied. In this framework, we are able to solve typical problems of Rough Set Theory and Formal Concept Analysis using combinatorial techniques. More in detail, we will give a formula to compute the degree of dependency and the partial implication between two sets of attributes, compute the set of reducts and define the structure of the partitions generated by all the definable indiscernibility relations.

The paper shows that a cube of opposition, a structure that generalizes the square of opposition invented in ancient logic, can be generated from the composition of a binary relation with a subset, by the effect of set complementation on the subset, on the relation, or on the result of the composition. Since the composition of relations is encountered in many areas, the structure of opposition exhibited by the cube of opposition has a universal flavor. In particular, it applies to information processing-oriented settings such as rough set theory, possibility theory, or formal concept analysis. We then discuss how this structure extends to a fuzzy relation and a fuzzy subset, and the graded cube of opposition thus obtained provides an organized view of the different existing compositions of fuzzy relations. The paper concludes by pointing out areas of research where the cube of opposition, or its graded version are of interest.

In this paper we consider sequences of orthopairs given by refinement sequences of partitions of a finite universe. While operations among orthopairs can be fruitfully interpreted by connectives of threevalued logics, we describe operations among sequences of orthopairs by means of the logic IUML of idempotent uninorms having an involutive negation.

In this paper we study the lattice of all indiscernibility partitions induced from attribute subsets of a knowledge representation system (information table in the finite case). This lattice, that we here call granular partition lattice, is a very well studied order structure in granular computing and data base theory and it provides a complete hierarchical classification of the knowledge obtained from all possible choices of attribute subsets. We show that it has a lattice structure also in the infinite case and we provide several isomorphic characterizations for this lattice. We discuss the potentiality of this order structure from both a micro-granular and a macro-granular perspective. Furthermore, the sub-poset of all the indiscernibility closures needed to determine when an arbitrary partition is an indiscernibility one is studied. Finally, we show the monotonic behaviour of the granular partition lattice with respect to entropy of partitions and attribute dependency in decision tables.

We introduce and study new generalizations of some rough set tools. Namely, the extended core, the generalized discernibility function, the discernibility space and the maximum partitioner. All these concepts where firstly introduced during the application of rough set theory to graphs, here we show that they have an interesting and useful interpretation also in the general setting. Indeed, among other results, we prove that reducts can be computed in incremental polynomial time, we give some conditions in order that a partition coincides with an indiscernibility partition of a given information table and we give the conditions such that a discernibility matrix corresponds to an information table.

The adjacency matrix of a graph is interpreted as a formal context. Then, the counterpart of Formal Concept Analysis (FCA) tools are introduced in graph theory. Moreover, a formal context is seen as a Boolean information table, the structure at the basis of Rough Set Theory (RST). Hence, we also apply RST tools to graphs. The peculiarity of the graph case, put in evidence and studied in the paper, is that both FCA and RST are based on a (different) binary relation between objects.

The incidence matrix of a simple undirected graph is used as an information table. Then, rough set notions are applied to it: approximations, membership function, positive region and discernibility matrix. The particular cases of complete and bipartite graphs are analyzed. The symmetry induced in graphs by the indiscernibility relation is studied and a new concept of generalized discernibility matrix is introduced.

Two classes of graphs, the n–cycles and n–paths, are interpreted as preclusivity spaces. In this way, it is possible to define two pairs of approximations on them: one based on a preclusive relation and another one based on a similarity relation. Further, two relations can be defined among the set of vertices and they define two different graphs, which are here studied.

The adjacency relation of a simple undirected graph is a preclusive (irreflexive and symmetric) relation. Hence, it originates a preclusive space enabling us to define the lower and upper preclusive approximations of graphs and two orthogonality graphs. Further, the possibility of defining the similarity lower and upper approximations and the sufficiency operator on graphs will be investigated, with particular attention to complete and bipartite graphs. All these mappings will be put in relation with Formal Concept Analysis and the theory of opposition.

The significance of three-valued logics partly depends on the interpretation of the third truth-value. When it refers to the idea of unknown, we have shown that a number of three-valued logics, especially Kleene, Ł eene, e s, and Nelson, can be encoded in a simple fragment of the modal logic KD, called MEL, containing only modal formulas without nesting. This is the logic of possibility theory, the semantics of which can be expressed in terms of all-or-nothing possibility distributions representing an agent’s epistemic state. Here we show that this formalism can also encode some three-valued paraconsistent logics, like Priest, Jawe have, and Sobociński’s, where the third truth-value represents the idea of contradiction. The idea is just to change the designated truth-values used for their translations.We show that all these translations into modal logic are very close in spirit to Avron t early work expressing natural three-valued logics using hypersequents. Our work unifies a number of existing formalisms and the translation also highlights the perfect symmetry between three-valued logics of contradiction and three-valued logics of incomplete information, which corresponds to a swapping of modalities in MEL.

This chapter reviews three formulations of rough set theory, i. e., element-based definition, granule-based definition, and subsystem-based definition. These formulations are adopted to generalize rough sets from three directions. The first direction is to use an arbitrary binary relation to generalize the equivalence relation in the element-based definition. The second is to use a covering to generalize the partition in the granule-based definition, and the third to use a subsystem to generalize the Boolean algebra in the subsystem-based definition. In addition, we provide some insights into the theoretical aspects of these generalizations, mainly with respect to relations with non-classical logic and topology theory.

The square of opposition is as old as logic. There has been a recent renewal of interest on this topic, due to the emergence of new structures (hexagonal and cubic) extending the square. They apply to a large variety of representation frameworks, all based on the notions of sets and relations. After a reminder about the structures of opposition, and an introduction to their gradual extensions (exemplified on fuzzy sets), the paper more particularly studies fuzzy rough sets and rough fuzzy sets in the setting of gradual structures of opposition.

This paper is a survey of the connections between three-valued logics and rough sets from the point of view of incomplete information management. Based on the fact that many three-valued logics can be put under a unique algebraic umbrella, we show how to translate three-valued conjunctions and implications into operations on ill-known sets such as rough sets. We then show that while such translations may provide mathematically elegant algebraic settings for rough sets, the interpretability of these connectives in terms of an original set approximated via an equivalence relation is very limited, thus casting doubts on the practical relevance of truth-functional logical renderings of rough sets.

Our article “A map of dependencies among three-valued logics” (Information Sciences, vol. 250, 161–177, 2013) contains some typing mistakes that may affect a proper understanding of the paper. They are corrected here.

n this paper we compare the expressive power of elementary representation formats for vague, incomplete or conflicting information. These include Boolean valuation pairs introduced by Lawry and González-Rodríguez, orthopairs of sets of variables, Boolean possibility and necessity measures, three-valued valuations, supervaluations. We make explicit their connections with strong Kleene logic and with Belnap logic of conflicting information. The formal similarities between 3-valued approaches to vagueness and formalisms that handle incomplete information often lead to a confusion between degrees of truth and degrees of uncertainty. Yet there are important differences that appear at the interpretive level: while truth-functional logics of vagueness are accepted by a part of the scientific community (even if questioned by supervaluationists), the truth-functionality assumption of three-valued calculi for handling incomplete information looks questionable, compared to the non-truth-functional approaches based on Boolean possibility–necessity pairs. This paper aims to clarify the similarities and differences between the two situations. We also study to what extent operations for comparing and merging information items in the form of orthopairs can be expressed by means of operations on valuation pairs, three-valued valuations and underlying possibility distributions.

Rough set theory (RST) and formal concept analysis (FCA) are two formal settings in information management, which have found applications in learning and in data mining. Both rely on a binary relation. FCA starts with a formal context, which is a relation linking a set of objects with their properties. Besides, a rough set is a pair of lower and upper approximations of a set of objects induced by an indistinguishability relation; in the simplest case, this relation expresses that two objects are indistinguishable because their known properties are exactly the same. It has been recently noticed, with different concerns, that any binary relation on a Cartesian product of two possibly equal sets induces a cube of oppositions, which extends the classical Aristotelian square of oppositions structure, and has remarkable properties. Indeed, a relation applied to a given subset gives birth to four subsets, and to their complements, that can be organized into a cube. These four subsets are nothing but the usual image of the subset by the relation, together with similar expressions where the subset and / or the relation are replaced by their complements. The eight subsets corresponding to the vertices of the cube can receive remarkable interpretations, both in the RST and the FCA settings. One facet of the cube corresponds to the core of RST, while basic FCA operators are found on another facet. The proposed approach both provides an extended view of RST and FCA, and suggests a unified view of both of them.

Before the advent of fuzzy and rough sets, some authors in the 1960s studied three-valued logics and pairs of sets with a meaning similar to those we can encounter nowadays in modern theories such as rough sets, decision theory and granular computing. We revise these studies using the modern terminology and making reference to the present literature. Finally, we put forward some future directions of investigation

In this paper, we discuss the relationship occurring among the basic blocks of rough set theory: approximations, definable sets and exact sets. This is done in a very general framework, named Basic Approximation Space that generalizes and encompasses previous known definitions of Approximation Spaces. In this framework, the lower and upper approximation as well as the boundary and exterior region are independent from each other. Further, definable sets do not coincide with exact sets, the former being defined “a priori” and the latter only “a posteriori” on the basis of the approximations. The consequences of this approach in the particular case of partial partitions are developed and a discussion is started in the case of partial coverings.

The proceedings contain 40 papers. The topics discussed include: from vagueness to rough sets in partial approximation spaces; random probes in computation and assessment of approximate reducts; applications of Boolean kernels in rough sets; robust ordinal regression for dominance-based rough set approach under uncertainty; monotonic uncertainty measures in probabilistic rough set model; attribute subset quality functions over a universe of weighted objects; a rough set approach to novel compounds activity prediction based on surface active properties and molecular descriptors; rough sets in ortholog gene detection; hybrid model based on rough sets theory and fuzzy cognitive maps for decision-making; decision rule classifiers for multi-label decision tables; and considerations on rule induction procedures by STRIM and their relationship to VPRS.

There are several three-valued logical systems that form a scattered landscape, even if all reasonable connectives in three-valued logics can be derived from a few of them. Most papers on this subject neglect the issue of the relevance of such logics in relation with the intended meaning of the third truth-value. Here, we focus on the case where the third truth-value means unknown, as suggested by Kleene. Under such an understanding, we show that any truth-qualified formula in a large range of three-valued logics can be translated into KD as a modal formula of depth 1, with modalities in front of literals only, while preserving all tautologies and inference rules of the original three-valued logic. This simple information logic is a two-tiered classical propositional logic with simple semantics in terms of epistemic states understood as subsets of classical interpretations. We study in particular the translations of Kleene, Gödel, Łukasiewicz and Nelson logics. We show that Priest’s logic of paradox, closely connected to Kleene’s, can also be translated into our modal setting, simply by exchanging the modalities possible and necessary. Our work enables the precise expressive power of three-valued logics to be laid bare for the purpose of uncertainty management.