C4- and D4-Modules via perspective direct summands

In this article, we study the C4- and D4-modules in terms of perspective direct summands, providing new characterizations and results. Endomorphism rings of C4-modules and extensions of right C4-rings are also investigated. Decompositions of C4-modules with restricted ACC on direct summands and D4-modules with restricted DCC on direct summands are obtained.     

Array processing machines: An abstract model

We present a new model of parallel computation called the array processing machine or APM (for short). The APM was designed to closely model the architecture of existing vector- and array processors, and to provide a suitable unifying framework for the complexity theory of parallel combinatorial and numerical algorithms. It is shown that every problem that is solvable in polynomial space on an ordinary, sequential random access machine can be solved in parallel polynomial time on an APM (and vice versa). The relationship to other models of parallel computation is discussed.This work was carried out while the second author was visiting the Dept. of Computer Science, University of Utrecht, the Netherlands (Fall 1984). A preliminary version of this paper was presented at the 5th International Conference on Fundamentals of Computation Theory (FCT 85), Cottbus, Sept. 9–13, 1985.     

Sections of zero dimensional ideals over a Noetherian ring

Let A be a commutative Noetherian ring and be an ideal containing a monic polynomial such that A[T]/I is zero dimensional. Suppose the conormal module I/I ² is generated by r elements over A[T]/I. Then a set of r generators of can be lifted to a r generating set of I. A part of this work is done at the Abdus Salam, International Centre for Theoretical Physics, Trieste, Italy. Received: 12 March 2006 Revised: 29 January 2007     

Distributed management of transactions in heterogeneous distributed database systems

In the two phase commit protocol, the coordinator decides to commit the distributed transaction if all its subtransactions are in a state called the prepared state. We have increased the semantics of the two phase commit protocols by replacing the prepared state by more restrictive states called the source state and the serializable state. The source state ensures that the execution of committed distributed transactions is not only atomic but also serializable. It also ensures that distributed transactions cannot interfere with other distributed transactions through local transactions, but it does not ensure a serializable view of the distributed database if local transactions are taken into account. The serializable state ensures that the execution is serializable also if local transactions are taken into account. Which of the two correctness criteria is appropriate for global concurrency control depends on the distributed applications of the system. In the proposed mechanism, each interconnected site supports the source state or the serializable state. Various methods of supporting these states are presented. Which method is appropriate for a site depends on the concurrency control method and the autonomy requirements of the site.     

Free summands of syzygies of modules over local rings

We give a new criterion for a commutative, Noetherian, local ring to be Cohen-Macaulay.     

Mixed Artin-Tate motives over number rings

This paper studies Artin-Tate motives over bases , for a number field F. As a subcategory of motives over S, the triangulated category of Artin-Tate motives is generated by motives , where ? is any finite map. After establishing the stability of these subcategories under pullback and pushforward along open and closed immersions, a motivic t-structure is constructed. Exactness properties of these functors familiar from perverse sheaves are shown to hold in this context. The cohomological dimension of mixed Artin-Tate motives () is two, and there is an equivalence .     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

Cleavability over ordinals

In this paper we show that if X is an infinite compactum cleavable over an ordinal, then X must be homeomorphic to an ordinal. X must also therefore be a LOTS. This answers two fundamental questions in the area of cleavability. We also leave it as an open question whether cleavability of an infinite compactum X over an ordinal λ implies X is embeddable into λ.     

The average performance of a parallel stable marriage algorithm

In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).     

Robust branch-cut-and-price for the Capacitated Minimum Spanning Tree problem over a large extended formulation

This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms: powerful new cuts expressed over a very large set of variables are added, without increasing the complexity of the pricing subproblem or the size of the LPs that are actually solved. Computational results on benchmark instances from the OR-Library show very significant improvements over previous algorithms. Several open instances could be solved to optimality.     

Generalized selection theorems without convexity

In this paper, we extend new selection theorems for almost lower semicontinuous multifunctions T on a paracompact topological space X to general nonconvex settings. On the basis of the Kim-Lee theorem and the Horvath selection theorem, we first show that any a.l.s.c. C-valued multifunction admits a continuous selection under a mild condition of a one-point extension property. Finally, we apply a fundamental selection theorem, due to Ben-El-Mechaiekh and Oudadess, to modify our selection theorems by adjusting a closed subset Z of X with its covering dimension dim_XZ≤0. The results derived here generalize and unify various earlier ones from classic continuous selection theory.     

Classifying subcategories of finitely generated modules over a Noetherian ring

For R a commutative Noetherian ring, wide and Serre subcategories of finitely generated R-modules have been classified by their support. This paper studies general torsion classes and introduces narrow subcategories. These are closed under fewer operations than wide and Serre subcategories, but still for finitely generated R-modules both narrow subcategories and torsion classes are classified using the same support data. Although for finitely generated R-modules all four kinds of subcategories coincide, they do not coincide in the larger category of all R-modules.     

