There have been several pioneering approaches to the extraction of attribute implications from a formal context, dating from the 1980's: the one of Guigues and Duquenne based on so-called non-redundancy nodes, another one proposed by Ganter highlighting the concept of pseudo-closed set, and the best-known one relying on the recursive computation of so-called pseudo-intents in the book by Ganter and Wille. The Guigues and Duquenne approach has never been compared in detail in the literature with the other two, although they turn out to be equivalent. This paper tries to fill this gap, proposing a unified view, hopefully more easy to grasp.

Formal concept analysis theory (FCA) classically relies on the use of the Galois powerset operator. Formal similarities between possibility theory and formal concept analysis have led to the use of possibilistic operators in FCA, which were ignored before. In this paper, an approach based on the use of asymmetric composition of the two most usual possibilistic operators is proposed. It enables us to complement the stem base, by deriving attribute implications with disjunctions on both sides of the implications. Besides, the approach is also generalized to incomplete contexts involving explicit positive and negative information. We outline the potential application of these results to the completion of TBoxes in description logic.

This survey paper provides an overview of existing methods for building possibility distributions. We both consider the case of qualitative possibility theory, where the scale remains ordinal, and the case of quantitative possibility theory, where the scale is the real interval [0, 1]. Methods may be order-based or similarity-based for qualitative possibility distributions, whereas statistical methods apply in the quantitative case and then possibilities encode nested random epistemic sets or upper bounds of probabilities. But distance-based approaches, or expert estimates, may be also exploited in the quantitative case.

Necessary and sufficient conditions for choice functions to be rational have been intensively studied in the past. However, in these attempts, a choice function is completely specified. That is, given any subset of options, called an issue, the best option over that issue is always known, whilst in real-world scenarios, it is very often that only a few choices are known instead of all. In this paper, we study partial choice functions and investigate necessary and sufficient rationality conditions for situations where only a few choices are known. We prove that our necessary and sufficient condition for partial choice functions boils down to the necessary and sufficient conditions for complete choice functions proposed in the literature. Choice functions have been instrumental in belief revision theory. That is, in most approaches to belief revision, the problem studied can simply be described as the choice of possible worlds compatible with the input information, given an agent’s prior belief state. The main effort has been to devise strategies in order to infer the agents revised belief state. Our study considers the converse problem: given a collection of input information items and their corresponding revision results (as provided by an agent), does there exist a rational revision operation used by the agent and a consistent belief state that may explain the observed results?

From a knowledge representation point of view, it may be interesting to distinguish between (i) what is potentially possible because it is not inconsistent with the available knowledge on the one hand, and (ii) what is actually possible because it is reported from observations on the other hand. Such a distinction also makes sense when expressing preferences, to point out positively desired choices among merely tolerated ones. Possibility theory provides a representation framework where this distinction can be made in a graded way. The two types of information can be encoded by two types of constraints expressed in terms of necessity measures and in terms of so-called guaranteed possibility functions. These two set-functions are min-decomposable with respect to conjunction and disjunction, respectively. This gives birth to two forms of possibilistic logic bases, where clauses (resp., phrases) are weighted in terms of a necessity measure (resp., a guaranteed possibility function). By application of a minimal commitment principle, the two bases induce a pair of possibility distributions at the semantic level, for which a consistency condition should hold to ensure that what is claimed to be actually possible is indeed not impossible. The paper provides a survey of this bipolar representation framework, including the use of conditional measures, or the handling of comparative context-dependent constraints. The interest of the framework is stressed for expressing preferences, as well as in the representation of “if–then” rules in terms of examples and counterexamples. © 2008 Wiley Periodicals, Inc.

Bipolarity seems to pervade human understanding of information and preference, and bipolar representations look very useful in the development of intelligent technologies. Bipolarity refers to an explicit handling of positive and negative sides of information. Basic notions and background on bipolar representations are provided. Three forms of bipolarity are laid bare: symmetric univariate, dual bivariate, and asymmetric (or heterogeneous) bipolarity. They can be instrumental in the logical handling of incompleteness and inconsistency, rule representation and extraction, argumentation, learning, and decision analysis. © 2008 Wiley Periodicals, Inc.

Uncertain relations between temporal points are represented by means of possibility distributions over the three basic relations precedes, equals, and follows. Operations for computing inverse relation, for composing relations, for combining relations coming from different sources and pertaining to the same temporal points, or for representing negative information are defined. An illustrative example of representation and reasoning with uncertain temporal relations is provided. This article shows how possibilistic temporal uncertainty can be handled in the setting of point algebra. Moreover, the article emphasizes the advantages of the possibilistic approach over a probabilistic approach previously proposed. This work does for the temporal point algebra what the authors previously did for the temporal interval algebra. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 157–179, 2007.

