Solving Hankel Systems over the Integers

A new algorithm is presented for computing the solution of a Hankel system with integer entries by means of structured matrix techniques. By combining subresultant theory and factorization properties of Hankel matrices, we prove that this algorithm has a Boolean sequential cost which is almost optimal among the algorithms based on fast integer LU factorization.     

基于整数的轻量级分组密码电路的同态运算

基于Gentry等在EUROCRYPT 2010上提出的整数上的全同态加密DGHV方案,结合批处理技术,给出了轻量级分组密码SIMON电路的状态切割同态运算实现方法;提出了半字节切割概念,给出了PRINCE电路的半字节切割同态运算实现方法。最后将PRINCE,SIMON-64/128,SIMON-128/256和AES-128电路的同态运算进行对比,分析给出了不同分组密码电路和不同实现方法的同态计算次数。     

Finding All Solution Sets of Piecewise-Trapezoidal Equations Described by Set-Valued Functions

This letter deals with the problem of bounding all solution sets to systems of nonlinear equations where nonlinear terms are described by set-valued functions termed piecewise-trapezoidal functions. Such a problem is important in the numerical computation with guaranteed accuracy and in the analysis of fluctuated systems (such as the tolerance analysis of electronic circuits). It is shown that the proposed algorithm could find all solution sets to a system of 300 piecewise-trapezoidal equations approximately in about 30 hours using a 360 MHz computer.     

基于布尔矩阵的模糊粗糙集代数运算与表示定理

主要研究模糊粗糙集理论基本概念与基本运算的矩阵表示,用布尔矩阵对模糊粗糙集理论中的基本概念进行描述,并通过布尔矩阵运算性质研究、揭示和刻画模糊粗糙集知识空间的基本代数性质.文中定义了布尔矩阵"与积"和"或积"两种逻辑运算,分别对模糊粗糙集理论中的模糊可能(fuzzy diamond)算子和模糊必然(fuzzy box)算子计算过程进行描述,对模糊粗糙集理论的基本概念和基本代数性质给出了基于布尔矩阵的表示定理,为基于模糊粗糙集理论的知识表示与知识获取提供了一种能行与可计算的思路与方法.     

区间集上的一元格蕴涵代数方程

把格蕴涵代数中滤子、素滤子、LI-理想、对偶原子和凸子格等概念拓展到区间集进行了重新定义,研究了三种基本的区间集上的一元格蕴涵代数方程,并给出了方程的可解性判断条件以及方程解集的若干性质.     

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

We present simple, self-contained proofs of correctness for algorithms for linearity testing and program checking of linear functions on finite subsets of integers represented as n-bit numbers. In addition we explore a generalization of self-testing to homomorphisms on a multidimensional vector space. We show that our self-testing algorithm for the univariate case can be directly generalized to vector space domains. The number of queries made by our algorithms is independent of domain size.     

Representing Animations by Principal Components

In this paper, we present a representation for three-dimensional geometric animation sequences. Different from standard key-frame techniques, this approach is based on the determination of principal animation components and decouples the animation from the underlying geometry. The new representation supports progressive animation compression with spatial, as well as temporal, level-of-detail and high compression ratios. The distinction of animation and geometry allows for mapping animations onto other objects.     

C1 Quadratic Interpolation over Arbitrary Point Sets

New formulas for generating smooth surfaces over arbitrarily spaced data points are developed. The formulas are based on quadratic polynomials for the construction of derivative continuous surfaces rather than on the cubic polynomials generally used. The technique is based on a subdivision procedure, dividing each triangle in a triangulation of the data points into six subtriangles and fitting a quadratic Bezier surface patch over each subtriangle. THe formulas require only function and first derivative values at the data points and are easily evaluated in terms of the Bezier coefficients. Since two-dimensional quadratic polynomials contain only six terms, while 10 terms are required to evaluate a cubic, the new procedure significantly improves the efficiency of algorithms for drawing surfaces in computer-aided geometric design.     

Equivalence Problems for Circuits over Sets of Natural Numbers

We investigate the complexity of equivalence problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C ₌ L, P,Π₂^P, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of {∪,∩,⁻,+,×}-circuits.     

Representing inference control by hypothesis-based association

An approach for representing inference control is presented. It is proposed that the representation of inference control should consist of two levels: planning level which realizes problem solving strategies, and a performing level, which represents inference tactics. Based on this approach, the representation system hypothesis-based associative representation (HAR) has been developed to realize the functional architecture for knowledge-based systems. Because users are allowed to organize hypothesis-based associative networks that perform the problem solving strategies with different features, HAR becomes not only a tool for building knowledge-based systems, but also an environment for exploring AI techniques. For example, by comparing three strategies of block-world action planning, it is found that the least commitment strategy is the most efficient     

Representing and processing lineages over uncertain data based on the Bayesian network

Processing lineages (also called provenances) over uncertain data consists in tracing the origin of uncertainty based on the process of data production and evolution. In this paper, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian network (BN), one of the popular and important probabilistic graphical models (PGMs), as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for SPJ (Selection–Projection–Join) queries over uncertain data, we propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, can be constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN's exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN's approximate inferences. Experimental results show the efficiency and effectiveness of our methods.     

