An Efficient Algorithm to Generate Prime Implicants

In this paper, an efficient recursive algorithm is presented to compute the set of prime implicants of a propositional formula in conjunctive normal form (CNF). The propositional formula is represented as a (0,1)-matrix, and a set of 1's across its columns are termed as paths. The algorithm finds the prime implicants as the prime paths in the matrix using the divide-and-conquer technique. The algorithm is based on the principle that the prime implicant of a formula is the concatenation of the prime implicants of two of its subformulae. The set of prime paths containing a specific literal and devoid of a literal are characterized. Based on this characterization, the formula is recursively divided into subformulae to employ the divide-and-conquer paradigm. The prime paths of the subformulae are then concatenated to obtain the prime paths of the formula. In this process, the number of subsumption operations is reduced. It is also shown that the earlier algorithm based on prime paths has some avoidable computations that the proposed algorithm avoids. Besides being more efficient, the proposed algorithm has the additional advantage of being suitable for the incremental method, without recomputing prime paths for the updated formula. The subsumption operation is one of the crucial operations for any such algorithms, and it is shown that the number of subsumption operation is reduced in the proposed algorithm. Experimental results are presented to substantiate that the proposed algorithm is more efficient than the existing algorithms.     

Maximal prime subgraph decomposition of Bayesian networks

The authors present a method for decomposition of Bayesian networks into their maximal prime subgraphs. The correctness of the method is proven and results relating the maximal prime subgraph decomposition (MPD) to the maximal complete subgraphs of the moral graph of the original Bayesian network are presented. The maximal prime subgraphs of a Bayesian network can be organized as a tree which can be used as the computational structure for LAZY propagation. We also identify a number of tasks performed on Bayesian networks that can benefit from MPD. These tasks are: divide and conquer triangulation, hybrid propagation algorithms combining exact and approximative inference techniques, and incremental construction of junction trees. We compare the proposed algorithm with standard algorithms for decomposition of undirected graphs into their maximal prime subgraphs. The discussion shows that the proposed algorithm is simpler, more easy to comprehend, and it has the same complexity as the standard algorithms.     

Computing prime implicants via transversal clauses

In this paper, the notion of transversal clauses is introduced and subsequently a new algorithm for computing prime implicants is developed. Opposed to the common approach of computing prime implicants of a dnf, the proposed algorithm uses a cnf representation of a propositional formula. The same algorithm applied on a dnf representation yields the set of prime implicates of a formula. Besides its suitability for implementation in a parallel environment and as an incremental algorithm, it has been found to work faster in case, the number of prime implicants is large.     

A generalized prime-number-based matrix strategy for efficient iconic indexing of symbolic pictures

In this paper, we propose an efficient iconic indexing strategy called generalized prime-number-based matrix (GPN Matrix) for symbolic pictures, in which each spatial relationship between any two objects is represented as a product of some prime numbers from a set of 12 prime numbers and is recorded in a matrix. In the proposed strategy, we classify 169 spatial relationships between two objects in 2D space into five spatial categories, and define a generalized category rule (based on module operations) for each of those five spatial categories. As compared to the prime-number-based matrix (PN Matrix) strategy (Chang and Yang, 1997), in which each spatial relationship between any two objects is represented as a product of some prime numbers from a set of 17 prime numbers, the GPN Matrix strategy has a smaller storage space requirement than the PN Matrix strategy, which also improves the query processing time.     

Fuzzy radicals and prime fuzzy ideals of ordered semigroups

Let S be an ordered semigroup. A fuzzy subset of S is, by definition, an arbitrary mapping f: S → [0, 1], where [0, 1] is the usual interval of real numbers. Motivated by studying prime fuzzy ideals in rings, semigroups and ordered semigroups, and as a continuation of Kehayopulu and Tsingelis’s works in ordered semigroups in terms of fuzzy subsets, in this paper we introduce the notion of ordered fuzzy points of an ordered semigroup S, and give a characterization of prime fuzzy ideals of an ordered semigroup S. We also introduce the concepts of weakly prime fuzzy ideals, completely prime fuzzy ideals, completely semiprime fuzzy ideals and weakly completely prime fuzzy ideals of an ordered semigroup S, and establish the relationship between the five classes of ideals. Furthermore, we characterize weakly prime fuzzy ideals, completely semiprime fuzzy ideals and weakly completely prime fuzzy ideals of S by their level ideals. Finally, we introduce and investigate the fuzzy radicals of ordered semigroups by means of ordered fuzzy points, and prove that the fuzzy radical of every completely semiprime fuzzy ideal of an ordered semigroup S can be expressed as the intersection of all weakly completely prime fuzzy ideals containing it. As an application of the results of this paper, the corresponding results of semigroups (without order) are also obtained.     

