Methods of solution and criteria of consistency of systems of linear diophantine equations over the set of natural numbers1

Some methods and algorithms of solution of systems of linear Diophantine equations over the naturals are briefly reviewed. Criteria and an incremental algorithm of efficient solution of the problem of consistency for a system of linear Diophantine equations and inequalities over the naturals are given. This research was supported under grant INTAS-RFBR 95-0095. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 12–36, July–August, 1999.     

Duality for programs involving non-separable objective functions

Mathematical programs involving non-separable objective functions arise in a variety of situations. In this paper we construct a duality theory for such functions using the notions of conjugate functions. Depending on the structure of the constraint set, different duals are possible. A particular case is analysed in detail, leading to an analytic solution. A numerical example is given.     

Notions ensemblistes et besoins d’apprentissage dans la transition secondaire-supérieur

Abstract

In set theory, functions present specific conceptual and semiotic properties. In this article, relying on constructs from the anthropological theory of didactics, we analyze the evolution of institutional relationships to set theory functional notions in the transition from high school to university in Tunisia, and the way some characteristics of this evolution can explain the observed difficulties met by successful high school students in the solving of problems involving functions in linear algebra at university.     

A review of: “ANTICIPATORY SYSTEMS”, by Robert Rosen,Pergamon Press,Oxford, 1985, X + 436pp.

In rough set theory there exists a pair of approximation operators, the upper and lower approximations, whereas in Dempster-Shafer theory of evidence there exists a dual pair of uncertainty measures, the plausibility and belief functions. It seems that there is some kind of natural connection between the two theories. The purpose of this paper is to establish the relationship between rough set theory and Dempster-Shafer theory of evidence. Various generalizations of the Dempster-Shafer belief structure and their induced uncertainty measures, the plausibility and belief functions, are first reviewed and examined. Generalizations of Pawlak approximation space and their induced approximation operators, the upper and lower approximations, are then summarized. Concepts of random rough sets, which include the mechanisms of numeric and non-numeric aspects of uncertain knowledge, are then proposed. Notions of the Dempster-Shafer theory of evidence within the framework of rough set theory are subsequently formed and interpreted. It is demonstrated that various belief structures are associated with various rough approximation spaces such that different dual pairs of upper and lower approximation operators induced by the rough approximation spaces may be used to interpret the corresponding dual pairs of plausibility and belief functions induced by the belief structures.     

A Fast Method for Finding the Basis of Non-negative Solutions to a Linear Diophantine Equation

We present a complete characterization of the set of minimal solutions of a single linear Diophantine equation in three unknowns over the natural numbers. This characterization, for which we give a geometric interpretation, is based on well-known properties of congruences and we use it as the foundation of direct algorithms for solving this particular kind of equation. These direct algorithms and an enumeration procedure are then put together to build an algorithm for solving the general case of a Diophantine equation over the naturals. We also put forth a statistical method for comparing algorithms for solving Diophantine equations which is more sound than comparisons based on times observed for small sets of equations. From an extensive comparison with algorithms described by other authors it becomes clear that our algorithm is the fastest known to date for a class of equations. Typically the equations in this class have a small number of unknowns in one side, the maximum value for their coefficients being greater than 3.     

Automata over continuous time

The principal objective of this paper is to lift basic concepts of the classical automata theory from discrete to continuous (real) time. It is argued that the set of finite memory retrospective functions is the set of functions realized by finite state devices. We show that the finite memory retrospective functions are speed-independent, i.e., they are invariant under ‘stretchings’ of the time axis. Therefore, such functions cannot deal with metrical aspects of the reals.

We classify and analyze phenomena which appear at continuous time and are invisible at discrete time.     

双论域的一般多粒度粗糙集

多粒度粗糙集是近几年来研究的热门课题之一。将多粒度粗糙集和双论域结合起来,首先定义了不同论域上的支撑函数;其次通过支撑函数建立了不同论域上的一般多粒度粗糙近似算子,研究了各个近似算子的性质。讨论了双论域的一般多粒度粗糙集的粗糙度和精确度;通过大学生选课这一实例验证了该模型的实用性和有效性。     

On the Lyapunov equation,coinvariant subspaces and some problems related to spectral factorizations

