An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*

Given a spanning tree T of some graph G, the problem of minimum spanning tree verification is to decide whether T = MST(G). A celebrated result of Komlós shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is e in the MST of T ∪{e}?”, where the tree T is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires Ω(mα(m,n)) time, where α(m,n) is the inverse-Ackermann function and n is the size of the tree. On the other hand, we show that if the weights of T are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time. * A preliminary version of this paper appeared in the proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 155–163. † This work was supported by Texas Advanced Research Program Grant 003658-0029-1999, NSF Grant CCR-9988160, and an MCD Graduate Fellowship.     

Charakterisierung nüchterner Räume

The categorySob of sober spaces is a full isomorphismclosed reflective subcategory of the categoryT _o of T_o-spaces (and continuous maps).SobT _o is characterized by: (i) every universal morphism of the adjunction is aT _o-epic embedding, and (ii) everyT _o-epic embedding, whose domain is sober, is a homeomorphism.Sob is the epi-reflective hull of the Sierpinski space D inT _o. A subspace of a sober space is sober, iff it is b-closed. A space is sober, iff it is a b-closed subspace of a power of D.     

Fcfs-scheduling in a hard real-time environment under rush-hour conditions

We investigate some real-time behaviour of a (discrete time) single server system with FCFS (first come first serve) task scheduling under rush-hour conditions. The main result deals with the probability distribution of a random variable SRD(T), which describes the time the system operates without violating a fixed task service time deadlineT.Relying on a simple general probability model, asymptotic formulas concerning the mean and the variance of SRD(T) are determined; for instance, if the average arrival rate is larger than the departure rate, the expectation of SRD(T) is proved to fulfilE[SRD(T)]=c ₁+O(T ^–3) forT, wherec ₁ denotes some constant. If the arrival rate equals the departure rate, we findE[SRD(T)]c ₂ T ⁱ for somei2.     

Matrices, machines and behaviors

