-Resolution principle based on lattice-valued propositional logic LP(X)

In the present paper, resolution-based automated reasoning theory in an L-type fuzzy logic is focused. Concretely, the -resolution principle, which is based on lattice-valued propositional logic LP(X) with truth-value in a logical algebra – lattice implication algebra, is investigated. Finally, an -resolution principle that can be used to judge if a lattice-valued logical formula in LP(X) is always false at a truth-valued level (i.e., -false), is established, and the theorems of both soundness and completeness of this -resolution principle are also proved. This will become the theoretical foundation for automated reasoning based on lattice-valued logical LP(X).     

Transfinite Semantics in the Form of Greatest Fixpoint

Transfinite semantics is a semantics according to which program executions can continue working after an infinite number of steps. Such a view of programs can be useful in the theory of program transformations.So far, transfinite semantics have been succesfully defined for iterative loops. This paper provides an exhaustive definition for semantics that enable also infinitely deep recursion.The definition is actually a parametric schema that defines a family of different transfinite semantics. As standard semantics also match the same schema, our framework describes both standard and transfinite semantics in a uniform way.All semantics are expressed as greatest fixpoints of monotone operators on some complete lattices. It turns out that, for transfinite semantics, the corresponding lattice operators are cocontinuous. According to Kleene’s theorem, this shows that transfinite semantics can be expressed as a limit of iteration which is not transfinite.     

Some results of fuzzy BCK-filters

Let X be a bounded BCK-algebra and f a fuzzy set in X. If a fuzzy BCK-filter μ in X satisfies that (i) fμ, (ii) for any fuzzy BCK-filter ν in X, fν implies μν, then μ is said to be generated by f and denote μ by [f) for short. In the present paper, we give a procedure to construct the [f) by f. As applications of this result we prove that the set of all fuzzy BCK-filters in a bounded BCK-algebra forms a complete and infinitely distributive lattice.     

Existence and uniqueness of unmixed solutions of the discrete-time algebraic Riccati equation

A solution X of a discrete-time algebraic Riccati equation is called unmixed if the corresponding closed-loop matrix Φ(X) has the property that the common roots of det(sI−Φ(X)) and det(I−sΦ(X)^*) (if any) are on the unit circle. A necessary and sufficient condition is given for existence and uniqueness of an unmixed solution such that the eigenvalues of Φ(X) lie in a prescribed subset of .     

A compact fixpoint semantics for term rewriting systems

This work is motivated by the fact that a “compact” semantics for term rewriting systems, which is essential for the development of effective semantics-based program manipulation tools (e.g. automatic program analyzers and debuggers), does not exist. The big-step rewriting semantics that is most commonly considered in functional programming is the set of values/normal forms that the program is able to compute for any input expression. Such a big-step semantics is unnecessarily oversized, as it contains many “semantically useless” elements that can be retrieved from a smaller set of terms. Therefore, in this article, we present a compressed, goal-independent collecting fixpoint semantics that contains the smallest set of terms that are sufficient to describe, by semantic closure, all possible rewritings. We prove soundness and completeness under ascertained conditions. The compactness of the semantics makes it suitable for applications. Actually, our semantics can be finite whereas the big-step semantics is generally not, and even when both semantics are infinite, the fixpoint computation of our semantics produces fewer elements at each step. To support this claim we report several experiments performed with a prototypical implementation.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

多Agent信念逻辑及其在概率意义下的推广

首先建立了一种多Agent信念逻辑MBL(multi-agentbelieflogic),在经典信念逻辑基础上增加了普遍信念算子和公共信念算子,给出MBL的Kripke语义与广义Aumann语义,讨论了两者的等价性,证明了MBL对于上述两种语义的可靠性和完备性.其次,建立了一种多Agent概率信念逻辑MPBL(multi-agentprobabilisticbelieflogic),通过在广义Aumann语义基础上引入概率空间,给出了MPBL的概率Aumann语义,证明了它的可靠性,并给出MPBL的一些推论.     

Infinite trees and completely iterative theories: a coalgebraic view

Infinite trees form a free completely iterative theory over any given signature—this fact, proved by Elgot, Bloom and Tindell, turns out to be a special case of a much more general categorical result exhibited in the present paper. We prove that whenever an endofunctor H of a category has final coalgebras for all functors H( _ )+X, then those coalgebras, TX, form a monad. This monad is completely iterative, i.e., every guarded system of recursive equations has a unique solution. And it is a free completely iterative monad on H. The special case of polynomial endofunctors of the category is the above mentioned theory, or monad, of infinite trees.

This procedure can be generalized to monoidal categories satisfying a mild side condition: if, for an object H, the endofunctor H_+I has a final coalgebra, T, then T is a monoid. This specializes to the above case for the monoidal category of all endofunctors.     

Constrained string editing

Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion, and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transforming X to Y using any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm is presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithm requires O(¦X¦ ¦ Y¦min(¦ X¦,¦ Y¦)) time and space. The technique to compute the optimal transformation is also presented.     

基于OE-概念格的形式背景属性约简

在三支概念格的属性约简框架下,借助布尔矩阵理论,研究保持OE-对象粒矩阵不变的属性约简问题。给出OE-对象粒矩阵的概念以及OEG粒协调集的定义,在此基础之上讨论属性之间的相似性,并且刻画属性的内外重要度。针对对象导出三支概念格的形式背景设计基于矩阵理论的启发式属性约简算法。将上述理论结果应用于对象导出三支概念格的决策形式背景,提出三支协调决策形式背景及OEG粒协调集的概念,并且从规则提取的角度说明约简集对应的OE-概念格的决策形式背景的三支规则集比原背景的三支规则集更加简洁。通过数值实验阐明该理论的可行性和合理性。