Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

Standard completions for quasiordered sets

A standard completion for a quasiordered set Q is a closure system whose point closures are the principal ideals of Q. We characterize the following types of standard completions by means of their closure operators:

1. V-distributive completions,
2. Completely distributive completions,
3. A-completions (i.e. standard completions which are completely distributive algebraic lattices),
4. Boolean completions.

Moreover, completely distributive completions are described by certain idempotent relations, and the A-completions are shown to be in one-to-one correspondence with the join-dense subsets of Q. If a pseudocomplemented meet-semilattice Q has a Boolean completion ?, then Q must be a Boolean lattice and ? its MacNeille completion.     

Topological conditions enabling use of harris methods in discrete and continuous time

This paper describes the role of continuous components in linking the topological and measuretheoretic (or regenerative) analysis of Markov chains and processes. Under Condition $\mathcal{T}$ below we show the following parallel results for both discrete and continuous time models:

1. when the model is open set irreducible it is ?-irreducible;
2. under (i), the measure-theoretic classification of the model as Harris recurrent or positive Harris recurrent is equivalent to a topological classification in terms of not leaving compact sets or of tightness of transition kernels;
3. under (i), the ‘global’ classification of the model as transient, recurrent or positive recurrent is given by a “local’ classification of any individual reachable point;
4. under (i), every compact set is a small set, so that through the Nummelin splitting there is pseudo-regeneration within compact sets, and compact sets are ‘test sets’ for stability;
5. even without irreducibility, there is always a Doeblin decomposition into a countable disjoint collection of Harris sets and a transient set. We conclude with a guide to verifying Condition $\mathcal{T}$ and indicate that it holds under very mild constraints for a wide range of specific models: in particular a ?-irreducible Feller chain satisfies Condition $\mathcal{T}$ provided only that the support of ? has nonempty interior.

     

States on bounded commutative residuated lattices

We define states on bounded commutative residuated lattices and consider their property. We show that, for a bounded commutative residuated lattice X,

1. If s is a state, then X/ker(s) is an MV-algebra.
2. If s is a state-morphism, then X/ker(s) is a linearly ordered locally finite MV-algebra.

Moreover we show that for a state s on X, the following statements are equivalent:

1. s is a state-morphism on X.
2. ker(s) is a maximal filter of X.
3. s is extremal on X.

     

On the number of non-isomorphic subgraphs

Let $\mathcal{K}$ be the family of graphs on ω₁ without cliques or independent subsets of sizew ₁. We prove that

1. it is consistent with CH that everyGε $\mathcal{K}$ has 2^ω many pairwise non-isomorphic subgraphs,
2. the following proposition holds in L: (*)there is a Gε $\mathcal{K}$ such that for each partition (A, B) of ω₁ either G?G[A] orG?G[B],
3. the failure of (*) is consistent with ZFC.

     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Randverteilungen von Nullösungen hypoelliptischer Differentialgleichungen

In this paper a distributional boundary value is defined for solutions f (defined on ?ⁿ⁺¹\?ⁿ) of a partially hypoelliptic differential operator (on ?ⁿ⁺¹)with constant coefficients. Then the following is equivalent:

1. f has a distributional boundary value.
2. f can be continued to ?ⁿ⁺¹ as a distribution. For hypoelliptic operators this is equivalent to:
3. f ist a locally slowly growing function. A topology is given on this function space, that makes the boundary value mapping a topological homomorphism.

     

Topologies on products of partially ordered sets III: Order convergence and order topology

This paper deals with the question under which circumstances filter-theoretical order convergence in a product of posets may be computed componentwise, and the same problem is treated for convergence in the order topology (which may differ from order convergence). The main results are:

1. Order convergence in a product of posets is obtained componentwise if and only if the number of non-bounded posets occurring in this product is finite (1.5).
2. For any product of posets, the projections are open and continuous with respect to the order topologies (2.1).
3. A productL of chainsL _i has topological order convergence iff all but a finite number of the chains are bounded. In this case, the order topology onL agrees with the product topology (2.7).
4. If (L _i :j ∈J) is a countable family of lattices with topological order convergence and first countable order topologies then order topology of the product lattice and product topology coincide (2.8).
5. LetP ₁ be a poset with topological order convergence and locally compact order topology. Then for any posetP ₂, the order topology ofP ₁?P ₂ coincides with the product topology (2.10).
6. A latticeL which is a topological lattice in its order topology is join- and meet-continuous. The converse holds whenever the order topology ofL?L is the product topology (2.15).