Almost surely convergent summands of a random sum

We find a sufficient condition for a.s. convergence to zero of summands given that a sum of two sequences of random variables a.s. converges to zero. The condition turns out to be weaker than that used in the monograph by Loeve and in a paper by Martikainen. Our result is also used in construction of a counter-example regarding the a.s. convergence of a rearranged series.     

Two-dimensional representations of finitely generated free group over an arbitrary field

Working over an arbitrary field, we give equivalent conditions for a representation of a finitely generated free group with given traces and determinants to exist and to be reducible, respectively; also, we classify all two-dimensional representations of a finitely generated free group.     

On vector spaces over specific fields without choice

We investigate the deductive strength of statements concerning vector spaces over specific fields in the hierarchy of various choice principles.     

Pairs of quadratic forms over a quadratic field extension

Let F be a field of characteristic distinct from 2, $L=F(\sqrt{d})$ a quadratic field extension. Let further f and g be quadratic forms over L considered as polynomials in n variables, $M_f$, $M_g$ their matrices. We say that the pair $(f,g)$ is a k-pair if there exist $S\in G{L}_n(L)$ such that all the entries of the $k\times k$ upper-left corner of the matrices $S{M}_f{S}^t$ and $S{M}_g{S}^t$ are in F. We give certain criteria to determine whether a given pair $(f,g)$ is a k-pair. We consider the transfer ${\mathrm{cor}}_{L(t)/F(t)}$ determined by the $F(t)$-linear map $s:L(t)\to F(t)$ with $s(1)=0$, $s(\sqrt{d})=1$, and prove that if $\dim {\mathrm{cor}}_{L(t)/F(t)}{(f+tg)}_{an}\le 2(n?k)$, then $(f,g)$ is a $[\frac{k+1}{2}]$-pair. If, additionally, the form $f+tg$ does not have a totally isotropic subspace of dimension $p+1$ over $L(t)$, we show that $(f,g)$ is a $(k?2p)$-pair. In particular, if the form $f+tg$ is anisotropic, and $\dim {\mathrm{cor}}_{L(t)/F(t)}{(f+tg)}_{an}\le 2(n?k)$, then $(f,g)$ is a k-pair.     

The approachability ideal without a maximal set

We develop a forcing poset with finite conditions which adds a partial square sequence on a given stationary set, with adequate sets of models as side conditions. We then develop a kind of side condition product forcing for simultaneously adding partial square sequences on multiple stationary sets. We show that certain quotients of such forcings have the ${\omega }_1$-approximation property. We apply these ideas to prove, assuming the consistency of a greatly Mahlo cardinal, that it is consistent that the approachability ideal $I[{\omega }_2]$ does not have a maximal set modulo clubs.     

Lawvere theories enriched over a general base

We generalise the correspondence between Lawvere theories and finitary monads on in two ways. First, we allow our theories to be enriched in a category V that is locally finitely presentable as a symmetric monoidal closed category: symmetry is convenient but not necessary. And second, we allow the arities of our theories to be finitely presentable objects of a locally finitely presentable V-category A. We call the resulting notion that of a Lawvere A-theory. We extend the correspondence for ordinary Lawvere theories to one between Lawvere A-theories and finitary V-monads on A. We illustrate this with examples leading up to that of the Lawvere -theory for cartesian closed categories, i.e., the -enriched theory on the category for which the models are all small cartesian closed categories. We also briefly investigate change-of-base.     

Tame parts of free summands in coproducts of Priestley spaces

It is well known that a sum (coproduct) of a family of Priestley spaces is a compactification of their disjoint union, and that this compactification in turn can be organized into a union of pairwise disjoint order independent closed subspaces Xu, indexed by the ultrafilters u on the index set I. The nature of those subspaces Xu indexed by the free ultrafilters u is not yet fully understood.In this article we study a certain dense subset satisfying exactly those sentences in the first-order theory of partial orders which are satisfied by almost all of the Xi's. As an application we present a complete analysis of the coproduct of an increasing family of finite chains, in a sense the first non-trivial case which is not a ?ech-Stone compactification of the disjoint union I_?Xi. In this case, all the Xu's with u free turn out to be isomorphic under the Continuum Hypothesis.     

Extendability of quadratic modules over a polynomial extension of an equicharacteristic regular local ring

We prove that a quadratic A[T]$A[T]$-module Q   with Witt index (Q/TQ)?d$(Q/TQ)?d$, where d is the dimension of the equicharacteristic regular local ring A, is extended from A. This improves a theorem of the second named author who showed it when A is the local ring at a smooth point of an affine variety over an infinite field. To establish our result, we need to establish a local–global principle (of Quillen) for the Dickson–Siegel–Eichler–Roy (DSER) elementary orthogonal transformations.