This article proposes a principled approach to multicriteria decision making (MCDM) where the worth of decisions along attributes is not supposed to be quantified, as in multiattribute utility theory, or even measured on a unique scale. This approach actually generalizes additive concordance rules a la Electre and is rigorously justified in an axiomatic way by representation theorems. We indeed show that the use of a generalized concordance (GC) rule is the only possible approach when in a purely ordinal framework and that the satisfaction of very simple principles forces the use of possibility theory as the unique way of expressing the importance of coalitions of criteria. © 2003 Wiley Periodicals, Inc.

This article expresses the idea that information encoded on a computer may have a negative or positive emphasis. Negative information corresponds to the statement that some situations are impossible. Often, it is the case for pieces of background knowledge expressed in a logical format. Positive information corresponds to observed cases. It is encountered often in data-driven mathematical models, learning, etc. The notion of an “if …, then …” rule is examined in the context of positive and negative information. It is shown that it leads to the three-valued representation of a rule, after De Finetti, according to which a given state of the world is an example of the rule, a counterexample to the rule, or is irrelevant for the rule. This view also sheds light on the typology of fuzzy rules. It explains the difference between a fuzzy rule modeled by a many-valued implication and expressing negative information and a fuzzy rule modeled by a conjunction (a la Mamdani) and expressing positive information. A new compositional rule of inference adapted to conjunctive rules, specific to positive information, is proposed. Consequences of this framework on interpolation between sparse rules are also presented. © 2003 Wiley Periodicals, Inc.

The problem of combining pieces of information issued from several sources can be encountered in various fields of application. This paper aims at presenting the different aspects of information fusion in different domains, such as databases, regulations, preferences, sensor fusion, etc., at a quite general level. We first present different types of information encountered in fusion problems, and different aims of the fusion process. Then we focus on representation issues which are relevant when discussing fusion problems. An important issue is then addressed, the handling of conflicting information. We briefly review different domains where fusion is involved, and describe how the fusion problems are stated in each domain. Since the term fusion can have different, more or less broad, meanings, we specify later some terminology with respect to related problems, that might be included in a broad meaning of fusion. Finally we briefly discuss the difficult aspects of validation and evaluation. © 2001 John Wiley & Sons, Inc.

The problem of assessing the value of a candidate is viewed here as a multiple combination problem. On the one hand, a candidate can be evaluated according to different criteria, and on the other hand, several experts are supposed to assess the value of candidates according to each criterion. Criteria are not equally important, experts are not equally competent or reliable. Moreover, levels of satisfaction of criteria, or levels of confidence are only assumed to take their values in linearly ordered scales, whose nature is rather qualitative. The problem is discussed within two frameworks, the transferable belief model (TBM) and the qualitative possibility theory (QPT). They respectively offer a quantitative and a qualitative setting for handling the problem, thus providing a way to emphasize what are the underlying assumptions in each approach. © 2001 John Wiley & Sons, Inc.

Fuzzy logic is known for providing a convenient tool for interfacing linguistic categories with numerical data and for expressing user's preference in a gradual and qualitative way. Fuzzy set methods have been already applied to the representation of flexible queries and to the modeling of uncertain pieces of information in databases systems, as well as in information retrieval. This methodology seems to be even more promising in multimedia databases which have a complex structure and from which documents have to be retrieved and selected not only from their contents, but also from "the idea" the user has of their appearance, through queries specified in terms of user's criteria. This paper provides a preliminary investigation of the potential applications of fuzzy logic in multimedia databases. The problem of comparing semistructured documents is first discussed. Querying issues are then more particularly emphasized. We distinguish two types of request, namely, those which can be handled within some extended version of an SQL-like language and those for which one has to elicit user's preference through examples.

This short overview paper points out the striking similarity between decision under uncertainty and multicriteria decision making problems, two areas which have been developed in an almost completely independent way until now. This pertains both to additive and non-additive (including qualitative) approaches existing for the two decision paradigms. This leads to an emphasis on the remarkable formal equivalence between postulates underlying these approaches (like between the “sure-thing principle” and mutual preferential independence of criteria). This analogy is exploited by surveying classical results as well as very recent advances. This unified view should be fruitful for a better understanding of the postulates underlying the approaches, for cross-fertilization, and for adapting artificial intelligence uncertainty representation frameworks to preference modelling. © 2000 John Wiley & Sons, Inc.

This paper provides a brief survey and an introduction to the modeling capabilities of qualitative possibility theory in decision analysis for the representation and the aggregation of preferences, for the treatment of uncertainty and for the handling of situations similar to previously encountered ones. “Qualitative” here means that we restrict ourselves to linearly ordered valuation sets (only the ordering of the grades is meaningful) for the assessment of preferences, uncertainty and similarity. Moreover, all the evaluations refer to the same valuation set (commensurability assumption). Such a qualitative structure is poor but not very demanding from an elicitation point of view; however, it is sufficient for giving birth to a valuable set of modeling tools. ©1999 John Wiley & Sons, Inc.

