Birth times,death times and time substitutions in Markov chains

Summary Given a Markov chain (X _n ) _n0, random times are studied which are birth times or death times in the sense that the post- and pre- processes are independent given the present (X _–1, X ) at time and the conditional post- process (birth times) or the conditional pre- process (death times) is again Markovian. The main result for birth times characterizes all time substitutions through homogeneous random sets with the property that all points in the set are birth times. The main result for death times is the dual of this and appears as the birth time theorem with the direction of time reversed.Part of this work was done while the author was visiting the Department of Mathematics, University of California at San DiegoThe support of The Danish Natural Science Research Council is gratefully acknowledged     

Opérateurs de mise en mémoire et traduction de Gödel

Résumé En-calcul, la stratégie de réduction à gauche (appel par nom) a, comme on sait, de bonnes propriétés mathématiques; en particulier, elle termine toujours si on l'applique à un terme normalisable. Mais, avec cette stratégie, l'argument d'une fonction est recalculé à chaque utilisation.Pour éviter ce défaut, on définit la notion «d'opérateur de mise en mémoire» (pour un type de données). SiT est un opérateur de mise en mémoire, pour les entiers par exemple, on remplace l'évaluation, par réduction gauche, de (où est un entier et un -terme quelconque) par celle deT; et celle-ci revient à ramener d'abord à une forme réduite ₀, puis à appliquer à ₀. On a donc ainsi simulé «l'appel par valeur» dans la stratégie de réduction à gauche.Le théorème principal (Corollaire du Théorème 4.1) montre que, dans un 1-calcul typé du second ordre, en utilisant la traduction de Gödel de la logique classique en logique intuitionniste, on peut trouver un type (spécification) très simple pour les opérateurs de mise en mémoire. Il donne donc aussi un moyen d'obtenir ces opérateurs, à savoir de démontrer ce type dans le calcul des prédicats intuitionniste du second ordre.

---

In-calculus, the strategy of leftmost reduction (call-by-name) is known to have good mathematical properties; in particular, it always terminates when applied to a normalizable term. On the other hand, with this strategy, the argument of a function is re-evaluated at each time it is used.To avoid this drawback, we define the notion of storage operator, for each data type. IfT is a storage operator for integers, for example, let us replace the evaluation, by leftmost reduction, of (where is an integer, and any-term) by the evaluation oft. Then, this computation is the same as the following: first compute up to some reduced form ₀, and then apply to ₀. So, we have simulated call-by-value evaluation within the strategy of leftmost reduction.The main theorem of the paper (Corollary of Theorem 4.1) shows that, in a second order-calculus, using Gödel's translation of classical intuitionistic logic, we can find a very simple type (or specification) for storage operators. Thus, it gives a way to get such operators, which is to prove this type in second order intuitionistic predicate calculus.

     

Multi-E-Reflective and Bireflective Subcategories of Partial Algebras

A category PAlg() of partial algebras of a given type will be introduced. Then we will present a categorical concept in order to characterize those subcategories of PAlg(), which are closed under the formation of various kinds of subobjects. We will also give a characterization for bireflective subcategories of PAlg(), which enables us to show, that the subcategory Alg() consisting of all total algebras of type is the smallest bireflective subcategory of PAlg().     

The Discrete Spectrum Asymptotics with Respect to a Large Coupling Constant under Strong Nonnegative Perturbations

Let A be a self-adjoint operator, let (, ) be an inner gap in the spectrum of the operator A, and let B(t) = A + tW ^* W, where the operator W(A – iI)^-1 is not necessarily bounded. Conditions are obtained under which the spectrum of B(t) in (, ) is discrete. Let N(, A, W, ), (, ), > 0, be the number of eigenvalues of the operator B(t) passing the point (, ) as t increases from 0 to . The asymptotics of N(, A, W, ) as + is obtained in terms of the spectral asymptotics of a certain self-adjoint compact operator. Bibliography: 5 titles.     

τ-Pseudocompact Mappings

We consider the problem of extending the notion of -pseudocompactness from spaces to continuous mappings, obtain conditions under which the product of -pseudocompact mappings is -pseudocompact. Since any space X can be considered as a continuous mapping from X into a singleton, we obtain consequences of the theorems on multiplicativity of -pseudocompactness for spaces. Thus, we study the notion of -pseudocompact mapping and some its properties similar to those of a pseudocompact space as well as consequences of the obtained assertions for spaces.     

Algebraic Properties of the Mikusiński Convolution Algebra

Let M be the space of all continuous, complex valued functions defined on [0, ]. This, with the convolution operation (^f*g)(t) = ₀ ^{t f}(t–)g() d yields a commutative, associative algebra. A new proof that M is a Jacobson radical algebra is given. The ideal structures of M and its Dorroh extension to an algebra, M¹, with unity are investigated. The algebraic properties of M are used to obtain new proofs of existence and uniqueness of solutions for certain integral and integro-differential equations.     

