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 .     

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     

Phase Conjugation in Saturable Absorbing Dye Films by Degenerate Four-Wave Mixing and Holographic Processes Using Nanosecond Pulse and CW Lasers

We report on the simultaneous generation of phase-conjugate signals by degenerate four-wave mixing (DFWM) and holographic processes using a nanosecond pulse and a CW lasers in polyvinyl alcohol (PVA) films doped with four kinds of saturable absorbing dyes. For the pulse laser, of the four kinds of dye-doped PVA films, the erythrosine B-doped PVA and uranine doped-PVA films generate PC signals only by the DFWM process, while the other dye-doped PVA films generate PC signals simultaneously by not only the DFWM process but also the holographic process. Especially, the safranin T-doped PVA film generates strong PC signals by the holographic process. In contrast, all of the dye-doped PVA films generate the two types of PC signals for the CW laser. The fading of dye molecules is found to result in the generation of the holographic component of PC signals which governs the temporal behavior of the total PC signals.     

覆盖广义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.     

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

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

Selection Principles and Sierpinski Sets

We show that a set of real numbers is a Sierpinski set if, and only if, it satisfies a selection property similar to the familiar Menger property.     

A New Family of Cyclic Difference Sets with Singer Parameters in Characteristic Three

We construct a new family of cyclic difference sets with parameters ((3 ^d – 1)/2, (3 ^{d – 1} – 1)/2, (3 ^{d – 2} – 1)/2) for each odd d. The difference sets are constructed with certain maps that form Jacobi sums. These new difference sets are similar to Maschietti's hyperoval difference sets, of the Segre type, in characteristic two. We conclude by calculating the 3-ranks of the new difference sets.