This paper is an attempt at providing a fuzzy set formalization of case-based reasoning and decision. Learning aspects are not considered here. The proposed approach assumes a principle stating that “the more similar are the problem description attributes, the more similar are the outcome attributes.” A weaker form of this principle concluding only on the graded possibility of the similarity of the outcome attributes, is also considered. These two forms of the case-based reasoning principle are modelled in terms of fuzzy rules. Then an approximate reasoning machinery taking advantage of this principle enables us to apply the information stored in the memory of previous cases to the current problem. A particular instance of case-based reasoning, named case-based decision, is especially investigated. A logical formalization of the basic case-based reasoning inference is also proposed. Extensions of the proposed approach in order to handle imprecise or fuzzy descriptions or to manage more general forms of the principle underlying case-based reasoning are briefly discussed in the conclusion. © 1998 John Wiley & Sons, Inc.

In the context of regular relational databases, functional dependencies have received a lot of attention, since they capture some semantics about the data related to redundancy. Functional dependencies lead to an appropriate design of a database in terms of a set of relations and can make the checking process of integrity constraints significantly easier. For about 10 years, several proposals to deal with ill-known information in database management systems have been made, and extensions of the relational data model have been proposed accordingly. In this context, the idea of fuzzy functional dependency has emerged to extend the classical functional dependency, and several definitions have been proposed. In this article, an overview of these different proposals is provided, and the connection between fuzzy functional dependencies and database design is discussed. In addition, some semantics and use of fuzzy functional dependencies are suggested. © 1998 John Wiley & Sons, Inc.

The paper proposes a parallel survey of revision and updating operations available in the probability theory and in the possibility theory frameworks. In these two formalisms the current state of knowledge is generally represented by a [0,1]-valued function whose domain is an exhaustive set of mutually exclusive possible states of the world. However, in possibility theory, the unit-interval can be viewed as a purely ordinal scale. Two general kinds of operations can be defined on this assignment function: conditioning, and imaging (or “projection”). the difference between these two operations is analogous to the one made between belief revision à la Gärdenfors and updating à la Katsuno and Mendelzon in the logical framework. In the probabilistic framework these two operations are respectively Bayesian conditioning and Lewis' imaging. Counterparts to these operations are presented for the possibilistic framework including the case of conditioning upon uncertain observations, and justifications are given which parallel the ones existing for the probabilistic operations. More particularly, it is recalled that possibilistic conditioning satisfies all the postulates proposed by Alchourrón, Gärdenfors and Makinson for belief revision (stated in possibilistic terms), and it is proved that possibilistic imaging satisfies all the postulates proposed by Katsuno and Mendelzon. the situation where our current knowledge is stated in terms of weighted logical propositions is discussed in connection to possibility theory. Revision in other more complex numerical formalisms, namely belief and plausibility functions, and upper and lower probabilities is also surveyed. Recent results on the revision of conditional knowledge bases are also reviewed. the frameworks of belief functions, upper and lower probabilities and conditional bases are more sophisticated than the previous ones because they enable to distinguish between factual evidence and generic knowledge in a cognitive state. This, framework leads to two forms of belief revision respectively taking care of the revision of evidence and the revision of knowledge. © 1994 John Wiley & Sons, Inc.

An approach to automated deduction under uncertainty, based on possibilistic logic, is described; for that purpose we deal with clauses weighted by a degree that is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the classical refutation method can be generalized with these rules. Also, the lower bounds are allowed to be functions of variables involved in the clauses, which results in hypothetical reasoning capabilities. In cases where only lower bounds of necessity measures are involved, a semantics is proposed in which the completeness of the extended resolution principle is proved. The relation between our approach and the idea of minimizing abnormality is briefly discussed. Moreover, deduction from a partially inconsistent knowledge base can be managed in this approach and captures a form of nonmonotonicity.>

Knowledge representation issues related to the modelling of imprecision and uncertainty are discussed in the framework of possibility theory. Differences and relations between possibility theory, fuzzy sets, probability theory and Shafer evidence theory are presented. Then, patterns of reasoning and inference and control procedures are studied in presence of uncertainty and imprecision using a possibilistic approach. the basic ideas and the main trends are emphasized rather than the mathematical and logical foundations or the technical details of implementation which can be found in the references.

ks

Dempster has proposed a rule for the combination of uncertain items of information issued from several sources. This note proves the unicity of this rule under an independence assumption. the existence of alternative rules is stressed, some corresponding to different assumptions, others pertaining to different types of combination.