A geometric approach to stochastic realization theory, and hence to spectral factorization problems, has been developed by Lindquist and Picci (1985, 1991) and Lindquist et al. (1995). Most of this work was done abstractly. Fuhrmann and Gombani (1998) adopted an entirely Hardy space approach to this set of problems, studying the set of rectangular spectral factors of given size for a weakly coercive spectral function. The parametrization of spectral factors in terms of factorizations of related inner functions, as developed in Fuhrmann (1995), had to be generalized. This led to a further understanding of the partial order introduced by Lindquist and Picci in the set of stable spectral factors. In the present paper we study the geometry of finite dimensional coinvariant subspaces of a vectorial Hardy space H ₂ via realization theory, emphasizing the role of the Lyapunov equation in lifting the Hardy space metric to the statespace domain. We follow this by deriving state space formulas for rectangular spectral factors as well as for related inner functions arising in Fuhrmann and Gombani (1998). Finally, we develop a state space approach to the analysis of the partial order of the set of rectangular spectral factors of a given spectral function and its representation in terms of inner functions.     

基于粗糙集理论的属性约简算法的VB实现

粗糙集理论成为近年来数据挖掘领域的研究热点,基于粗糙集理论的属性约简算法具有重要的研究意义,开发一套用于研究粗糙集理论属性约简算法的软件将是有效的辅助工具。论文首先对粗糙集理论基本概念及属性约简问题进行介绍,接着介绍该软件的设计和结构功能,举例说明该软件的应用,并提出该软件有待进一步扩展的功能。     

The algebraic structures of generalized rough set theory

Rough set theory is an important technique for knowledge discovery in databases, and its algebraic structure is part of the foundation of rough set theory. In this paper, we present the structures of the lower and upper approximations based on arbitrary binary relations. Some existing results concerning the interpretation of belief functions in rough set backgrounds are also extended. Based on the concepts of definable sets in rough set theory, two important Boolean subalgebras in the generalized rough sets are investigated. An algorithm to compute atoms for these two Boolean algebras is presented.     

A note on grey level-intensity transformation: effect on HVS thresholding

An attempt is made in this note to investigate the effect on edge extraction when the theory of HVS (human visual system) based thresholding [1] is made to operate on the intensity domain of a grey tone image. A family of S and S⁻¹ functions is considered to take care of the grey level to intensity transformation. The performance of the systems is also quantitatively analysed using the measure ‘entropy’ of a fuzzy set.     

A Decision Procedure for a Sublanguage of Set Theory Involving Monotone, Additive, and Multiplicative Functions

MLSS is a decidable sublanguage of set theory involving the predicates membership, set equality, set inclusion, and the operators union, intersection, set difference, and singleton.In this paper we extend MLSS with constructs for expressing monotonicity, additivity, and multiplicativity properties of set-to-set functions. We prove that the resulting language is decidable by reducing the problem of determining the satisfiability of its sentences to the problem of determining the satisfiability of sentences of MLSS.     

无限论域中的粗糙近似空间与信任结构

在粗糙集理论中存在一对近似算子:下近似算子和上近似算子.而在Dempser-Shafer证据理论中有一对对偶的不确定性测度:信任函数与似然函数.集合的下近似和上近似可以看成是对该集合所表示信息的定性描述,而同一集合的信任测度和似然测度可以看成是对该集合的不确定性的定量刻画.针对各种复杂系统中不确定性知识的表示问题,介绍了无限论域中经典和模糊环境下信任结构及其导出的信任函数与似然函数的概念,建立了Dempser-Shafer证据理论中信任函数与似然函数和粗糙集理论中下近似与上近似之间的关系.阐述了由近似空间导出的下近似和上近似的概率生成一对对偶的信任函数和似然函数;反之,对于任何一个信任结构及其生成的信任函数与似然函数,必可以找到一个概率近似空间,使得由近似空间导出的下近似和上近似的概率分别恰好就是所给的信任函数和似然函数.最后,指出了主要理论成果在智能信息系统的知识表示和知识获取方面的潜在应用.     

Coverage and invariability by structural functions

Based on some of the results and definitions provided in the article System linkage: Structural functions and hierarchies (Lloret et al. “System linkage: structural functions and hierarchies”, Cybern. Syst. Int. J., 29, pp. 35–46, 1998) and adding new definitions that are in keeping with the spirit of the same article, new results have been obtained that explore the utility of the structural input–output function (also transferable to the other structural functions) and that expand on studies conducted to date on variables (cells).

