Orders of Indescribable Sets

We extract some properties of Mahlo’s operation and show that some other very natural operations share these properties. The weakly compact sets form a similar hierarchy as the stationary sets. The height of this hierarchy is a large cardinal property connected to saturation properties of the weakly compact ideal.     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

Local homology and dimensional full-valuedness

A natural criterion for dimensional full-valuedness of locally compact spaces with finitely generated local homology is given.     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

Artificial time integration

Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought. In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency. AMS subject classification (2000)  65L05, 65M32, 65N21, 65N22, 65D18     

覆盖广义Rough集中的隶属关系

对覆盖广义Rough集中的隶属关系、隶属函数进行了定义，并利用隶属函数定义了集合的Rough包含与Rough相等，得到一些与Pawlak的Rough集不同的性质。     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

AN ITERATIVE EQUATION ON THE UNIT CIRCLE

A functional equation of nonlinear iterates is discussed on the circle S1 for its continuous solutions and differentiable solutions. By lifting to R, the existence, uniqueness and stability of those solutions are obtained. Techniques of continuation are used to guarantee the preservation of continuity and differentiability in lifting.     

极大单调算子和m增生映射值域的扰动定理及在非线性微分方程上的应用

利用不动点定理,分别证明了在自反Banach空间中极大单调算子值域扰动的抽象结论和在H ilbert空间中m增生映射值域的扰动结果,这些结论是对以往一些工作的推广;然后,利用文中的新结论讨论了一类微分方程解的存在性.     

确定线性偏微分方程组可积系统的对合特征集方法

基于Ritt-Wu特征集方法和Riquier-Janet理论,给出一种将线性微分方程组化成简单标准形式的有效算法．该算法通过消去冗余和添加可积条件获得线性微分方程组的完全可积系统(有形式幂级数解)或不相容判定．该算法不仅适用于常系数的线性偏微分方程组,而且对于变系数(以函数为系数)仍然有效．作者还给出了完全可积系统判定定理及其严格证明．