完全二叉树的量词消去

量词消去法已经成为计算机科学和代数模型论中最有力的研究工具之一.本 文针对完全二叉树理论所独有的特性,给出了它的基本公式集,然后利用分布公式及 有限覆盖证明了完全二叉树的理论可以量词消去.     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

投入产出系统的完全需要系数矩阵的简化计算方法

对大型投入产出系统进行经济结构分析，需要考虑对投入产出系统的分解，由最终产品确定总产品，需要计算完全需要系数矩阵（I－A）^-1。由于投入产出系统的分析和计算的工作量主要集中于（I－A）^-1，本文给出了矩阵（I－A）^-1的简化计算方法，它具有非常的实际意义。     

不完全信息下房地产价格的演化博弈分析

基于PAB(Pay-As-Bid)竞价机制,探讨不完全信息情况下供需关系对房屋成交价格的影响.在购房者对房屋价格预期不确定和购房者有限理性的假设下,利用鲁棒优化技术和演化博弈论中的"复制动态"思想,提出鲁棒演化博弈均衡的概念,建立相应的复制动态系统,并对系统的鲁棒演化均衡的渐进稳定性进行分析,得到在不同市场供需情况下购房者价格策略演化的一般规律.最后选用数值算例对模型加以验证.     

不完全博弈学习过程的虚拟行动规则

本文把博弈学习虚拟行动规则的学习时间一般化,研究不完全学习过程中参与人策略选择的收敛性及效用一致性问题. 分析结果表明：当学习时间不完全时,在学习一致到达的条件下,虚拟行动规则对严格纳什均衡是吸收的; 在学习时间充分及时与虚拟行动非频繁转换的条件下,各参与人的虚拟行动具有效用一致性.     

关于Banach空间的无条件基

给出具有唯一无条件基的无穷维Banach空间,并给出其无条件基的若干性质.     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

野生中药材供给与稽查的不完全信息动态博弈分析

针对中药材供给中的信息不对称性,建立了三个中药材供给方与政府稽查部门之间的三个不完全信息动态博弈模型,得到了相应的子博弈精炼贝叶斯均衡解的五个结论.这五个结论合理刻画了中药材供给方与政府稽查部门的博弈行为并揭示了非法采挖野生中药材现象难以杜绝的原因.结果表明,政府对稽查行为的条件激励措施并不能有效杜绝非法采挖野生中药材现象,只有政府对所有的稽查行为实施普遍的强激励机制才可从根本上消除非法采挖野生中药材的现象.     

多圆柱上的完全准凸映射

在C~n中有界凸Reinhardt域上讨论了一类介于凸映射类与星形映射类之间的“完全准凸映射类”.特别地,在C~n中的多圆柱上给出了完全准凸映射的分解定理,得到了多圆柱上判别凸映射的一个改进的充分条件.     

无原子布氏代数理论的计算复杂性

研究无原子布氏代数的计算复杂性 .得到了下面的新定理 :定理 1　无原子布氏代数理论Δ具有完全的量词消去法 ,也就是说每一个式子都Δ等价于一个开式子 .定理 2　无原子布氏代数的初等型Γ (x1,… ,xn)是由型内的不含量词的全体开式子所唯一决定 .定理 3　无原子布氏代数的一个长度为 n的语句的判断过程所消耗的 Turing时间和空间都是属于 2 2 cn指数级 .     

A New View of the Computational Complexity of IVP for ODE

The cost of solving an initial value problem for ordinary differential equations to accuracy 2 is polynomial in ln. Adaptive step-size control is never theoretically more costly than fixed step-size control, and can be an unbounded factor less costly. These results contradict the standard theory, but are based on more realistic assumptions.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

完全区间树顶点数目的大数律

本文讨论完全区间树顶点数目Sx的大数律,所采用的方法不同于单边区间树．文章包括三部分内容:首先探讨完全区间树所得以定义的概率空间,弄清楚它的结构,为强大数律的研究奠定理论基础．接着,针对完全区间树上的Sx的矩母函数不易求得的情况,另辟蹊径,求得Sx的期望和方差．最后,给出Sx的强弱大数律．     

Order Structure on the Algebra of Permutations and of Planar Binary Trees

Let X _n be either the symmetric group on n letters, the set of planar binary n-trees or the set of vertices of the (n – 1)-dimensional cube. In each case there exists a graded associative product on _n0 K[X _n]. We prove that it can be described explicitly by using the weak Bruhat order on S _n, the left-to-right order on planar trees, the lexicographic order in the cube case.     

On the Complexity Functions for T-Ideals of Associative Algebras

Let be the sequence of codimension growth for a variety V of associative algebras. We study the complexity function , which is the exponential generating function for the sequence of codimensions. Earlier, the complexity functions were used to study varieties of Lie algebras. The objective of the note is to start the systematic investigation of complexity functions in the associative case. These functions turn out to be a useful tool to study the growth of varieties over a field of arbitrary characteristic. In the present note, the Schreier formula for the complexity functions of one-sided ideals of a free associative algebra is found. This formula is applied to the study of products of T-ideals. An exact formula is obtained for the complexity function of the variety U c of associative algebras generated by the algebra of upper triangular matrices, and it is proved that the function is a quasi-polynomial. The complexity functions for proper identities are investigated. The results for the complexity functions are applied to study the asymptotics of codimension growth. Analogies between the complexity functions of varieties and the Hilbert--Poincaré series of finitely generated algebras are traced.     

On positive homogeneity and comonotonic additivity of the principle of equivalent utility under Cumulative Prospect Theory

Investigating the principle of equivalent utility under Cumulative Prospect Theory, Kałuszka and Krzeszowiec (2012) established characterizations of several important properties of the premium. It turns out that the results concerning positive homogeneity and comonotonic additivity are in general not true. The aim of this paper is to present modified and essentially generalized versions of the mentioned above results.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

On the cut‐off phenomenon for the transitivity of randomly generated subgroups

Consider K ≥ 2 independent copies of the random walk on the symmetric group S_N starting from the identity and generated by the products of either independent uniform transpositions or independent uniform neighbor transpositions. At any time $n\in \mathbb{N}$, let G_n be the subgroup of S_N generated by the K positions of the chains. In the uniform transposition model, we prove that there is a cut‐off phenomenon at time N ln(N)/(2K) for the non‐existence of fixed point of G_n and for the transitivity of G_n, thus showing that these properties occur before the chains have reached equilibrium. In the uniform neighbor transposition model, a transition for the non‐existence of a fixed point of G_n appears at time of order $N^{1+\frac{2}{K}}$ (at least for K ≥ 3), but there is no cut‐off phenomenon. In the latter model, we recover a cut‐off phenomenon for the non‐existence of a fixed point at a time proportional to N by allowing the number K to be proportional to ln(N). The main tools of the proofs are spectral analysis and coupling techniques. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A general form of Jordan-type double inequality for the generalized and normalized Bessel functions

In this note, a general form of Jordan-type double inequality involving the generalized and normalized Bessel functions is presented, and then some recent results concerning generalized and sharp work of Jordan’s inequality are extended. At the same time, the applications of the results above give two new infinite series for sinx/x and sinhx/x.