Practical Handling of Exception-Tainted Rules and Independence Information in Possibilistic Logic

This paper provides a survey of possibilistic logic as a simple and efficient tool for handling nonmonotonic reasoning, with some emphasis on algorithmic issues. In our previous works, two well-known nonmonotonic systems have been encoded in the possibility theory framework: the preferential inference based on System P, and the rational closure inference proposed by Lehmann and Magidor which relies on System P augmented with a rational monotony postulate. System P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of irrelevant properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious, or on the contrary, provide counter -intuitive conclusions. The paper proposes an approach to overcome the cautiousness of System P and the problems encountered by the rational closure inference. This approach takes advantage of (contextual) independence assumptions of the form: the fact that is true (or is false) does not affect the validity of the rule normally if then . The modelling of such independence assumptions is discussed in the possibilistic framework. Moreover, we show that when a counter-intuitive conclusion of a set of defaults can be inferred, it is always possible to repair the set of defaults by adding suitable information so as to produce the desired conclusions and block unsuitable ones.     

The Possibilistic Handling of Irrelevance in Exception-Tolerant Reasoning

In nonmonotonic reasoning, the preferential system P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of irrelevant properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious. These two types of inference can be represented using a possibility theory-based semantics. To overcome the cautiousness of system P, we first progressively augment preferential inference with two extensions which are in between system P and rational closure. Then, in order to overcome some remaining limitations of rational closure the second half of this paper focuses more particularly on the use of (contextual) independence assumptions of the form: the fact that is true (or is false) does not affect the validity of the rule normally if then . The modelling of such independence assumptions is discussed in the possibilistic framework. Algorithms are provided to jointly handle default rules and independence relations, and to check their multual consistency.     

Possibilistic Merging and Distance-Based Fusion of Propositional Information

The problem of merging multiple sources information is central in many information processing areas such as databases integrating problems, multiple criteria decision making, expert opinion pooling, etc. Recently, several approaches have been proposed to merge propositional bases, or sets of (non-prioritized) goals. These approaches are in general semantically defined. Like in belief revision, they use implicit priorities, generally based on Dalal's distance, for merging the propositional bases and return a new propositional base as a result. An immediate consequence of the generation of a propositional base is the impossibility of decomposing and iterating the fusion process in a coherent way with respect to priorities since the underlying ordering is lost. This paper presents a general approach for fusing prioritized bases, both semantically and syntactically, when priorities are represented in the possibilistic logic framework. Different classes of merging operators are considered depending on whether the sources are consistent, conflicting, redundant or independent. We show that the approaches which have been recently proposed for merging propositional bases can be embedded in this setting. The result is then a prioritized base, and hence the process can be coherently decomposed and iterated. Moreover, this encoding provides a syntactic counterpart for the fusion of propositional bases.     

Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty

In classical Constraint Satisfaction Problems (CSPs) knowledge is embedded in a set of hard constraints, each one restricting the possible values of a set of variables. However constraints in real world problems are seldom hard, and CSP's are often idealizations that do not account for the preference among feasible solutions. Moreover some constraints may have priority over others. Lastly, constraints may involve uncertain parameters. This paper advocates the use of fuzzy sets and possibility theory as a realistic approach for the representation of these three aspects. Fuzzy constraints encompass both preference relations among possible instantiations and priorities among constraints. In a Fuzzy Constraint Satisfaction Problem (FCSP), a constraint is satisfied to a degree (rather than satisfied or not satisfied) and the acceptability of a potential solution becomes a gradual notion. Even if the FCSP is partially inconsistent, best instantiations are provided owing to the relaxation of some constraints. Fuzzy constraints are thus flexible. CSP notions of consistency and k-consistency can be extended to this framework and the classical algorithms used in CSP resolution (e.g., tree search and filtering) can be adapted without losing much of their efficiency. Most classical theoretical results remain applicable to FCSPs. In the paper, various types of constraints are modelled in the same framework. The handling of uncertain parameters is carried out in the same setting because possibility theory can account for both preference and uncertainty. The presence of uncertain parameters leads to ill-defined CSPs, where the set of constraints which defines the problem is not precisely known.     

Syntax and Semantics for a Fuzzy Temporal Constraint Logic

In this paper we establish the relationship between the syntax and semantics of a fuzzy temporal constraint logic (FTCL) proposed by Cárdenas et al. FTCL enables us to express interrelated events by means of fuzzy temporal constraints. Moreover, it provides a resolution principle for performing inferences which take these constraints into account. FTCL is compatible with the theoretical temporal reasoning model proposed by Marín et al. – the Fuzzy Temporal Constraint Networks (FTCN). The main contributions of this paper are, on the one hand, the proofs of the FTCL-deduction and the FTCL-refutation theorems, and, on the other, the proof of the soundness of the refutation by resolution in this formal system, together with an exhaustive study of its completeness.     