Sabadini, Walters and others have developed a categorical, machine based theory of concurrency in which there are four essential aspects: a distributive category of data-types; a bicategory Mach whose objects are data types, and whose arrows are input-output machines built from data types; a semantic category (or categories) Sem, suitable to contain the behaviors of machines, and a functor, behavior: MachSem. Suitable operations on machines and semantics are found so that the behavior functor preserves these operations. Then, if each machine is decomposable into primitive machines using these operations, the behavior of a general machine is deducible from the behavior of its parts. The theory of non-deterministic finite state automata provides an example of the paradigm and also throws some light on the classical theory of finite state automata.We describe a bicategory whose objects are natural numbers, in which an arrow M: np is a finite state automaton with n input states, p output states, and some additional internal states; we require that no transitions begin at output states or end at input states. A machine is represented by an q+n by q+p matrix. The bicategory supports additional operations: non-deterministic choice, parallel interleaving, and feedback. Enough operations are imposed on machines to show that each machine may be obtained from some atomic ones by means of the operations.The semantic category is the (Bloom-Ésik) iteration theory Mat _(X whose objects are natural numbers and whose arrows from n to p are n×p matrices with entries in the semiring of languages. The behavior functor associates to a machine M: np a matrix |M| of languages, one language to each pair of input and output states. Behavior preserves composition, feedback, takes non-deterministic choice to union, and parallel-interleaving to shuffle. Thus, behavior gives a compositional semantics to a primitive notion of concurrent processes.This work has been supported by the Australian Research Council, by CEC under grant number 6317, ASMICS II, by Italian MURST, and by the Italian CNR.Visit to Sydney supported by a grant from the Australian Research Council.Presented at the European Colloquium of Category Theory, Tours, France, 25–31 July 1994.     

FACTORIZATION OF UNBOUNDED THIN AND COTHIN OPERATORS

Abstract

Let X and Y be normed spaces and T: D(T) ? X → Y a linear operator. Following R.D. Neidingcr [N1] we recall the Davis, Figiel, Johnson, Pelczynski factorization of T corresponding to a parameter p (1 ≤ p ≤ ∞) and apply the corresponding factorization result in [N1] to unbounded thin operators. Properties equivalent to ubiquitous thinness arc derived. Defining an operator T to be cothin if its adjoint is thin, a dual factorization result for cothin operators is obtained, where for each 1 < p < ∞, the intermediate space in the factorization is cohereditarily l_p. This result is shown to hold more generally for the cases when T is either partially continuous or closable; in particular, such operators are strictly cosingular. A condition for a closable weakly compact operator to be strictly cosingular follows as a corollary.     

Irreducible filters and sober spaces

A filterF on a convergence space is called irreducible, iff the set convF of convergence points ofF belongs toF. A space is sober, iff for every irreducible filterF there is a unique point x with convF=conv x. The categorySob-Conv of sober convergence spaces is a full productive, but not a reflective subcategory of the categoryConv of convergence spaces and continuous maps. For a topological space (X,t) the following are equivalent: (i) for every irreducible filterF on (X,t) there is a point x withF=x (ii) (X,t) is both sober and T_D (iii) every subspace of (X,t) is sober (iv) every topological space finer than (X,t) is sober (v) whenever (Y,s) is a T_o-space whose latticeO(Y,s) of open sets is isomorphic toO(x,t), then (Y,s)(X,t). The categorySob-T ₁ß of sober T₁-spaces is the greatest epi-reflective subcategory ofTop consisting of sober spaces, moreoverSob-T ₁ß is a dis-connectedness in the sense of Preuß- Arhangelskii-Wiegandt (generated by all irreducible spaces), henceSob-T ₁ is (extremal epi)-reflective inTop. It is strictly between T₁ and T₂ and different from various sorts of weak Hausdorffness discussed in the literature.     

Banach's Fixed-Point Theorem as a base for data-type equations

For a categoryK of data types, solutions of recursive data-type equationsX T(X), whereT is an endofunctor ofK, can be constructed by iteratingT on the unique arrowT1 1. This is well-known forK enriched over complete posets and forT locally continuous (an application of the Kleene Fixed-Point Theorem). We prove this forK enriched over complete metric spaces and forT contracting (an application of the Banach Fixed-Point Theorem). Moreover, we prove that each such recursive equation has a unique solution. Our results generalize the approach of P. America and J. Rutten.Dedicated to Dieter Pumplün on the occasion of his 60th birthday     

On Representing Concepts in Finite Models

We present a method of transferring Tarski's technique of classifying finite order concepts by means of truth‐definitions into finite mode theory. The other considered question is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree ≤ o′. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl(T) as the set of all sentences true in almost all finite models for T. For theories of sufficiently large models our version of Tarski's technique becomes practically the same as the classica one. We investigate also degrees of undecidability for theories of sufficiently large finite models. We prove for some special theory ST that its degree is stronger than 0′ but still not more than Σ⁰₂.     

Families of cuts with the MFMC-property

A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class has the MFMC-property if and only if it is one of (i), (ii), (iii).     

Dense codense predicates and the NTP2

We show that if T is any geometric theory having the NTP₂ then the corresponding theories of lovely pairs of models of T and of H‐structures associated to T also have the NTP₂. We also prove that if T is strong then the same two expansions of T are also strong.     

Covering in the lattice of equational theories and some properties of term finite theories

For countable languages, we completely describe those cardinals κ such that there is an equational theory which covers exactly κ other equational theories. For this task understanding term finite theories is helpful. A theoryT isterm finite provided {ψ:Tτϕ≈ψ} is finite for all terms ϕ. We develop here some fundamental properties of term finite theories and use them, together with Ramsey's Theorem, to prove that any finitely based term finite theory covers only finitely many others. We also show that every term finite theory possesses an independent base and that there are such theories whose pairwise joins are not term finite. The paper was written with the support of NSF Grant MCS-80-01778. Presented by B. Jónsson. Received July 22, 1980. Accepted for publication in final form March 19, 1981.     

Finding model-companions via the skeleton

We present an analysis on the existentially closed (e.c.) structures for some theoryT in a rather complete categorical setting. The central notion of the skeleton ofT is defined. We formulate conditions on the skeleton which limit the number of e.c. structures forT, thereby ensuring the existence of a model-companion ofT. A new (purely categorical) proof of the uniqueness of the atomic structure is given for theories having the joint-embedding-property (JEP).As an application it is shown that a finitely generated universal Horn class possesses a model-companion — a resuilt that was proved earlier by a different method.Presented by Stanley Burris.     

Nearly Model Complete Theories

A theory T of a language L is 1-model complete (nearly model complete) iff for every formula ρ of L there is a formula ? (χ) of L which is a ??-formula (a Boolean combination of universal formulas) such that T ? ?x [??θ]. The main results of the paper give characterizations of nearly model complete theories and of 1-model complete theories. As a consequence we obtain that a theory T is nearly model complete iff whenever ?? is a model of T and ???₁??, then T ∪ Δ¹_?? is a complete L(A)-theory, where Δ¹_?? is the 1-diagram of ??. We also point out that our main results extend to (n + l)-model complete and nearly ra-model complete theories for all n > 0.     

VARIETAL HULLS OF FUNCTORS

Abstract

The well known characterizations of equational classes of algebras with not necessaryly finitary operations by FELSCHER [6.7] and of categories of A-algebras for algebraic theories A in the sense of LINTON [10], esp., by means of their forgetful functors are the foundations of a concept of varietal functors U:K → L over arbitrary basecategories L. They prove to be monadic functors which satisfy an additional HOM-condition [17]. (In the case L = Set this condition is always fulfilled, see LINTON [11].)

Contrary to monadic functors, varietal functors are closed under composition. Pleasent algebraic properties of the base-category L can be ‘lifted’ along varietal functors, such as e.g. factorization properties, (co-) completeness, classical isomorphism theorems, etc.

By means of the well known EILENBERG-MOORE-algebras there is a universal monadic functor U^T:L ^T → L for any functor U: K → L, having a left adjoint F (T: = UF). But, in general, UT is not varietal. Under some suitable conditions, however it is possible, to construct a canonical varietal functor ?:R → L, the varietal hull of U. This hull has much more interesting (algebraic) properties than the EILENBERG-MOORE construction. Moreover, results of BANASCHEWSKI-HERRLICH [2] are extended.     

Bimatroids and invariants

A bimatroid B between the sets S and T incorporates the combinatorial exchange properties of relative invariants of the special linear group acting on a vector space and its dual, or equivalently, when S and T are finite, the exchange properties fo nonsingular minors of a matrix whose columns and rows are indexed by S and T. A rather simple idea, basically that of adjoining an identity matrix, yields a construction which produces, from the bimatroid B, a matroid R on the disjoint union S T which encodes all the structure of B. This gives a method of translating matroidal concepts and results into the language of bimatroids. We also define an analog of matrix multiplication for bimatroids: This operation generalizes matroid induction and affords another combinatorial interpretation of a linear transformation.     

Finite groups in which normality is a transitive relation

Let G be a finite group. We say that G is a T₀-group, if its Frattini quotient group G/F(G)G/\Phi (G) is a T-group, where by a T-group we mean a group in which every subnormal subgroup is normal. We determine the structure of a non T₀-group G all of whose proper subgroups are T₀-groups.     

Smith Normal Form and acyclic matrices

An approach, based on the Smith Normal Form, is introduced to study the spectra of symmetric matrices with a given graph. The approach serves well to explain how the path cover number (resp. diameter of a tree T) is related to the maximal multiplicity MaxMult(T) occurring for an eigenvalue of a symmetric matrix whose graph is T (resp. the minimal number q(T) of distinct eigenvalues over the symmetric matrices whose graphs are T). The approach is also applied to a more general class of connected graphs G, not necessarily trees, in order to establish a lower bound on q(G).     

Lower bounds for a polynomial in terms of its coefficients

We determine new sufficient conditions in terms of the coefficients for a polynomial ${f\in \mathbb{R}[\underline{X}]}We determine new sufficient conditions in terms of the coefficients for a polynomial f ? \mathbbR[X]{f\in \mathbb{R}[\underline{X}]} of degree 2d (d ≥ 1) in n ≥ 1 variables to be a sum of squares of polynomials, thereby strengthening results of Fidalgo and Kovacec (Math. Zeitschrift, to appear) and of Lasserre (Arch. Math. 89 (2007) 390–398). Exploiting these results, we determine, for any polynomial f ? \mathbbR[X]{f\in \mathbb{R}[\underline{X}]} of degree 2d whose highest degree term is an interior point in the cone of sums of squares of forms of degree d, a real number r such that f − r is a sum of squares of polynomials. The existence of such a number r was proved earlier by Marshall (Canad. J. Math. 61 (2009) 205–221), but no estimates for r were given. We also determine a lower bound for any polynomial f whose highest degree term is positive definite.     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Liftungen von Tripeln

For triplesS andT in a categoryOl, J. Beck [1] has shown the equiva-lence of a distributive law 1:TSST with a lifting ofT into the category ofS-algebras. Now in this paper it is proved that such a di-ributive law is also equivalent with a lifting of S into the T-Kleisli-category. Distributive laws of mixed type are also considered. Each of the distributive laws GTTG and TGGT (with T a triple and G a cotriple inOl) produces a pair of dual liftings.