Interval Estimations of Solution Sets to Real-Valued Systems of Linear or Non-Linear Equations

This is a second paper devoted to present the Modal Interval Analysis as a framework where the search of formal solutions for a set of simultaneous interval linear or non-linear equations is started on, together with the interval estimations for sets of solutions of real-valued systems in which coefficients and right-hand sides belong to certain intervals. The main purpose of this second paper is to show that the modal intervals are a suitable tool to approach problems where logical references appear, for example, to find interval estimates of a special class of generalized sets of solutions of real-valued linear and non-linear systems, the UE-solution sets.     

Systems of Random Equations over Finite Algebraic Structures

The results on systems of random equations over finite algebraic structures are reviewed. Basic definitions, concepts, and problems in this field are presented.__________Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 82–116, January–February 2005.     

Equations over sets of integers with addition only

Systems of equations of the form $X=Y+Z$ and $X=C$ are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set $S\subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component T with $S=\{n|16n+13\in T\}$. Testing solution existence for these equations is ${\mathrm{\Pi }}_1^0$-complete, solution uniqueness is ${\mathrm{\Pi }}_2^0$-complete, and finiteness of the set of solutions is ${\mathrm{\Sigma }}_3^0$-complete. A similar construction for integers represents any hyper-arithmetical set $S\subseteq \mathbb{Z}$ by a set $T\subseteq \mathbb{Z}$ satisfying $S=\{n|16n\in T\}$, whereas testing solution existence is ${\mathrm{\Sigma }}_1^1$-complete.     

Representing Epistemic Uncertainty by Means of Dialectical Argumentation

We articulate a dialectical argumentation framework for qualitative representation of epistemic uncertainty in scientific domains. The framework is grounded in specific philosophies of science and theories of rational mutual discourse. We study the formal properties of our framework and provide it with a game theoretic semantics. With this semantics, we examine the relationship between the snaphots of the debate in the framework and the long run position of the debate, and prove a result directly analogous to the standard (Neyman–Pearson) approach to statistical hypothesis testing. We believe this formalism for representating uncertainty has value in domains with only limited knowledge, where experimental evidence is ambiguous or conflicting, or where agreement between different stakeholders on the quantification of uncertainty is difficult to achieve. All three of these conditions are found in assessments of carcinogenic risk for new chemicals.     

一种从不完备数据集中发现规则的RS方法

Rough集(Rough SetS、Rs)理论被广泛应刑于数据分类问题,该文用基于RS的方法从不完备数据集中产生确定和可能的规则集,提出了一种新的规则发现算法,可以同时从不完备数据集中产生规则和估计缺失值,并指出了进一步的研究方向。     

面向海量数据的空间co-location模式挖掘新算法

空间co-location模式挖掘是空间数据挖掘的一个重要任务,目前无论是挖掘确定数据,还是不确定数据,算法的时间和空间效率都不高,更谈不上对海量数据进行挖掘。为此,在深入分析传统挖掘方式过度消耗时间和空间资源的根本原因的基础上,提出了网格微分挖掘co-location模式的算法。新算法在传统网格基础上实施微分,求出各微分格中属于同一特征的实例质心,并基于这些质心进行多分辨剪枝co-location模式挖掘。算法在保证具有较高准确率的前提下,较好地解决了传统挖掘方式中存在的效率问题,从而解决了面向海量数据进行空间co-location模式挖掘的难题。大量实验证明,网格微分算法具有高效性、稳健性和高准确率等优点。     

Bubble Sets: Revealing Set Relations with Isocontours over Existing Visualizations

While many data sets contain multiple relationships, depicting more than one data relationship within a single visualization is challenging. We introduce Bubble Sets as a visualization technique for data that has both a primary data relation with a semantically significant spatial organization and a significant set membership relation in which members of the same set are not necessarily adjacent in the primary layout. In order to maintain the spatial rights of the primary data relation, we avoid layout adjustment techniques that improve set cluster continuity and density. Instead, we use a continuous, possibly concave, isocontour to delineate set membership, without disrupting the primary layout. Optimizations minimize cluster overlap and provide for calculation of the isocontours at interactive speeds. Case studies show how this technique can be used to indicate multiple sets on a variety of common visualizations.     

Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers

A finite recurrent system over sets of natural numbers of dimension n is a pair composed of n n-ary functions over sets of natural numbers and an n-tuple of singleton sets of natural numbers. Every function is applied to the entries of the tuple and computes a set of natural numbers, that may also be empty. The results are composed into another tuple, and the process is started anew. Thus, a finite recurrent system defines an infinite sequence of n-tuples containing sets of natural numbers. The last entry of a generated n-tuple is called the output of a step, and the union of the output sets of all steps is the set defined by the finite recurrent system. Membership problems ask whether a given number is in a specified output set or in some output set. We study membership problems for special finite recurrent systems, whose functions are built from the set operations union, intersection and complementation and the arithmetical operations addition and multiplication. Sum and product of two sets of natural numbers are defined elementwise. We restrict the set of operations from which functions are built and determine the impact on the complexity of the membership problems. We focus on PSPACE-decidable membership problems and show completeness results for the complexity classes NL, NP and PSPACE.