广义可能性互模拟及其逻辑刻画

首先,给出了基于广义可能性测度的计算树逻辑的扩展GPoCTL*、计算树逻辑的约简GPoCTL-以及带回报的计算树逻辑GPoRCTL的语构和语义。在经典互模拟和广义可能性测度的基础上讨论了广义可能性互模拟及其相关性质。最后证明了GPoCTL、GPoCTL*和GPoCTL-公式与互模拟状态之间的等价关系。     

Towards a Logic of Perishable Propositions

Reasoning with uncertain information is a central issue for Artificial Intelligence and Information Systems. Consequently, a vast amount of studies and results devoted to this issue can be found in the literature.Curiously, reasoning with information whose uncertaintyvaries along time cannot be found so much in the literature. Dynamic reliability is a feature found rather frequently in many problems, e.g. in financial markets, meteorology and demographics.In this article we consider propositions whose information about truth evaluation is gradually lost with time. Our motivation has come from the information system under development within the project SIDAM—Distributed Information Systems for Mobile Agents (supported by FAPESP, grant 98/06138-2)—to provide citizens with information about urban automotive traffic in a large city.We propose functions of loss of information, and show how they can be used to characterize the obsolescence of propositional information in a logical system.     

基于可能性测度的计算树逻辑

首先,提出了可能的Kripke结构的定义,建立了可能的Kripke结构的可能性测度空间,并分析了可能的Kripke结构的一系列性质,即任一路径转移的可能性可由其初始状态的可能性分布与各转移的可能性取下确界而得到;依据可能的Kripke结构所定义的可能性测度具有其合理性等等。其次,给出了可能性计算树逻辑(PoCTL)的概念,讨论了两个PoCTL状态公式以及PoCTL与经典计算树逻辑(CTL)公式的等价性。最后,证明了PoCTL公式有与CTL*公式中\"一致性\"相对应的公式。     

可能性理论与不相容知识处理

Ｄ．Ｄｕｂｏｉｓ和Ｈ．Ｐｒａｄｅ提出的可能性逻辑是一种基于可能性理论的非经典逻辑，主要和于不确定证据推理。可能性逻辑不同于模糊逻辑，因为模糊逻辑处理非布尔公式，其命题中包模糊谓词，而可能性逻辑处理布尔公式，其中只包含经典命题的和谓词。本文尝试在可能性理论的框架下进行不相容知识库的维护和问题求解。这里的知识表示是基于可能性逻辑的。为此，我们提出了两种不同的方法：第一种方法在计算命题可信度时，要考虑所     

Belief, Logic, and Partial Truth

Contrary to some interpretations of "impossibility theorems," belief models exist which are both truth-functional and give equal credibility to all equivalent formulas. This combination of features can be useful, e.g., in case-based reasoning. That such models exist casts doubt on theories which try to restrict the applications of belief calculi based upon the supposed incompatibility of the features. One prominent theory attempts to divorce partial truth, described as the province of fuzzy logic, from probabilistic reasoning. Nevertheless, ordinary logic and cumulative probability exactly restate the inferences of the usual fuzzy logic.     

Towards a Hybrid Dynamic Logic for Hybrid Dynamic Systems

We introduce a hybrid variant of a dynamic logic with continuous state transitions along differential equations, and we present a sequent calculus for this extended hybrid dynamic logic. With the addition of satisfaction operators, this hybrid logic provides improved system introspection by referring to properties of states during system evolution. In addition to this, our calculus introduces state-based reasoning as a paradigm for delaying expansion of transitions using nominals as symbolic state labels. With these extensions, our hybrid dynamic logic advances the capabilities for compositional reasoning about (semialgebraic) hybrid dynamic systems. Moreover, the constructive reasoning support for goal-oriented analytic verification of hybrid dynamic systems carries over from the base calculus to our extended calculus.     

RELATIONSHIP BETWEEN TRUE AND ESTIMATED POSSIBILISTIC SYSTEMS AND THEIR RECONSTRUCTIONS†