Many examples are presented in order to illustrate how far the obtained results are as sharp as possible.     

On a class of σ-space with special nets

Strong CP(HCP)-netted spaces are defined and some properties are shown. In particular, the following results are shown.

1. A submetrizable space is strong CP(HCP)-netted provided that the space admits a perfect map onto a strong CP(HCP)-netted space.
2. The image of a strong CP(HCP)-netted space under a perfect map is strong CP(HCP)-netted space.
3. A stratifiable space is strong HCP-netted if the space has a countable closed cover consisting of strong HCP-netted subspaces.

     

Analysis of bounded sets in a topological tensor product

The aim of this paper is to investigate the nature of bounded sets in a topological ∈-tensor product EX_∈* F of any two locally convex topological vector spaces E and F over the same scalar field K. Next, we apply the results of this investigation to the study of each of the following:

1. Totally summable families in EX_∈*F;
2. ∈-tensor product of DF-spaces;
3. Topological nature of the dual of E X_∈*F, where E and F are strong duals of Banach spaces;
4. Properties of bounded sets in an ∈-tensor product of metrizable spaces.

Forπ-tensor product, the result corresponding to (b) is well known (see Grothendieck¹) that if E and F are DF-spaces then EX_π* F and EX_π* F are DF-spaces and that the strong topology on the topological dual (EX_π*F)′, which equals the space of continuous bilinear forms on EXF, coincides with the bibounded topology. We study each of the problems from (a) to (d) for ∈-tensor products. For terminology, notations and the well-known results in the theory of topological vector spaces and the topological tensor products we refer to [1–11]. However, for convenience in presentation of the results of our investigation we give a brief survey of notations and fundamental theorems which are needed throughout this paper.     

Über Deformationen von analytischen Abbildungskeimen

The notion of deformations of germs of k-analytic mappings generalizes the one of deformations of germs of k-analytic spaces. Using algebraic terms, we prove:

1. The morphism f: A→B of analytic algebras is rigid, iff it is infinitesimally rigid. Moreover, this is equivalent to Ex_A (B,B)=0. This theorem generalizes a result of SCHUSTER [11].
2. Let A be a regular analytic algebra. Then f is rigid iff there exists a rigid analytic algebra B_o such that f is equivalent to the canonic injection A→A?B_o.
3. If f is “almost everywhere” rigid or smooth, then the injection Ext _B ^l (Ω_B|A, Bⁿ)→Ex_A(B, Bⁿ) is an isomorphism.

     

A Remark on non-separable solutions to the Schroeder-Bernstein Problem for Banach spaces

We show that the geometric structure of Banach spaces which are solutions to the Schroeder-Bernstein Problem is very complex. More precisely, we prove that there exists a non-separable solution E to this problem such that

1. E is isomorphic to each one of its finite codimensional subspaces.
2. E has no complemented Hereditarily Indecomposable subspace.
3. E has no complemented subspace isomorphic to its square.
4. E has no non-trivial divisor.

     

Multidimensional symmetric stable processes

This paper surveys recent remarkable progress in the study of potential theory for symmetric stable processes. It also contains new results on the two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric α-stable process in boundedC ^1,1 open sets. The new results give explicit information on how the comparing constants depend on parameter α and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing α ↑ 2. In addition to these new estimates, this paper surveys recent progress in the study of notions of harmonicity, integral representation of harmonic functions, boundary Harnack inequality, conditional gauge and intrinsic ultracontractivity for symmetric stable processes. Here is a table of contents.

1. Introduction
2. Green function and Poisson kernel estimates

1. Estimates on balls
2. Estimates on boundedC ^1,1 domains
3. Estimates on boundedC ^1,1 open sets

1. Harmonic functions and integral representation
2. Two notions of harmonicity
3. Martin kernel and Martin boundary
4. Integral representation and uniqueness
5. Boundary Harnack principle
6. Conditional process and its limiting behavior
7. Conditional gauge and intrinsic ultracontractivity

     

Normalizers,Centralizers and Action Representability in Semi-Abelian Categories

We introduce the notion of normalizer as motivated by the classical notion in the category of groups. We show for a semi-abelian category ? that the following conditions are equivalent:

1. ? is action representable and normalizers exist in ?;
2. the category Mono(?) of monomorphisms in ? is action representable;
3. the category ?² of morphisms in ? is action representable;
4. for each category \(\mathbb {D}\) with a finite number of morphisms the category \({\mathbb {C}} ^{\mathbb {D}}\) is action representable.

Moreover, when in addition ? is locally well-presentable, we show that these conditions are further equivalent to:

1. ? satisfies the amalgamation property for protosplit normal monomorphism and ? satisfies the axiom of normality of unions;
2. for each small category \(\mathbb {D}\) , the category \({\mathbb {C}} ^{\mathbb {D}}\) is action representable.

We also show that if ? is homological, action accessible, and normalizers exist in ?, then ? is fiberwise algebraically cartesian closed.     

Noetherian type in topological products

The cardinal invariant Noetherian type Nt(X) of a topological space X was introduced by Peregudov in 1997 to deal with base properties that were studied by the Russian School as early as 1976. We study its behavior in products and box-products of topological spaces. We prove in Section 2:

1. There are spaces X and Y such that Nt(X×Y)< min{Nt(X), Nt(Y)}.
2. In several classes of compact spaces, the Noetherian type is preserved by the operations of forming a square and of passing to a dense subspace.

The Noetherian type of the Cantor Cube of weight \({\aleph _\omega }\) with the countable box topology, \({({2^{{\aleph _\omega }}})_\delta }\) , is shown in Section 3 to be closely related to the combinatorics of covering collections of countable subsets of \({\aleph _\omega }\) . We discuss the influence of principles like \({\square _{{\aleph _\omega }}}\) and Chang’s conjecture for \({\aleph _\omega }\) on this number and prove that it is not decidable in ZFC (relative to the consistency of ZFC with large cardinal axioms). Within PCF theory we establish the existence of an (?₄, ?₁)-sparse covering family of countable subsets of \({\aleph _\omega }\) (Theorem 3.20). From this follows an absolute upper bound of ?₄ on the Noetherian type of \({({2^{{\aleph _\omega }}})_\delta }\) . The proof uses a method that was introduced by Shelah in 1993 [33].     

Verallgemeinerungen eines Satzes von H. Steinhaus

The following result is due to H. Steinhaus [20]: “If A,B?R are sets of positive inner Lebesgue measure and if the function f: R x R→R is defined by f(x,y):=x+y (x,y?R), then the interior of f(A x B) is non void”. In this note there is proved, that the theorem of H. Steinhaus remains valid, if

1. R is replaced by certain topological measure spaces X, Y and a Hausdorff space Z,
2. f is a continuous function from an open set T?X x Y into Z and satisfies a special local (respectively global) solvability condition in T,
3. A?X is a set of positive outer measure, B?Y contains a set of positive measure and A x B?T.

     

The shortest augmenting path method for solving assignment problems — Motivation and computational experience

In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect:

we introduce this basic concept using matching theory

we present several efficient labeling techniques for constructing shortest augmenting paths

we show the relationship of this approach to several classical assignment algorithms

we present extensive computational experience for complete problems, and

we show how postoptimal analysis can be performed using this approach and naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems

     

Platitude d'une adherence schematique et lemme de Hironaka generalise

The main aim of this article is to prove the following:Theorem (Generalized Hironaka's lemma). Let X→Y be a morphism of schemes, locally of finite presentation, x a point of X and y=f(x). Assume that the following conditions are satisfied:

1. O _Y,y is reduced.
2. f is universally open at the generic points of the components of X_y which contain x.
3. For every maximal generisation y′ of y in Y and every maximal generisation x′ of x in X which belongs to X_y, we have dim_x, (X_y')=dim_x(X_y)=d.
4. X_y is reduced at the generic points of the components of X_y which contain x and (X_y)_red is geometrically normal over K(y) in x.

Then there exist an open neighbourhood U of x in X and a subscheme U₀ of U which have the same underlying space as U such that f₀:U₀\arY is normal (i.e. f₀ is a flat morphism whose geometric fibers are normal).     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Curvature Dimension Inequalities and Subelliptic Heat Kernel Gradient Bounds on Contact Manifolds

We study curvature dimension inequalities for the sub-Laplacian on contact Riemannian manifolds. This new curvature dimension condition is then used to obtain:

• Geometric conditions ensuring the compactness of the underlying manifold (Bonnet–Myers type results);
• Volume estimates of metric balls;
• Gradient bounds and stochastic completeness for the heat semigroup generated by the sub-Laplacian;
• Spectral gap estimates.