Our approach is based principally on the application of graph theory to the study of relationships between variables (cells) using specific set theory concepts, introducing new definitions and adapting continuous function properties to our discrete environment. More specifically, we present two new concepts—coverage between sets and the invariant set—analysing their inter-relatedness from the perspective of structural functions, i.e. from the point of view of influences in the system. To date these concepts have been handled from a continuous point of view, and so the discrete approach described here will lay the foundations for new developments in this direction.

Although the development of the concepts may, a priori, appear to very theoretical, they are, in fact, much more practical than would appear to be the case. A result such as the fact that A covers B, for example, can be interpreted in terms of the latter set being formed of direct influences from elements in the former set in relation to one or more than one relationships. Analogously, the invariant set concept may be interpreted as the set maintaining its structure and status, remaining constant with respect to any possible relationships.     

Set-based extended aggregation functions

Inspired by the Zadeh approach to fuzzy connectives in fuzzy set theory and by some applications, we introduce and study set-based extended functions, and in particular, set-based extended aggregation functions. These functions reflect neither reordering nor repetition of input values, and, linking different arities, they introduce serious constraints for extended functions. A complete characterization of set-based extended (aggregation) functions is given, and some constructions of such functions are also proposed, including several examples.     

DEMORS: A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems

The aim of this paper is to show how the hybridization of a multi-objective evolutionary algorithm (MOEA) and a local search method based on the use of rough set theory is a viable alternative to obtain a robust algorithm able to solve difficult constrained multi-objective optimization problems at a moderate computational cost. This paper extends a previously published MOEA [Hernández-Díaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective optimization using differential evolution and rough set theory. In: 2006 genetic and evolutionary computation conference (GECCO’2006). Seattle, Washington, USA: ACM Press; July 2006], which was limited to unconstrained multi-objective optimization problems. Here, the main idea is to use this sort of hybrid approach to approximate the Pareto front of a constrained multi-objective optimization problem while performing a relatively low number of fitness function evaluations. Since in real-world problems the cost of evaluating the objective functions is the most significant, our underlying assumption is that, by aiming to minimize the number of such evaluations, our MOEA can be considered efficient. As in its previous version, our hybrid approach operates in two stages: in the first one, a multi-objective version of differential evolution is used to generate an initial approximation of the Pareto front. Then, in the second stage, rough set theory is used to improve the spread and quality of this initial approximation. To assess the performance of our proposed approach, we adopt, on the one hand, a set of standard bi-objective constrained test problems and, on the other hand, a large real-world problem with eight objective functions and 160 decision variables. The first set of problems are solved performing 10,000 fitness function evaluations, which is a competitive value compared to the number of evaluations previously reported in the specialized literature for such problems. The real-world problem is solved performing 250,000 fitness function evaluations, mainly because of its high dimensionality. Our results are compared with respect to those generated by NSGA-II, which is a MOEA representative of the state-of-the-art in the area.     

Mining fuzzy β-certain and β-possible rules from quantitative data based on the variable precision rough-set model

The rough-set theory proposed by Pawlak, has been widely used in dealing with data classification problems. The original rough-set model is, however, quite sensitive to noisy data. Ziarko thus proposed the variable precision rough-set model to deal with noisy data and uncertain information. This model allowed for some degree of uncertainty and misclassification in the mining process. Conventionally, the mining algorithms based on the rough-set theory identify the relationships among data using crisp attribute values; however, data with quantitative values are commonly seen in real-world applications. This paper thus deals with the problem of producing a set of fuzzy certain and fuzzy possible rules from quantitative data with a predefined tolerance degree of uncertainty and misclassification. A new method, which combines the variable precision rough-set model and the fuzzy set theory, is thus proposed to solve this problem. It first transforms each quantitative value into a fuzzy set of linguistic terms using membership functions and then calculates the fuzzy β-lower and the fuzzy β-upper approximations. The certain and possible rules are then generated based on these fuzzy approximations. These rules can then be used to classify unknown objects. The paper thus extends the existing rough-set mining approaches to process quantitative data with tolerance of noise and uncertainty.     

On the axiomatic justification of Dempster's rule of combination

Within the theory of belief functions Dempster's rule of combination is of particular importance for the integration of different bodies of evidence. In this article a set of axioms is presented that uniquely determines this rule. As the axioms reflect just the intuitive idea of partially moveable evidence masses the presented results emphasize the unicity of Dempster's rule. © 1992 John Wiley & Sons. Inc.