Hypercubic 4 and 5-Designs from Double-Error-Correcting BCH Codes

An ordered orthogonal array OOA(, k, n) is a binary 2 ^k × n matrix with the property that for each complete -set of columns, each possible -tuple occurs in exactly 2 ^k– rows of those columns (for definition of a complete -set, see below). Constructions of OOA(, k, n) for = 4 and = 5 are given.     

Estimates for lebesgue constants in dimension two

Summary Let D denote the interior of a piecewise regular curve of R² having a point with Gauss curvature different from zero. We show that the Lebesgue constants L ^D relative to D behave like ^1/2 as .     

Discrete Spectrum of Differential Operators in Spectral Gaps under Nonnegative Perturbations of High Order

Let A be a self-adjoint elliptic second-order differential operator, let (, ) be an inner gap in the spectrum of A, and let B(t) = A + tW ^* W, where W is a differential operator of higher order. Conditions are obtained under which the spectrum of the operator B(t) in the gap (, ) is either discrete, or does not accumulate to the right-hand boundary of the spectral gap, or is finite. The quantity N(, A, W, ), (, ), > 0 (the number of eigenvalues of the operator B(t) passing the point (, ) as t increases from 0 to ) is considered. Estimates of N(, A, W, ) are obtained. For the perturbation W ^* W of a special form, the asymptotics of N(, A, W, ) as + is given. Bibliography: 5 titles.     

Das Zeitverhalten von einfachen offenen exponentiellen Warteschlangensystemen mit unendlich vielen Warteplätzen

Zusammenfassung Die zeitabhängige (instationäre) Lösung für die Zustandswahrscheinlichkeiten und für einige Kenngrößen von Warteschlangensystemen mit einer Bedienungsstation, unendlich vielen Warteplätzen, exponentiellem Zu- und Abgang und beliebigem Anfangszustand wird bestimmt. Die ZustandswahrscheinlichkeitenP _v (), d. h. die Wahrscheinlichkeiten für Einheiten im System zur Zeit, ergeben sich als Integrale, in denen modifizierteSessel-Funktionen 1. Art auftreten. Der ErwartungswertL () und die VarianzV() der Zahl von Einheiten im System lassen sich als Integrale darstellen, in denen nur die ZustandswahrscheinlichkeitP ₀() auftritt.Für<1 und erreichen die Systeme einen stationären Zustand (für den die Lösung bekannt ist); für1 und giltP _v ()0 für alle, L(),V().Ist>1, dann wachsenL() undV() für große linear mit; ihre Asymptoten werden berechnet. Ist=1, dann wachsenL() und die Standardabweichung() für große mit ; einfache Näherungsformeln werden gefunden.

---

Summary The time dependent solution is determined for the state probabilities and for some characteristic values of queuing systems with a single server, an infinite number of waiting places, exponentially distributed inter-arrival and service times, and any initial state. The state probabilitiesP _v (), i.e. the probabilities for units in the system at time, are given in the form of integrals in which modifiedBessel functions of the first kind occur. Integrating the state probalityP ₀() over leads to the meanL() and the varianceV() of the number of units in the system.For<1 and the systems tend to a steady state (for which the solution is known); for1 and we haveP _v ()0 for all, L(),V().If>1 asymptotic expansions for large are found givingL() andV() proportional to. If=1 simple approximate formulas for large are obtained givingL() and the standard deviation() proportional to .

---

---

Vorgel. v.:J. Nitsche.     

On the asymptotic behaviour of first passage times for transient random walk

Summary Let _x denote the time at which a random walk with finite positive mean first passes into (x, ), wherex0. This paper establishes the asymptotic behaviour of Pr { _x >n} asn for fixedx in two cases. In the first case the left hand tail of the step-distribution is regularly varying, and in the second the step-distribution satisfies a one-sided Cramér type condition. As a corollary, it follows that in the first case Pr { _x >n}/Pr{ ₀ >n} coincides with the limit of the same quantity for recurrent random walk satisfying Spitzer's condition, but in the second case the limit is more complicated.     

The Milnor–Totaro Theorem for Space Polygons

If denotes the curvature and the torsion of a closed, generic, and oriented polygonal space curve X in , then we show that _X (² + ²) ds = _X ds + _X | | ds > 4 if is positive. We also show that _X (² + ²) ds 2n if no four consecutive vertices lie in a plane and X has linking number n with a straight line. These extend theorems of Milnor and Totaro.     

C r -finite elements of Powell-Sabin type on the three direction mesh