An algorithm for constructing gröbner bases from characteristic sets and its application to geometry

In Ritt's method, a prime ideal is given by a characteristic set. A characteristic set of a prime ideal is generally not a set of generators of this ideal. In this paper we present a simple algorithm for constructing Gröbner bases of a prime ideal from its characteristic set. We give a method for finding new theorems in geometry as an application of this algorithm.     

Useless prime implicants of incompletely specified multiple-output switching functions

In the process of finding a minimal sum representation for an incompletely specified multiple-output switching function, there often occur certain types of prime implicants, referred to as useless, which can be discarded because of the presence of the don't-cares. This paper presents a correction to the definition of useless given by Tison and extends the definition to other notations. A procedure for removing useless prime implicants quickly is presented for the case when multiple-output prime implicants are derived from minterms. The deletion of useless prime implicants can, in many cases, speed up any procedure for finding a minimal sum that begins with the multiple-output prime implicants in both hand calculation and in computer implementation.This work was supported in part by the National Science Foundation under Grant No. MCS-77-09744.     

The Minimal Structure and Motion Problems with Missing Data for 1D Retina Vision

In this paper we investigate the structure and motion problem for calibrated one-dimensional projections of a two-dimensional environment. The theory of one-dimensional cameras are useful in several areas, e.g. within robotics, autonomous guided vehicles, projection of lines in ordinary vision and vision of vehicles undergoing so called planar motion. In a previous paper the structure and motion problem for all cases with non-missing data was classified and solved. Our aim is here to classify all structure and motion problems, even those with missing data, and to solve them. In the classification we introduce the notion of a prime problem. A prime problem is a minimal problem that does not contain a minimal problem as a sub-problem. We further show that there are infinitely many such prime problems. We give solutions to four prime problems, and using the duality of Carlsson these can be extended to solutions of seven prime problems. Finally we give some experimental results based on synthetic data.     

Prime Number Generation Based On Pocklington's Theorem

Public-key cryptosystems base their security on well-known number-theoretic problems, such as factorisation of a given number n . Hence, prime number generation is an absolute requirement. Many prime number generation techniques have been proposed up-to-date, which differ mainly in terms of complexity, certainty and speed. Pocklington's theorem, if implemented, can guarantee the generation of a true prime. The proposed implementation exhibits low complexity at the expense of long execution time.     

关于关系模式主属性判定的一种多项式算法

该文深入分析了主属性在关系模式中的结构特征,提出了化简独立复合环、独立简单环、化简双部属性函数依赖图等概念。在此基础上,给出了一个关系模式主属性判定的多项式算法。     

RSA密码分析中分解大整数的判定算法

RSA的安全性是依据大整数分解的困难性而设计的。在RSA的密码分析中,根据RSA公钥加密体制中的公开密钥n为2个大素数乘积的特性,针对形如n=pq(其中,p、q为大素数)的大整数n分解,提出一种分解n的判定算法,并对n的素因子特征与该算法的有效性关系进行分析。经过数学证明和相应算法设计证实,该算法的复杂度低于O(plogn)。     

An algorithm for constructing gr?bner bases from characteristic sets and its application to geometry

In Ritt's method, a prime ideal is given by a characteristic set. A characteristic set of a prime ideal is generally not a set of generators of this ideal. In this paper we present a simple algorithm for constructing Gröbner bases of a prime ideal from its characteristic set. We give a method for finding new theorems in geometry as an application of this algorithm.The first author was supported by NSF Grants Nos. DCR-8503498 and CCR-8702108. The computer facility was supported by the NSF/CER Grant at the University of Texas.     

Prime Decompositions of Radicals in Polynomial Rings

