Search

The present paper investigates approximation spaces in the context of mathematical structures which axiomatise the notion of nearness. Starting with the framework of information quanta which distinguishes two levels of information structures, namely property systems (the first level) and information quantum relational systems (the second level), we shall introduce the notion of Pawlak property system. These systems correspond bijectively to finite approximation spaces, i.e. their respective information quantum relational systems. Then we characterise Pawlak property systems in terms of symmetric topological spaces. In the second part of the paper, these systems are defined by means of topological structures based on the concept of nearness. We prove that the category of Pawlak property systems is isomorphic to the category of finite topological nearness spaces and provide its additional topological characterisation. [ABSTRACT FROM AUTHOR]

We study the transformation of "predicate introduction" in non-monotonic logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In this paper, we study predicate introduction in the algebraic framework of "approximation theory"; this is a fixpoint theory for nonmonotone operators that generalizes all main semantics of various non-monotonic logics, including logic programming, default logic and autoepistemic logic. We prove an abstract, algebraic equivalence result in this framework. This can then be used to show that, in logic programming, certain transformations are equivalence preserving under, among others, both the stable and well-founded semantics. Based on this result, we develop a general method of eliminating universal quantifiers in the bodies of rules. Our work is, however, also applicable beyond logic programming. In a companion paper, we demonstrate this, by using the same algebraic results to derive a transformation which reduces the nesting depth of the modal operator K in autoepistemic logic. [ABSTRACT FROM AUTHOR]

This paper considers the problem of how to establish calculi of approximation spaces. Approximation spaces considered in the context of rough sets were introduced by Zdzisław Pawlak more than two decades ago. In general, a calculus of approximation spaces is a system for combining, describing, measuring, reasoning about, and performing operations on approximation spaces. An approach to achieving a calculus of approximation spaces that provides a basis for approximating reasoning in distributed systems of cooperating agents is considered in this paper. Examples of basic concepts are given throughout this paper to illustrate how approximation spaces can be beneficially used in many settings, in particular for complex concept approximation. The contribution of this paper is the presentation of a framework for calculi of approximation spaces useful for approximate reasoning by cooperating agents. [ABSTRACT FROM AUTHOR]

In this paper, we propose the notion of precise sets in texture spaces. Precise sets are defined by using textural sections and presections under a direlation. We obtain some properties of definability; it is proved that the family of precise sets under reflexive and transitive direlation is an Alexandroff ditopology. It is observed that sections and presections, which are approximation operators in the textural meaning, are Galois connections. Finally, effective results are given for definability by using textural precise sets. [ABSTRACT FROM AUTHOR]

In this paper, we show that approximation spaces are basic structures for knowledge discovery from multi-relational data. The utility of approximation spaces as fundamental objects constructed for concept approximation is emphasized. Examples of basic concepts are given throughout this paper to illustrate how approximation spaces can be beneficially used in many settings. [ABSTRACT FROM AUTHOR]

We study the transformation of "predicate introduction" in non-monotonic logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In a companion paper, we developed an algebraic theory that considers predicate introduction within the framework of "approximation theory", a fixpoint theory for non-monotone operators that generalizes all main semantics of various non-monotonic logics, including logic programming, default logic and autoepistemic logic. We then used these results to show that certain logic programming transformations are equivalence preserving under, among others, both the stable and well-founded semantics. In this paper, we now apply the same algebraic results to autoepistemic logic and prove that a transformation to reduce the nesting depth of modal operators is equivalence preserving under a family of semantics for this logic. This not only provides useful theorems for autoepistemic logic, but also demonstrates that our algebraic theory does indeed capture the essence of predicate introduction in a generally applicable way. [ABSTRACT FROM AUTHOR]

Rough rule extraction refers to the rule induction method by using rough set theory. Although rough set theory is a powerful mathematical tool in dealing with vagueness and uncertainty in data sets, it is lack of effective rule extracting approach under complex conditions. This paper proposes several algorithms to perform rough rule extraction from data sets with different properties. Firstly, in order to obtain uncertainty rules from inconsistent data, we introduce the concept of confidence factor into the rule extracting process. Then, an improved incremental rule extracting algorithm is proposed based on the analysis of the incremental data categories. Finally, above algorithms are further extended to perform approximate rule extraction from huge data sets. Preliminary experiment results are encouraging. [ABSTRACT FROM AUTHOR]

The problem considered in this paper is the extension of an approximation space to include a nearness relation. Approximation spaces were introduced by Zdzis?aw Pawlak during the early 1980s as frameworks for classifying objects by means of attributes. Pawlak introduced approximations as a means of approximating one set of objects with another set of objects using an indiscernibility relation that is based on a comparison between the feature values of objects. Until now, the focus has been on the overlap between sets. It is possible to introduce a nearness relation that can be used to determine the "nearness" of sets of objects that are possibly disjoint and, yet, qualitatively near to each other. Several members of a family of nearness relations are introduced in this article. The contribution of this article is the introduction of a nearness relation that makes it possible to extend Pawlak's model for an approximation space and to consider the extension of generalized approximations spaces. [ABSTRACT FROM AUTHOR]

