An upper （lower） bound for Max （Min） CSP

The random constraint satisfaction problem(CSP)instances generated by Model RB have been widely used in the field of CSP and have some nice features.In this paper,we consider two optimization versions of CSP,i.e.,the maximum constraint satisfaction problem(Max-CSP)and the minimum satisfaction problem(Min-CSP)of Model RB.The problem of the Max-CSP is how to find an assignment to all the variables such that the maximum number of constraints are satisfied and the problem of Min-CSP is how to find an assignment to all the variables such that the minimum number of constraints are satisfied.We use the first moment method to prove that when r2α(1/p-1)(or p2α/(2α+r)),an upper bound of Max-CSP can be derived.Similarly,we can prove that when r2α(1/p-1)(or p2α/(2α+r)),a lower bound of Min-CSP can be derived.     

On the size of randomized OBDDs and read-once branching programs for k-stable functions

In this paper, a simple technique which unifies the known approaches for proving lower bound results on the size of deterministic, nondeterministic, and randomized OBDDs and kOBDDs is described.?As an application of this technique, a generic lower bound on the size of randomized OBDDs with bounded error is established for a class of functions which has been studied in the literature on branching programs for a long time. These functions have been called “k-stable” by Jukna. It follows that several standard functions are not contained in the analog of the class BPP for OBDDs. Furthermore, exponential lower bounds on the size of randomized kOBDDs are presented.?It is well known that k-stable functions with large k are hard for deterministic read-once branching programs. This is no longer true in the randomized case. It is shown here that a certain k-stable function due to Jukna, Razborov, Savicky, and Wegener has randomized branching programs of polynomial size, even with zero error. It follows that for the analogs of these classes defined in terms of the size of read-once branching programs. Received: September 3, 1998.     

布尔函数线路复杂度的一个新的下界

布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。     

Upper bounds on the size of LR(k) parsers

It is shown that in many cases the trivial upper bound 2^{|G|k + 1} on the number of states of an LR(k) parser for a grammar G is too conservative. In particular, if G is not right-recursive, the canonical LR(k) parser for G has at most |G^k|G|·2^|G| states. Examples of grammars with large LR(k) parsers are given.     

循环程序的界函数合成

作为循环程序终止性分析的主流方法,当前的秩函数方法大多局限于线性或多项式秩函数的求解.针对循环程序若不存在对应的线性或多项式秩函数,现有秩函数方法就无法证明其终止性的问题,提出一个新的方法来合成给定循环程序对应的界函数.对于给定的循环程序,倘若能找到其界函数,则表明该循环程序是可终止的.首先将界函数的求解问题转化为一个...     

基于时区与时区估计的层次调度模型

本文针对偏序集（ＰＯＳ）任务的调度问题，提出一种基于时区与时区估计的层次调度模型．该模型与界定搜索（ＢｅａｍＳｅａｒｃｈ）方法有机结合，使得本文给出的调度算法具有搜索空间小、求解速度快的优点．     

用自同构循环图计算Ramsey数R(3,q)的下界*

确定经典Ramsey数的下界是组合数学中非常困难的问题,因而人们常用各种方法计算它的界。发现一种新的方法, 即自同构循环图的方法,计算得到三个经典Ramsey数的新下界：R(3,30)≥188,R(3,33)≥217,R(3,34)≥225。     

基于二元与三元模型相结合的句法规则层次化分析算法

句法分析是自然语言处理领域中应用前景非常广阔的一个研究方向.针对目前句法分析多数是从字、词的角度出发且存在诸多不足,提出了二、三元词模型相结合的句法规则层次化分析算法,并结合分词、词性标注以及句子组织信息之间的结合度来解决词元间优先合成的问题,同时利用句子成分之间的语法结构关系对词性、词序的影响,实现句法规则的层次化分...     

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

A tight lower bound for the worst case of Bottom-Up-Heapsort

Bottom-Up-Heapsort is a variant of Heapsort. Its worst-case complexity for the number of comparisons is known to be bounded from above by 3/2n logn+0(n), wheren is the number of elements to be sorted. There is also an example of a heap which needs 5/4n logn-0(n log logn) comparisons. We show in this paper that the upper bound is asymptotically tight, i.e., we prove for largen the existence of heaps which need at least 3/2n logn–O(n log logn) comparisons. This result also proves the old conjecture that the best case for classical Heapsort needs only asymptotic n logn + O(n log logn) comparisons.This work was supported by the ESPRIT II program of the EC under Contract No. 3075 (project ALCOM).     

On the definition of ELR(k) and ELL(k) grammars

Summary Extended context free grammars are obtained by allowing regular expressions on the right hand sides of production rules of context free grammars. The LR(k) and LL(k) conditions are made applicable to these grammars by defining canonical transformations of extended grammars into context free grammars.     

A characterization of span program size and improved lower bounds for monotone span programs

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.?In the monotone case our new methods yield lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is suficient for constructing Boolean functions with large monotone span program complexity. Received: September 30, 2000.     

A numerical study of k(3,2) equation

The Korteweg-de Vries (Kdv) equation has been generalized by Rosenau and Hyman [7] to a class of partial differential equations (PDEs) which has solitary wave solution with compact support. These solitary wave solutions are called compactons

Compactons are solitary waves with the remarkable soliton property, that after colliding with other compactons, they reemerge with the same coherent shape. These particle like waves exhibit elastic collision that are similar to the soliton interaction associated with completely integrable systems. The point where two compactons collide are marked by a creation of low amplitude compacton-anticompacton pair. These equations have only a finite number of local conservation laws

In this paper, an implicit finite difference method and a finite element method have been developed to solve the K(3,2) equation. Accuracy and stability of the methods have been studied. The analytical solution and the conserved quantities are used to assess the accuracy of the suggested methods. The umerical results have shown that this compacton exhibits true soliton behavior.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

Lower bounds for the multiplicative complexity of matrix multiplication

We prove a lower bound of km + mn + k—m + n— 3 for the multiplicative complexity of the multiplication of -matrices with -matrices using the substitution method. Received: July 8, 1997.     

Formal Derivation of Graph AlgorithmicPrograms Using Partition-and-Recur

In this paper,we derive,by presenting some suitable notations,three typical graph algorithms and corresponding programs using a unified approach,partition-and-recur.We putemphasis on the derivation rather than the algorithms themselves.The main ideas and ingenuity of these algorithms are revealed by formula deduction.Success in these examples gives us more evidence that partition-and-recur is a simple and practical approach and developing enough suitable notations is the key in designing and deriving efficient and correct algorithmic programs.     

The embedding of rings and meshes into RP(k) networks

Copyright by Science in China Press 2004 Interconnection networks, as an important means in parallel processing systems, are investigated widely[1,2]. Recently a class of lower-degree networks is proposed[2—4]. In ref. [3] we have investigated a constant degree network, called RP(k) network. Com-pared with rings and 2-D mesh networks, the RP(k) network has many good properties. The RP(k) network has a much smaller diameter than that of 2-D meshes when the number of network nodes is less …