Primitives for asynchronous list compression

In this paper we study the problem of asynchronous processors traversing a list with path compression. We show that if an atomic splice operation is available, the worst-case work forp processors traversing a list of length h is (np ^1/2). The splice operation can be generalized to removek elements from the list. For thek-splice operation the worst-case work is (np ^1/ k+1).This research was supported by an NSF Presidential Young Investigator Award CCR-8657562, Digital Equipment Corporation, NSF CER Grant CCR-861966, and NSF/Darpa Grant CCR-8907960. A preliminary version of this paper was presented at the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures.     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n–2+ [lgn], andW _k (n) = n + (k–1)lg n +O(1) for all fixed k 3. In this paper we studyW _k (n), the minimax complexity of selecting thek largest, when tests of the form Isx _i the median of {x _i ,x _j ,x _t }? are also allowed. It is proved thatW₂(n) =n–2+ [lgn], andW _k (n) =n + (k–1)lg₂ n +O(1) for all fixedk3.This research was supported in part by the National Science Foundation under Grant No. DCR-8308109.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

On the boundedness properties of a perturbed nonlinear system

It is shown that certain asymptotic equivalence hypotheses on the equationsu(t) = F(t, u(t))+G(t, u(t)) andv(t) = F(t, v(t)) imply that uniform boundedness in the second equation induces eventual uniform boundedness in the first. Also, under these hypotheses, a characterization is given of the unbounded solutions of the first equation.     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

On parsing two-level grammars

Summary Making use of the fact that two-level grammars (TLGs) may be thought of as finite specification of context-free grammars (CFGs) with infinite sets of productions, known techniques for parsing CFGs are applied to TLGs by first specifying a canonical CFG G — called skeleton grammar — obtained from the cross-reference of the TLG G. Under very natural restrictions it can be shown that for these grammar pairs (G, G) there exists a 1 — 1 correspondence between leftmost derivations in G and leftmost derivations in G. With these results a straightforward parsing algorithm for restricted TLGs is given.     

Sur les générateurs algébriques et linéaires

Résumé Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L et tout générateur algébrique L, il existe une transduction rationnelle fonctionnelle et fidèle telle que L=(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur séquentiel pour Lin.

---

Algebraic and linear generators

Summary We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L and every algebraic generator L, there exists a faithful rational function such that L=(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a sequential generator for Lin.

     

On reducing the number of stack symbols in a PDA

Two transformations are presented which, for any pushdown automaton (PDA)M withn states andp stack symbols, reduce the number of stack symbols to any desired numberp greater than one. The first transformation preserves deterministic behavior and produces an equivalent PDA witho(np/p) states. The second construction, using a technique which introduces nondeterminism, produces an equivalent PDA withO(np/p) states. Both transformations are essentially optimal, the former among determinism-preserving transformations, the latter among all transformations.This research was supported in part by the National Science Foundation under Grants MCS 76-10076 and MCS 76-10076A01 and by the Stiftung Volkswagenwerk under Grant No. II/62 325.     

Towards separating nondeterminism from determinism

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) ^1/k ). This implies, for example that for any positive integer,l,l k, there is a language accepted by an ^l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n ^l ) andO((logn) ^l ) respectively for anyl. Such a result is not provable by direct diagonalization because we do not have time to simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.Supported by NSF Grant No. MCS-8105557     

Exponential Queuing Network with Dependent Servicing, Negative Customers, and Modification of the Customer Type