This paper focuses on approximate reasoning based on the use of similarity spaces. Similarity spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak [17, 18]. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logic which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between approximate relations, similarity spaces and three-valued logics. Using ideas from correspondence theory for modal logics and constraints on an accessibility relation, we develop an analogous framework for three-valued logics and constraints on similarity relations. In this manner, we can provide a tool which helps in determining the proper three-valued logical reasoning engine to use for different classes of approximate relations generated via specific types of similarity spaces. Additionally, by choosing a three-valued logic first, the framework determines what constraints would be required on a similarity relation and the approximate relations induced by it. Such information would guide the generation of approximate relations for specific applications. [ABSTRACT FROM AUTHOR]

Approximation Spaces were introduced in order to analyse data on the basis of Indiscernibility Spaces, that is, spaces of the form , where U is a universe of items and E is an equivalence relation on U. Various authors suggested to consider spaces of the form , where R is any binary relation. This paper aims at introducing a further step consisting in taking into account spaces of the form i}i∈l>, where {Ri}i∈l is a family of binary relations, that we call "Dynamic Spaces" because by means of this generalisation we can account for different forms of dynamics. While Indiscernibility Spaces induce 0-dimensional topological spaces (Approximation Spaces), Dynamic Spaces induce various types of pre-topological spaces. [ABSTRACT FROM AUTHOR]

We advocate the thesis that the following general statements are equivalent: the existence of an optimal proof system, the existence of an optimal acceptor (an algorithm with optimality property stated only for input strings which are accepted), and the existence of a suitable recursive presentation of the class of all easy (polynomial-time recognizable) subsets of TAUT (SAT). We prove three concrete versions of this thesis with different variants of notions appearing in it. These versions give alternative characterizations of the following problems: the existence of a p-optimal proof system for SAT, the existence of an optimal proof system for TAUT, and the existence of an optimal and automatizable proof system for TAUT. [ABSTRACT FROM AUTHOR]

The concept of approximation is one of the most fundamental in rough set theory. In this work we examine this basic notion as well as its extensions and modifications. The goal is to construct a parameterized approximation mechanism making it possible to develop multi-stage multi-level concept hierarchies that are capable of maintaining acceptable level of imprecision from input to output. [ABSTRACT FROM AUTHOR]

The undecidability of the additive theory of prime numbers (with identity) as well as the theory Th(N, +, n ↦ p_n), where pn denotes the (n + 1)-th prime, are open questions. In a first part, we show the undecidability of Th(N, +, n ↦ nf(n)) where f is a good approximation of the enumeration n ↦ p_n/n. In a second part, as a possible approach, we extend the former theory by adding some extra function. In this direction we show the undecidability of the existential part of the theory Th(N, +, n ↦ p_n, n ↦ r_n), where r_n is the remainder of pn divided by n in the euclidian division. L'indécidabilité de la théorie additive des nombres premiers ainsi que de la théorie Th(N, +, n ↦ p_n), où p_n désigne le (n+1)-ième premier, sont deux questions ouvertes. Dans une première partie, nous montrons l'indécidabilité de Th(N, +, n ↦ nf(n)) où f est une bonne approximation de la fonction n ↦ p_n/n des nombres premiers. Dans une seconde partie, nous étendons la première théorie en lui ajoutant une fonction supplémentaire et nous montrons l'indécidabilité de la théorie Th(N, +, n ↦ p_n, n ↦ r_n), où r_n désigne le reste de p_n dans la division euclidienne de p_n par n, et même de sa seule partie existentielle. [ABSTRACT FROM AUTHOR]

We investigate patterns over information maps. Such patterns can represent information changes (e.g., in time or space) across information maps. Any map is defined by some transition relation on states. Each state is a pair consisting of a label and information related to the label. Introduced concepts are illustrated by examples. We also discuss searching problems for relevant patterns extracted from data stored in information maps. Some patterns can be expressed by temporal formulas. Then, searching is reduced to searching for relevant temporal formulas. We generalise association rules over information systems to association roles over information maps. Approximate reasoning methods based on information changes are important for many applications (e.g., related to spatio-temporal reasoning). We introduce basic concepts for approximate reasoning about information changes across information maps. We measure degree of changes using information granules. Any role for reasoning about information changes specifies how changes of information granules from the rule premise influence changes of information granules from the rule conclusion. Changes in information granules can be measured, e.g., using expressions analogous to derivatives. Illustrative examples are also presented. [ABSTRACT FROM AUTHOR]

Classification systems working on large feature spaces, despite extensive learning, often perform poorly on a group of atypical samples. The problem can be dealt with by incorporating domain knowledge about samples being recognized into the learning process. We present a method that allows to perform this task using a rough approximation framework. We show how human expert's domain knowledge expressed in natural language can be approximately translated by a machine learning recognition system. We present in details how the method performs on a system recognizing handwritten digits from a large digit database. Our approach is an extension of ideas developed in the rough mereology theory. [ABSTRACT FROM AUTHOR]