In this paper we are concerned with the computation of prime decompositions of radicals in polynomial rings over a noetherian commutative ring R with identity. We show that prime decomposition algorithms in R can be lifted to R[x] if for every prime ideal P in R univariate polynomials can be factored over the quotient field of the residue class ring R/P. In the proof of this result a lifting algorithm is constructed which can be considered as a generalization of the algorithm of Ritt and Wu.     

A method of finding simple disjunctive decomposition with one free variable

Simple disjunctive decomposition with one free variable can be obtained by using the prime implicants of the Boolean function. A function is decomposable with its redundant variable as a free variable. A necessary condition for decomposition with a non-redundant variable as free variable is that the number of minterms in an n variable function be 2^(n?1). A sufficient condition is that the variable remain present, in either true or complemented form, in all the prime implicants of the function.     

格的模糊滤子与模糊素滤子的度量

主要研究了模糊代数中格的模糊（素）滤子的度量。首先给出了模糊（素）滤子度的新概念,并利用模糊（素）滤子度讨论了格的模糊子集是模糊（素）滤子的程度。其次,利用格的模糊集的（强）水平集得到了模糊（素）滤子的等价刻画。最后,讨论了任意多个模糊子集的交、直积的模糊（素）滤子度以及格的模糊子集在同态映射下像与原像的模糊（素）滤子度的性质。     

Polynomial-time inference of all valid implications for Horn and related formulae

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.To the memory of Robert G. Jeroslow     

BR_0代数的模糊理想与直觉模糊理想

引入BR0代数的Fuzzy理想与素Fuzzy理想的概念;给出了Fuzzy理想与素Fuzzy理想的等价形式;在(素)Fuzzy理想基础之上又进一步引入了(素)直觉Fuzzy理想,并通过Fuzzy理想找到了它们与(素)理想之间的关系。     

一种基于Arnold置乱和优化大素数选取方案的RSA数字图像加密算法

提出了一种优化大素数选取方案的RSA算法和Arnold置乱结合的数字图像加密算法,该算法包括图像置乱加密和RSA加密。在传统RSA算法的基础上,针对大素数选取方案的优化,提出了一种以时间的流逝作为seed的随机大素数选取方案,提高了加密的安全性。实验结果表明,该方法有较强的安全性,密文图像对加性噪声的攻击也有一定的鲁棒性。     

Load balanced and optimal disk allocation strategy for partial match queries on multidimensional files

A multidimensional file is one whose data are characterized by several attributes, each specified in a given domain. A partial match query on a multidimensional file extracts all data whose attributes match the values of one or more attributes specified in the query. The disk allocation problem of a multidimensional file F on a database system with multiple disks accessible in parallel is the problem of distributing F among the disks such that the data qualifying for each partial match query are distributed as evenly as possible among the disks of the system. We propose an optimal solution to this problem for multidimensional files with pairwise prime domains based on a large and flexible class of maximum distance separable codes, namely, the redundant residue codes. We also introduce a new family of residue codes, called the redundant nonpairwise prime residue codes, to deal with files whose attribute domains are nonpairwise prime.     

Influences of haptic communication on a shared manual task

With the advent of new haptic feedback devices, researchers are giving serious consideration to the incorporation of haptic communication in collaborative virtual environments. For instance, haptic interactions based tools can be used for medical and related education whereby students can train in minimal invasive surgery using virtual reality before approaching human subjects. To design virtual environments that support haptic communication, a deeper understanding of humans′ haptic interactions is required. In this paper, human′s haptic collaboration is investigated. A collaborative virtual environment was designed to support performing a shared manual task. To evaluate this system, 60 medical students participated to an experimental study. Participants were asked to perform in dyads a needle insertion task after a training period. Results show that compared to conventional training methods, a visual-haptic training improves user′s collaborative performance. In addition, we found that haptic interaction influences the partners′ verbal communication when sharing haptic information. This indicates that the haptic communication training changes the nature of the users′ mental representations. Finally, we found that haptic interactions increased the sense of copresence in the virtual environment: haptic communication facilitates users′ collaboration in a shared manual task within a shared virtual environment. Design implications for including haptic communication in virtual environments are outlined.