This paper is a theoretical contribution to reconstructability analysis of possibilistic systems. A method to estimate a given possibility distribution from the associated observations is derived based on the one-to-one correspondence between possibility distributions and their basic probability assignments. It is shown that in this estimation the possibility value for a state is proportional to the frequency of the state in the observations which are drawn from nested state subsets. The order preservation relationship between a given (true) possibility distribution and its estimation is derived. Based on this preservation property, it is shown that the order in the distance from an original possibilistic overall system of their unbiased reconstructions from two alternative reconstruction hypotheses (structures) is preserved in the estimated systems domain. Particularly, it is proved that systems conceptualized in terms of possibility theory possess an important property: if a possibilistic system is perfectly reconstructable from a specific reconstruction hypothesis, then a system estimated from any data produced by the former system is also perfectly reconstructable from the same hypothesis.     

Extension of Petri Nets for Representing and Reasoning with Tasks with Imprecise Durations

This paper presents an extension of Petri net framework with imprecise temporal properties. We use possibility theory to represent imprecise time by time-stamping tokens and assigning durations to firing of the transitions. A method for approximation of an arbitrary temporal distribution with a set of possibilistic intervals is used to introduce the composition operation for two possibilistic temporal distributions. We developed a method to determining an effective enabling time of a transition with incoming tokens with possibilistic distributions. The utility of the proposed theory is illustrated using an example of an automated manufacturing system. The proposed approach is novel and has a broad utility beyond a timed Petri network and its applications.     

随机时序逻辑的模糊时间扩展方法

基于随机时序逻辑(SQTL),通过扩展模糊时间来表达系统的模糊时间关系,并实现一种表达能力更强的时序逻辑——模糊随机时序逻辑(FSQTL)。FSQTL能够建模实时系统中的确定时间、概率时间、随机时间和模糊时间,并利用可能性实现对性能需求的分析。     

基于多值方法的模糊逻辑函数最小化

首先提出了模糊逻辑和多值逻辑的相似性,并从开关信号理论出发建立了三值逻辑函数阈运算和模糊逻辑函数文字运算的对应关系,进而提出了基于差动电流开关理论的三值逻辑函数化简法求模糊逻辑函数最小化表达式的算法,并用该算法对几个模糊逻辑函数实例进行了化简,实例操作表明,该算法具有操作简单快捷的特点,是获得模糊逻辑函数最小化表达式的一种有效的方法。     

面向可能性数据库的异构双极信息查询策略研究

在日常交流中,人们常常会对同一事物同时使用正面的描述和负面的描述来表达其愿望和不满,由于不要求正、负面的描述必须相互对称,此类信息因而被称为异构双极(Heterogeneous bipolarity)信息.传统信息系统中的模糊查询方法,不能很好地处理用户查询需求中所含有的异构双极信息.本文基于可能性数据库,在限定的条件下,以在模糊查询选择操作的基本查询条件中,能够处理异构双极信息为目标,将Vague集用于异构双极信息的建模,并给出了在基本查询条件中含有异构双极信息的情况下,查询结果相关可能性测度和必要性测度的计算公式,同时还通过实例讨论了该方法的语义、特点及其与基于可能性理论方法的一致性.     

模型转换的重写逻辑构架研究

规则式的模型转换技术在模型驱动构架的模型转换实施中占有重要地位,但目前诸实施对于转换规则的定义存在多种解释、转换的协调方面、终止性和一致性等数学属性缺乏支持。该文提出一种Maude重写逻辑基础的构架(RLBA)以实施模型转换,通过产生式规范、多方法风格的重写规则集设计、OC(对象配置)和OM(对象消息)重写规则分类等技术并结合模型检查工具,为自动产生元模型和模型的面向对象可执行代数规范、转换规则的严格形式化定义、转换协调方面的刻画、终止性和一致性等的验证提供支持。     

Knowledge-Driven versus Data-Driven Logics

The starting point of this work is the gap between two distinct traditions in information engineering: knowledge representation and data-driven modelling. The first tradition emphasizes logic as a tool for representing beliefs held by an agent. The second tradition claims that the main source of knowledge is made of observed data, and generally does not use logic as a modelling tool. However, the emergence of fuzzy logic has blurred the boundaries between these two traditions by putting forward fuzzy rules as a Janus-faced tool that may represent knowledge, as well as approximate non-linear functions representing data. This paper lays bare logical foundations of data-driven reasoning whereby a set of formulas is understood as a set of observed facts rather than a set of beliefs. Several representation frameworks are considered from this point of view: classical logic, possibility theory, belief functions, epistemic logic, fuzzy rule-based systems. Mamdani's fuzzy rules are recovered as belonging to the data-driven view. In possibility theory a third set-function, different from possibility and necessity plays a key role in the data-driven view, and corresponds to a particular modality in epistemic logic. A bi-modal logic system is presented which handles both beliefs and observations, and for which a completeness theorem is given. Lastly, our results may shed new light in deontic logic and allow for a distinction between explicit and implicit permission that standard deontic modal logics do not often emphasize.