Let be the triangulation generated by a uniform three direction mesh of the plane. Let ₆ be the Powell-Sabin subtriangulation obtained by subdividing each triangleT by connecting each vertex to the midpoint of the opposite side.Given a smooth functionu, we construct a piecewise polynomial function C ^r (²) of degreen=2r (resp. 2r+1) forr odd (resp. even) in each triangle of ₆, interpolating derivatives ofu up to orderr at the vertices of.     

Über den algorithmischen Nachweis von Ungleichungen I

We shall develop a method to prove inequalities in a unified manner. The idea is as follows: It is quite often possible to find a continuous functional : ⁿ , such that the left- and the right-hand side of a given inequality can be written in the form (u)(v) for suitable points,v=v(u). If one now constructs a map ^{n n} , which is functional increasing (i.e. for each x ⁿ (which is not a fixed point of ) the inequality (x)<((x)) should hold) one specially gets the chain (u)( u))( ²(u))... ⁿ (u)). Under quite general conditions one finds that the sequence { ⁿ (u)} _n converges tov=v(u). As a consequence one obtains the inequality (u)(v).     

Ideals of the semigroup of ultrafilters of a topological group

We construct two new series of closed left ideals of the semigroup of ultrafilters of a topological group (G, ). The first series gives a disjunctive decomposition of -absorbing ultrafilters. Under certain restrictions on the topology of the group (G, ), the second series gives a disjunctive decomposition of the semigroup of free ultrafilters. For a nondiscrete metrizable topological group (G, ), we construct a large free subsemigroup of the semigroup .Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 4, pp. 506–511, April, 1995.     

The nth reduced BKP hierarchy, the string equation and BW 1+∞-constraints

We study the BKP hierarchy and its n-reduction, for the case that n is odd. This is related to the principal realization of the basic module of the twisted affine Lie algebra % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqaqpepeea0dXdb9aqVe% 0larpepe0lb9cs0-LqLs-Jarpepeea0-qqVe0Firpepa0xar-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaadaWfGaqaaiGaco% hacaGGSbWaaSbaaSqaaiaac6gaaeqaaaqabKqaGhaacqWIh4ETaaGc% daahaaWcbeqaaiaacIcacaaIYaGaaiykaaaaaaa!3B2F!\[\mathop {{\mathop{\rm sl}\nolimits} _n }\limits^ ^{(2)} \]. We show that the following two statements for a BKP function are equivalent: (1) is is n-reduced and satisfies the string equation, i.e., L _-1=0, where L _-1 is an element of some natural Virasoro algebra. (2) satisfies the vacuum constraints of the BW ₁₊ algebra. Here BW ₁₊ is the natural analog of the W ₁₊ algebra, which plays a role in the KP case.The research of Johan van de Leur is financially supported by the Stichting Fundamenteel Onderzoek der Materie (FOM).     

Stability and uniqueness of the solution of the inverse kinematic problem of seismology in higher dimensions

The following inverse kinematic problem of seismology is considered. In the compact domain M of dimension ,2 with the metric, we consider the problem of constructing a new metricdu=nds according to the known formula where ,M and K_, is the geodesic in the metric du, connecting the points , . One proves uniqueness and one obtains a stability estimate, where the refraction indices n₁, n₂ are the solutions of the inverse kinematic problem, constructed relative to the functions ₁, ₂, respectively, is the differential form on M×Mwhere =₂–₁,.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 84, pp. 3–6, 1979.     

On Idempotent Ranks of Semigroups of Partial Transformations

A subset U of a semigroup S is a generating set for S if every element of S may be written as a finite product of elements of U. The rank of S is the size of a minimal generating set of S, and the idempotent rank of S is the size of a minimal generating set of S consisting of idempotents in S. A partition of a q-element subset of the set X_n={1,2,..., n} is said to be of type if the sizes of its classes form the partition of q n. A non-trivial partition of a positive integer q consists of k < q elements. For a non-trivial partition of q n, the semigroup S(), generated by all the transformations with kernels of type , is idempotent-generated. It is known that if is a non-trivial partition of n, that is, S() consists of total many-to-one transformations, then the rank and the idempotent rank of S() are both equal to max{ⁿ_d, N()}, where N() is the number of partitions of X_n of type . We extend this result to semigroups of partial transformations, and prove that if is a non-trivial partition of q < n, then the rank and the idempotent rank of S() are both equal to N().     

Isometries of symmetric operator spaces associated with AFD factors of typeII and symmetric vector-valued spaces

If is a surjective isometry of the separable symmetric operator spaceE(M, ) associated with the approximately finite-dimensional semifinite factorM and if · _E(M,) is not proportional to · _{L 2}, then there exist a unitary operatorUM and a Jordan automorphismJ ofM such that(x)=UJ(x) for allxME(M, ). We characterize also surjective isometries of vector-valued symmetric spacesF((0, 1), E(M, )).Research supported by the Australian Research Council     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.