The open exponential queuing network with negative customers (G-network) was considered.For each arriving customer, given was a set of its random parameters such as the route defining the sequence of network nodes passed by the customer, route length, size, and servicing duration at each stage of the route. It was assumed that the negative customer arriving to the sth node with the probabilities _s and _s ⁺ either kills the positive customer in a randomly chosen server or does not affect it at all and with the probability _s ^– =1 – _s – _s ⁺ transforms it into a negative customer which after an exponentially distributed time arrives to the sth node with the given probability. The multidimensional stationary probability distribution of the network states was proved to be representable in the multiplicative form.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define (P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy . HeresQ denotes a scaling ofQ by the factors, andQ,Q are some translates ofQ. This function gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.)For integerk 3, define (k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with (P, Q) (k). Among other results, we prove that 2.118 ... <-(3) 2.25 and (k) = 1 + (k ^–2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes (T, P) among triangles. However, in linear time we can find a trianglet with (t, P)<-2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.Work of all authors was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Rudolf Fleischer and Kurt Mehlhorn acknowledge also DFG (Grant SPP Me 620/6). Chee Yap acknowledges also DFG (Grant Be 142/46-1) and NSF (Grants DCR-84-01898 and CCR-87-03458). This research was performed when Günter Rote and Chee Yap were at the Freie Universität Berlin.     

Asymptotic component densities in Programmable Gate Arrays realizing all circuits of a given size

A Programmable Gate Array (PGA) is modeled as a square grid. Some grid nodes are processing nodes containing electrical elements. The rest are switching nodes capable of connecting wires incident on them. Two possible types of switching nodes are considered. In vertex connectivity each switching node can connect only one pair of wires. In edge connectivity each switching node can simultaneously connect two pairs of wires. The PGA must be capable of implementing any graph of size at mostk and degree at most 4. We prove tight bounds on the highest achievable density of processing nodes.In edge connectivity the highest achievable density is (1/k). In vertex connectivity the highest achievable density is (1/k ²). If the grid is augmented by the diagonal edges, then the highest achievable density is (1/k) even with vertex connectivity. These extend known results for embedding graphs in grids.Small graphs of degree 1 are further examined. Fork=2 andk=3 the highest density of processing nodes equals the highest density of parked cars in a square parking lot where each car can exit. Both densities are two-thirds. Fork=4 the highest density is one-half.This work was supported in part by NSF Grants NCR-8903288 and IAI-9005849.     

Fabrication aspects in the optimum design of welded structures

A brief survey of selected literature shows that fabrication aspects play an important role in the economic design of welded structures. Fabrication costs and production requirements should be considered in the optimum design procedure.In a detailed numerical example some optimal solutions are determined for a simple box beam having transverse diaphragms and carrying a fluctuating load. In the objective function the material and fabrication costs are taken into account. The cost function formula enables the investigation of structural solutions for wide ranges of cost factors.Constraints on fatigue strength, local buckling of plate elements, shear stress and deflection are considered. Based on the active constraints, the cost function may be expressed as a function of the beam height as the main variable. The minimum cross-sectional area, volume and cost designs are calculated.Concerning the fillet welds of the transverse diaphragms two solutions are considered: (1) without post treatment with a lower fatigue strength; (2) with post toe burr grinding with improved fatigue strength. In the second case the cost of post treatment is also included in the cost function.A comparison of the above solutions shows that the post treatment of transverse fillet welds may be economic despite of the additional cost.Notation A cross-sectional area - A _f cross-sectional area of a flange - a _w fillet weld size - b beam width - c ₁ , c₂ distances of diaphragms from the support - E modulus of elasticity - G = V mass - h web height - I _x moment of inertia - K total cost - K _m , K _f material and fabrication cost, respectively - k _m , k _f material and fabrication cost factor, respectively - L span length - L _w weld length - M bending moment - N number of cycles - n number of diaphragms - n ₁ number of diaphragms with post treated welds - p intensity of normal load - Q shear force - S _x statical moment - T time - t _f , t _w /2 flange and web thickness, respectively - V volume - W _x section modulus - W ₀ required section modulus - deflection - limiting plate slenderness of webs - difficulty factor - _f limiting plate slenderness of the compression flange - = k _f /k_m ratio of cost factors - number of structural elements - v Poisson's ratio - density - normal stress - _f fatigue strength - shear stress - _f fatigue strength in shear - _w shear stress in welds     

A Low-Cost Fault-Tolerant Structure for the Hypercube

We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and almost fully tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations—expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired—the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.     

On the usefulness of bifaithful rational cones

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL, from which we can obtainL by faithful rational transduction, for any languageL, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction such thatL is the image ofL . We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as , very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

A Hyperbase for Binary Lattice Hyperidentities

We define an identity to be hypersatisfied by a variety V if, whenever the operation symbols of V, are replaced by arbitrary terms (of appropriate arity) in the operations of V, the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a V hyperidentity. For example, the identity x + x y = x (x + y) is hypersatisfied by the variety L of all lattices. A proof of this consists of a case-by-case examination of { + , } {x, y, x y, x y}, the set of all binary lattice terms. In an earlier work, we exhibited a hyperbase ^L for the set of all binary lattice (or, equivalently, quasilattice) hyperidentities of type 2, 2. In this paper we provide a greatly refined hyperbase _L . The proof that _L is a hyperbase was obtained by using the automated reasoning program Otter 3.0.4.     

Simple adaptive stabilization of output feedback stabilizable distributed parameter systems

We show that the simple universal adaptive control lawu(t)=N(k(t))y(t)=|y(t)| ², withN(k)=(logk) cos((logk)) and 3+<1, stabilizes all detectable and stabilizable infinite dimensional systems of Pritchard-Salamon type which are externally stabilized by somescalar output feedback. The same controller is also shown to stabilize time varying systems satisfying the same type of output feedback stabilizability.     

A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.