The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.Richard Cole was supported in part by NSF Grants DCR-84-01633 and CCR-8702271, ONR Grant N00014-85-K-0046 and by an IBM faculty development award. Uzi Vishkin was supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046, by the Applied Mathematical Science subprogram of the office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities.     

On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation

This paper characterizes the class of closed and (M, N)-recognizable languages in terms of certain structural aspects of relevant automata. This characterization leads to algorithms that effectively compute the supremal (M, N)-recognizable sublanguage of a given language. One of these algorithms is used, in an alternating manner with an algorithm which yields the supremal (∑_u, N)-invariant resulting algorithm is proved. An example illustrates the use of these algorithms. This research was supported in part by the Air Force Office of Scientific Research under Grant No. AFOSR-86-0029, in part by the National Science Foundation under Grant No. ECS-8412100, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract No. F49620-86-C-0045     

Analysis of an identification algorithm arising in the adaptive estimation of Markov chains

We investigate an algorithm applied to the adaptive estimation of partially observed finite-state Markov chains. The algorithm utilizes the recursive equation characterizing the conditional distribution of the state of the Markov chain, given the past observations. We show that the process “driving” the algorithm has a unique invariant measure for each fixed value of the parameter, and following the ordinary differential equation method for stochastic approximations, establish almost sure convergence of the parameter estimates to the solutions of an associated differential equation. The performance of the adaptive estimation scheme is analyzed by examining the induced controlled Markov process with respect to a long-run average cost criterion. This research was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860 and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Proof rules for the programming language Euclid

Summary In the spirit of the previous axiomatixation of the programming language Pascal, this paper describes Hoare-style proof rules for Euclid, a programming language intended for the expression of system programs which are to be verified. All constructs of Euclid are covered except for storage allocation and machine dependencies.Supported by the Defense Advanced Research Projects Agency under contract DAHC-15-72-C-0308Supported in part by the National Science Foundation under grant MCS-76-86089 and the Joint Services Electronics Program monitored by the Air Force Office of Scientific Research under contract F44620-76-C-0061Supported in part by a Research Leave Grant from the University of Toronto and a grant from the National Research Council of Canada.Supported in part by the Defense Advanced Research Projects Agency under contract DAHC 73-C-0368. The views expressed are those of the authors     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

LIGA and LIGA-like processing with high energy photons

High energy X-rays, in the present case photons near 20,000 eV, can be used in LIGA-like processing. Heating problems with this type of photon flux can be avoided by proper filtration via transmission filters. The exposure of PMMA with high energy photons leads to cost effective exposures with full cost recovery estimates of $0.10 per square centimeter at 200 μm photoresist thickness. The cost advantage originates from increased PMMA absorption lengths and the ability to fabricate large area masks without diaphragms which permit large exposure fields. This work was supported in part by the National Science Foundation under grant #ECS-916566. Additional financial support via ARPA-DALP Contract ONR N00014-93-1-0911 is acknowledged. The cooperation of Dr. E. Johnson and Dr. D.P. Siddons of Brookhaven National Laboratory is gratefully acknowledged. We acknowledge the support of the staffs of the Center for X-ray Lithography, F. Cerrina, Director, and the Synchrotron Radiation, Center, D. Huber, Director, for their help and the use of their facilities. The Center for X-ray Lithography is supported by SEMATECH Center of Excellence SRC Grant No. 88-MC-507 and the Department of Defense Naval Research Laboratory Grant No. N00014-91-J-1876. The Synchrotron Radiation Center is supported by the National Science Foundation Grant No. DMR-88-21625.     

Global observability of flows on the torus: An application of number theory

Kronecker's theorem is used to show that the irrational flows on then-dimensional torus are globally observed by a large class of continuous functions. These results are used to study the observability of Riccati flows on the Grassman manifolds.Supported in part by NASA Grant # NAG 2-203.     

Realization theory of infinite-dimensional linear systems. Part I

This paper deals with the problem of realization of infinitedimensional constant linear continuous-time systems. A framework, suitable for treating this problem, is introduced, including the definitions of input/output maps, systems, weighting patterns, etc. The theorem of the existence and uniqueness of canonical realizations is then proved. Central emphasis is placed on the introduction of a new notion of observability, called topological observability.This research was supported in part by US Army Research Grant DAA 29-77-G-0225 and US Air Force Grant AFOSR 76-3034 Mod. B while the author was at the Center for Mathematical System Theory, University of Florida, Gainsville, FL 32611, USA.     

Wave envelope technique for multimode wave guide problems

In this paper we propose a fast method for solving wave guide problems. In particular, we consider the guide to be inhomogeneous, and allow propagation of waves of higher-order modes. Such techniques have been handled successfully for acoustic wave propagation problems with single mode and finite length. This paper extends this concept to electromagnetic wave guides with several modes and infinite in length. The method is shown and results of computations are presented.Research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-18107 while the first author was in residence at the ICASE, NASA Langley Research Center, Hampton, VA 23665-5225, and by NASA Grant No. NAG-1-624.     

A parallel algorithm for approximating the minimum cycle cover

