Initial Segments of Recursive Linear Orders

We show that any -initial segment of a recursive linear order can be presented recursively.     

Linear Extensions of Additive Partial Orders

Addive partial orders arise naturally in theories of comparativeprobability and subset preferences. An additive partial order is a partialorder on the family of subsets of ann-element set that satisfies . This is reformulated as a subset P of {1,0,–1}ⁿ that excludes 0 and containsx+y whenever x,y P and x+y {1,0,–1}ⁿ. Additional conditions of positivity andcompleteness give rise to positive additive partial orders and additivelinear orders respectively. The paper investigates conditions under which anadditive partial order is included in, or extendable to, an additive linearorder. The additive dimension of an extendable additive partial order isdefined and computed for several classes of additive orders.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

具有2n线性复杂度的2n周期二元序列的3错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n的2n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式, k=3,4.对于一般的线性复杂度为2n-m的2n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式.     

Cofinalities of Linear Orders

We investigate whether the existence of long linear orders can be proved without the Axiom of Choice. This question has two different answers depending on its formalization.     

Linear Complexity of the Discrete Logarithm

We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.     

Confidence intervals in the solution of stochastic integer linear programming problems

A method is proposed to estimate confidence intervals for the solution of integer linear programming (ILP) problems where the technological coefficients matrix and the resource vector are made up of random variables whose distribution laws are unknown and only a sample of their values is available. This method, based on the theory of order statistics, only requires knowledge of the solution of the relaxed integer linear programming (RILP) problems which correspond to the sampled random parameters. The confidence intervals obtained in this way have proved to be more accurate than those estimated by the current methods which use the integer solutions of the sampled ILP problems.This research was partially supported by the Italian National Research Council contract no. 82.001 14.93 (P.F. Trasporti).     

Free Triangle Orders

We define a new class of ordered sets, called free triangle orders. These are ordered sets represented by a left-to-right ordering on geometric objects contained in a horizontal strip in the plane. The objects are called 'free triangles', and have one vertex on each of the two boundaries of the strip and one vertex in its interior. These ordered sets generalize the classes of trapezoid and triangle orders studied by Bogart, Möhring, and Ryan, represented by trapezoids and triangles respectively, contained within a strip in the plane, and are a special case of the orders of tube dimension 2 introduced by Habib and co-workers, which are represented by any set of convex bodies contained within a strip in the plane. Our main result is that the class of free triangle orders strictly contains the class of trapezoid orders.     

On Operations and Linear Extensions of Well Partially Ordered Sets

A (partially) ordered set P is well founded if no infinite decreasing sequences occur in P. A well founded poset containing no infinite antichains is called partially well ordered. We investigate some operations preserving that property and linear extensions of partial well orders. This revised version was published online in September 2006 with corrections to the Cover Date.     

Cycle Orders

Let X, T and C be, respectively, a finite set with at least three points, a set of ordered triples of distinct points from X, and a cyclic ordering of the points in X. Define T C to mean that, for every a b c T, the elements a, b, c occur in that cyclic order in C, and let C(T) denote the set of cyclic orderings of X for which T C. We say that T is noncyclic if C(T) is empty, cyclic if C(T) is nonempty, uniquely cyclic if | C(T) | = 1, a partial cycle order if it is cyclic and T ={a b c :{a b c} C for all C C(T)}, and a total cycle order if it is a uniquely cyclic partial cycle order. Many years ago E. V. Huntington axiomatized total cycle orders by independent necessary and sufficient conditions on T. The present paper studies the more relaxed structures of cyclic T sets and partial cycle orders. We focus on conditions for cyclicity, a theory of cycle dimension of partial cycle orders, and extremal problems that address combinatorial structures of T sets.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

On k-CS-Transitive Cycle-Free Partial Orders with Finite Alternating Chains

The notion of cycle-free partial order (CFPO) was defined by R. Warren, and the major cases of the classification of the countable sufficiently transitive CFPOs were given, the finite and infinite chain cases, by Creed, Truss, and Warren. It is the purpose of this paper to complete the classification. The cases which remained untreated were CFPOs not embedding an infinite alternating chain ALT (which can only happen in the finite chain case). It is shown that if a k-CS-transitive CFPO does not embed ALT, where k 3, then it does not embed any alternating chain of size k + 3, and this leads to the desired classification (which is only given explicitly for k = 3 and 4). The general result says that the class of k-CS-transitive CFPOs for k 3 not embedding ALT admits a recursive classification.     

Extending Partial Orders on o-Minimal Structures to Definable Total Orders

It is shown that if (M, <, ?) is an o-minimal structure such that (M, <) is a dense total order and ? is a parameter-definable partial order on M, then ? has an extension to a definable total order.     

Counting Split Interval Orders

A poset (X,) is a split interval order (a.k.a. unit bitolerance order, proper bitolerance order) if a real interval and a distinguished point in that interval can be assigned to each xX so that xy precisely when x's distinguished point precedes y's interval, and x's interval precedes y's distinguished point. For each |X|9, we count the split interval orders and identify all posets that are minimal forbidden posets for split interval orders. The paper is a companion to Counting Split Semiorders by Fishburn and Reeds (this issue).     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.     

Epimorphisms Between Linear Orders

We study the relation on linear orders induced by order preserving surjections. In particular we show that its restriction to countable orders is a bqo.     

Negative Dense Linear Orders

Considering dense linear orders, we establish their negative representability over every infinite negative equivalence, as well as uniformly computable separability by computable gaps and the productivity of the set of computable sections of their negative representations. We construct an infinite decreasing chain of negative representability degrees of linear orders and prove the computability of locally computable enumerations of the field of rational numbers.     

Cube Orders

A finite partially ordered set P =(X, ) is a cube order in R ^m if there is a map C from X into cubes in R ^m such that, for all x and y in X, x y if and only if C(x) C(y). It is proved that every finite poset with order dimension 2 m is a cube order in R ^m .     

p元扩展序列的线性复杂度

给出了由周期为p~m-1的p元序列导出的周期为p~(em)-1的p元扩展序列的线性复杂度.作为一个实例,计算了扩展Legendre序列的线性复杂度.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.