We address the problem of approximating aminimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to aminimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of 0(1 +n logn/(m + n) of the minimum-sized cover usingO(log² n) time on (m + n)/logn processors.Research supported by ONR Grant N00014-88-K-0243 and DARPA Grant N00039-88-C0113 at Harvard University.Research supported by a graduate fellowship from GE. Additional support provided by Air Force Contract AFOSR-86-0078, and by an NSF PYI awarded to David Shmoys, with matching funds from IBM, Sun Microsystems, and UPS.     

The theory of equivalence of Pfaffian systems and input systems under feedback

The Theory of equivalence of exterior differential systems is applied to study canonical forms under feedback for nonlinear systems in differential equation, state-space forms.Supported by Ames Research Center (NASA), Grant NSG-2404, U.S. Army Research Office. Contract #IL161102BH57-03 MATH, NSF MCS8003227.     

Decentralized sequential detection with sensors performing sequential tests

A decentralized sequential detection problem is considered where a set of sensors making independent observations must decide which of the given two hypotheses is true. Decision errors are penalized through a common cost function, and each time step taken by the sensors as a team is assigned a positive cost. It is shown that optimal sensor decision functions can be found in the class ofgeneralized sequential probability ratio tests (GSPRTs) with monotonically convergent thresholds. A technique is presented for obtaining the optimal thresholds. The performance of the optimal policy is compared with that of a policy which uses SPRTs at each of the sensors.This research was supported in part by the Joint Services Electronics Program under Grant N00014-90-J-1270, through the University of Illinois.     

A note on the accuracy of spectral method applied to nonlinear conservation laws

Fourier spectral method can achieve exponential accuracy both on the approximation level and for solving partial differential equations if the solutions are analytic. For a linear PDE with discontinuous solutions, Fourier spectral method will produce poor point-wise accuracy without post-processing, but still maintains exponential accuracy for all moments against analytic functions. In this note we assess the accuracy of Fourier spectral method applied to nonlinear conservation laws through a numerical case study. We have found out that the moments against analytic functions are no longer very accurate. However the numerical solution does contain accurate information which can be extracted by a Gegenbauer polynomial based post-processing.Research supported by ARO Grant DAAL03-91-G-0123 and DAAH04-94-G-0205, NSF Grant DMS-9211820, NASA Grant NAG1-1145 and contract NAS1-19480 while the first author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23681-0001, and AFOSR Grant 93-0090.     

A formalization of priority inversion

A priority inversion occurs when a low-priority task causes the execution of a higher-priority task to be delayed. The possibility of priority inversions complicates the analysis of systems that use priority-based schedulers because priority inversions invalidate the assumption that a task can be delayed by only higher-priority tasks. This paper formalizes priority inversion and gives sufficient conditions as well as some new protocols for preventing priority inversions.Supported by the Commission of the European Communities under the ESPRIT Programme Basic Research Action Number 3092 (Predictably Dependable Computing Systems) and the Italian Ministry of Research and University, and in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG-2-593.Supported in part by the Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG 2-593, and by grants from IBM T.J. Watson Research Laboratory, the IBM Endicott Programming Laboratory, Siemens RTL, and Xerox Webster Research Center.Supported in part by the Office of Naval Research under contract N00014-91-J-1219, the National Science Foundation under Grant No. CCR-8701103, DARPA/NSF Grant No. CCR-9014363, and by the IBM Endicott Programming Laboratory.     

Global controllability of nonlinear systems in two dimensions

LetM be a connected real-analytic 2-dimensional manifold. Consider the system (t) = f(x(t)) + u(t)g(x(t)),x(0) =x ₀ M, wheref andg are real-analytic vector fields onM which are linearly independent at some point ofM, andu is a real-valued control. Sufficient conditions on the vector fieldsf andg are given so that the system is controllable fromx ₀. Suppose that every nontrivial integral curve ofg has a pointp wheref andg are linearly dependent,g(p) is nonzero, and that the Lie bracket [f,g] andg are linearly independent atp. Then the system is controllable (with the possible exception of a closed, nowhere dense set which is not reachable) from any pointx ₀ such that the vector space dimension of the Lie algebraL _A generated byf,g and successive Lie brackets is 2 atx ₀.Research supported in part by the National Science Foundation under NSF Grant MCS76-05267-A01 and by the Joint Services Electronics Program under ONR Contract 76-C-1136.     

The algebraic specification of abstract data types

Summary There have been many recent proposals for embedding abstract data types in programming languages. In order to reason about programs using abstract data types, it is desirable to specify their properties at an abstract level, independent of any particular implementation. This paper presents an algebraic technique for such specifications, develops some of the formal properties of the technique, and shows that these provide useful guidelines for the construction of adequate specifications.Supported in part by the National Science Foundation under grant MCS-76-06089 and the Joint Services Electronics Program monitored by the Air Force Office of the Scientific Research under contract F44620-72C-0061Supported in part by the National Research Council of Canada.     

A method for obtaining randomized algorithms with small tail probabilities

We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.Supported by ESPRIT U Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).Supported by ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (Project ALCOM).Research supported by NSF Grant No. CCR-9005448.Partially supported by a Wolfson Research Award administered by the Israel Academy of Sciences and Humanities.     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.     

Semi-automatic process partitioning for parallel computation

Automatic process partitioning is the operation of automatically rewriting an algorithm as a collection of tasks, each operating primarily on its own portion of the data, to carry out the computation in parallel. Hybrid shared memory systems provide a hierarchy of globally accessible memories. To achieve high performance on such machines one must carefully distribute the work and the data so as to keep the workload balanced while optimizing the access to nonlocal data. In this paper we consider a semi-automatic approach to process partitioning in which the compiler, guided by advice from the user, automatically transforms programs into such an interacting set of tasks. This approach is illustrated with a picture processing example written in BLAZE, which is transformed by the compiler into a task system maximizing locality of memory reference.Research supported by an IBM Graduate Fellowship.Research supported under NASA Contract No. 520-1398-0356.Research supported by NASA Contract No. NAS1-18107 while the last two authors were in residence at ICASE, NASA, Langley Research Center.     

Optimal parallel verification of minimum spanning trees in logarithmic time

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan. Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.