Blocking for external graph searching

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.Support was provided in part by an IBM Graduate Fellowship, by NSF Research Grants CCR-9007851 and IRI-9116451, and by Army Research Office Grant DAAL03-91-G-0035.Support was provided in part by NSF Grants CCR-9003299, CCR-9300079, and IRI-9116843, and by NSF/DARPA Grant CCR-8908092.Support was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, and by Army Research Office Grant DAAL03-91-G-0035.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

Optimal cooperative search in fractional cascaded data structures

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.An earlier version of this work appears inProceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 307–316. The first author's support was provided in part by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225. This research was performed while the second author was at Brown University. Support was provided in part by an NSF Presidential Young Investigator Award CCR-9047466, with matching funds from IBM, by National Science Foundation Grant CCR-9007851, by the U.S. Army Research Office under Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225.     

Dynamic expression trees

We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include changing the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortestst-path in a series-parallel subgraph.Research supported in part by the National Science Foundation under Grant CCR-9007851, by the US Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225, and by Cadre Technologies, Inc.     

Combining databases with prioritized information

To solve a problem one may need to combine the knowledge of several different experts. It can happen that some of the claims of one or more experts may be in conflict with the claims of other experts. There may be several such points of conflict and any claim may be involved in several different such points of conflict. In that case, the user of the knowledge of experts may prefer a certain claim to another in one conflict-point without necessarily preferring that statement in another conflict-point.Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give four types of semantics for priorities, three of which are shown to be equivalent to one another. The fourth type of semantics for priorities is shown to be more cautious than the other three. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.Jack Minker and Shekhar Pradhan were supported in part by the National Science Foundation grant IRI-89-16059 and Air Force Office of Scientific Research grant 91-0350. V.S. Subrahmanian was supported in part by Army Research Office grant DAAL-03-92-G-0225, Air Force Office of Scientific Research Grant F49620-93-1-0065, and NSF grant IRI-9109755.     

Algorithms for parallel memory,II: Hierarchical multilevel memories

In this paper we introduce parallel versions of two hierarchical memory models and give optimal algorithms in these models for sorting, FFT, and matrix multiplication. In our parallel models, there areP memory hierarchies operating simultaneously; communication among the hierarchies takes place at a base memory level. Our optimal sorting algorithm is randomized and is based upon the probabilistic partitioning technique developed in the companion paper for optimal disk sorting in a two-level memory with parallel block transfer. The probability of using/times the optimal running time is exponentially small in (log ) logP.A summarized version of this research was presented at the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 1990. This work was done while the first author was at Brown University. Support was provided in part by a National Science Foundation Presidential Young Investigator Award with matching funds from IBM, by NSF Research Grants DCR-8403613 and CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052 ARPA Order 8225. This work was done in part while the second author was at Brown University supported by a Bellcore graduate fellowship and at Bellcore.     

System reduction via truncated Hankel matrices

The problem of approximating Hankel operators of finite or infinite rank by lower-rank Hankel operators is considered. For efficiency, truncated Hankel matrices are used as the intermediate step before other existing algorithms such as theCF algorithms are applied to yield the desirable approximants. If the Hankel operator to be approximated is of finite rank, the order of approximation by truncated Hankel operators is obtained. It is also shown that when themths-number is simple, then rational symbols of the best rank-m Hankel approximants of thenth truncated Hankel matrices converge uniformly to the corresponding rational symbol of the best rank-m Hankel approximant of the original Hankel operator asn tends to infinity. Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025 and also supported by the National Science Foundation under Grant No. DMS 8602337. Supported by SDIO/IST managed by the U.S. Army under Contract No. DAAL03-87-K-0025. Supported by the National Science Foundation under Grant No. DMS 8602337.     

Pathwise approximation and simulation for the Zakai filtering equation through operator splitting

Pathwise approximate solutions to the Zakai nonlinear filtering equation are analyzed and computed through operator splitting techniques. Several examples are presented to test the performances of the operator splitting algorithms. The work of R. Glowinski was supported by the U.S. Army Research Office under Contract DAAL03-86-K-0138 and by NSF via Grant INT-8612680.     

Algorithms for parallel memory,I: Two-level memories

We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size.A summarized version of this research was presented at the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 1990. This work was done while the first author was at Brown University. Support was provided in part by a National Science Foundation Presidential Young Investigator Award with matching funds from IBM, by NSF Research Grants DCR-8403613 and CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052 ARPA Order 8225. This work was done in part while the second author was at Brown University supported by a Bellcore graduate fellowship and at Bellcore.     

Range estimation from focus using a non-frontal imaging camera

This paper is concerned with active sensing of range information from focus. It describes a new type of camera whose sensor plane is not perpendicular to the optical axis as is standard. This special imaging geometry eliminates sensor plane movement usually necessary for focusing. Camera panning, required for panoramic viewing anyway, in addition enables focusing and range estimation. Thus panning integrates the two standard mechanical actions of focusing and panning, implying range estimation is done at the speed of panning. An implementation of the proposed Non-frontal Imaging Camera (NICAM) design is described. Experiments on range estimation are also presented.The support of the National Science Foundation and Defense Advanced Research Projects Agency under grant IRI-89-02728 and U.S. Army Advance Construction Technology Center under grant DAAL 03-87-K-0006 is gratefully acknowledged.     

Mean-field phase transitions and correlation functions for Gibbs random fields

The use of Gibbs random fields (GRF) to model images poses the important problem of the dependence of the patterns sampled from the Gibbs distribution on its parameters. Sudden changes in these patterns as the parameters are varied are known asphase transitions. In this paper we concentrate on developing a general deterministic theory for the study of phase transitions when a single parameter, namely, the temperature, is varied. This deterministic framework is based on a technique known as themean-field approximation, which is widely used in statistical physics. Our mean-field theory is general in that it is valid for any number of gray levels, any pairwise interaction potential, any neighborhood structure or size, and any set of constraints imposed on the desired images. The mean-field approximation is used to compute closed-form estimates of the critical temperatures at which phase transitions occur for two texture models widely used in the image modeling literature: the Potts model and the autobinomial model. The mean-field model allows us to gain insight into the Gibbs model behavior in the neighborhood of these temperatures. These analytical results are verified by computer simulations that use a novel mean-field descent algorithm. An important spinoff of our mean-field theory is that it allows us to compute approximations for the correlation functions of GRF models, thus bridging the gap between neighborhood-based and correlation-baseda priori image models.The work of I.M. Elfadel was supported in part by the National Science Foundation under grant MIP-91-17724. The work of A.L. Yuille was supported by the Brown, Harvard, and MIT Center for Intelligent Control Systems under U.S. Army Research Office grant DAAL03-86-C-0171, by the Defense Advanced Research Projects Agency under contract AFOSR-89-0506, and by the National Science Foundation under grant IRI-9003306.     

Augmented infinitesimal perturbation analysis: An alternate explanation

Augmented infinitesimal perturbation analysis (APA) was introduced by Gaivoronski [1991] to increase the purview of the theory of Infinitesimal Perturbation Analysis (IPA). In reference [Gaivoronski 1991] it is shown that an unbiased estimate for the gradient of a class of performance measures of DEDS represented bygeneralized semi-Markov processes (GSMPs) (cf. [Glynn 1989] can be expressed as a sum of an IPA-estimate and a term that takes into account the event order changes. In this paper we present an alternate approach to establishing the result of Gaivoronski, and from this we derive a necessary and sufficient condition for the validity of the IPA algorithm for this class of performance measures. Finally we validate our results by simulation examples.This research was supported by the National Science Foundation under grant number ECS-85-15449, Office of Naval Research Grants Nos. N00014-90-K-1093 and N00014-89-J-1023 and by Army Grant No. DAAL-03-86-K-0171.     

Invertibility of Discrete-Event Dynamic Systems

In this paper we consider a class of Discrete-Event Dynamic Systems (DEDS) modeled as finite-state automata in which only some of the transition events are directly observed. An invertible DEDS is one for which it is possible to reconstruct the entire event string from the observation of the output string. The dynamics of invertibility are somewhat complex, as ambiguities in unobservable events are typically resolved only at discrete intervals and, perhaps, with finite delay. A notion of resiliency or error recovery is developed for invertibility, and polynomial-time tests for invertibility and for resilient invertibility, as well as a procedure for the construction of a resilient inverter, are discussed.Research supported by the Air Force Office of Scientific Research under Grant AFOSR-88-0032 and by the Army Research Office under Grant DAAL03-86-K0171. This research was partially done during our stay at the Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France, and the second author was also supported by IRISA during this time.     

On the control of discrete-event dynamical systems

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Ramadge and Wonham, and we focus on the computational effort required for their solution. While the problem of supervisory control of a perfectly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when imperfectly observed systems are considered. Research supported by the Army Research Office (Grant No. DAAL03-86-K-0171) and by an NSF PYI award, with matching funds from Bellcore Inc.     

A systematic incrementalization technique and its application to hardware design

A systematic transformation method based on incrementalization and value caching generalizes a broad family of program optimizations. It yields significant performance improvements in many program classes, including iterative schemes that characterize hardware specifications. CACHET is an interactive incrementalization tool. Although incrementalization is highly structured and automatable, better results are obtained through interaction, where the main task is to guide term rewriting based on data-specific identities. Incrementalization specialized to iteration corresponds to strength reduction, a familiar program improvement technique. This correspondence is illustrated by the derivation of a hardware-efficient nonrestoring square-root algorithm, which has also served as an example of theorem prover-based implementation verification. Published online: 9 October 2001 RID="*" ID="*"S.D. Johnson supported, in part, by the National Science Foundation under grant MIP-9601358. RID="**" ID="**"Y.A. Liu supported in part by the National Science Foundation under grant CCR-9711253, the Office of Naval Research under grant N00014-99-1-0132, and Motorola Inc. under a Motorola University Partnership in Research Grant. RID="***" ID="***"Y. Zhang is a student recipient of a Motorola University Partnership in Research Grant.     

Homogeneous Lyapunov functions and necessary conditions for stabilization

We provide necessary conditions for the stabilization of nonlinear control systems with the additional requirement that a time-invarianthomogeneous Lyapunov function exists for the closed-loop system.The authors gratefully acknowledge research support from the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology, and Culture, and from the EC-Science Project SC1-0433-C(A). The first author is Charge de recherches F.N.R.S, on leave from CESAME, Université Catholique de Louvain, Belgium. He acknowledges partial support from the following organizations: National Science Foundation under Grant ECS-9203491, Air Force Office of Scientific Research under Grant F-49620-92-J-0495, Belgian American Educational Foundation, and North Atlantic Treaty Organization. The scientific responsibility rests with the authors.     

The complexity of induced minors and related problems

The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning non-induced structures. The effect on these problems of restricting the input to planar graphs is also considered. The principal results include: (1) Induced Maximum Matching and Induced Directed Path are NP-complete for planar graphs, (2) for every fixed graphH, InducedH-Minor Testing can be accomplished for planar graphs in time0(n), and (3) there are graphsH for which InducedH-Minor Testing is NP-complete for unrestricted input. Some useful structural theorems concerning induced minors are presented, including a bound on the treewidth of planar graphs that exclude a planar induced minor.The research of the first author was supported by the U.S. Office of Naval Research under Contract N00014-88-K-0456, by the U.S. National Science Foundation under Grant MIP-8603879, and by the National Science and Engineering Research Council of Canada. The second author acknowledges the support of the U.S. Office of Naval Research when visiting the University of Idaho in spring 1990. Some results were also obtained during a visit to the University of Cologne in fall 1990.     

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.     

Modal logic for default reasoning

In the paper we introduce a variant of autoepistemic logic that is especially suitable for expressing default reasonings. It is based on the notion of iterative expansion. We show a new way of translating default theories into the language of modal logic under which default extensions correspond exactly to iterative expansions. Iterative expansions have some attractive properties. They are more restrictive than autoepistemic expansions, and, for some classes of theories, than moderately grounded expansions. At the same time iterative expansions avoid several undesirable properties of strongly grounded expansions, for example, they are grounded in the whole set of the agent's initial assumptions and do not depend on their syntactic representation.Iterative expansions are defined syntactically. We define a semantics which leads to yet another notion of expansion — weak iterative expansion — and we show that there is an important class of theories, that we call -programs, for which iterative and weak iterative expansions coincide. Thus, for -programs, iterative expansions can be equivalently defined by semantic means.This work was partially supported by Army Research Office under grant DAAL03-89-K-0124, and by National Science Foundation and the Commonwealth of Kentucky EPSCoR program under grant RII 8610671.     

Completeness issues in RUE-NRF deduction: The undecidability of viability

We show that the algorithm directly induced by the viability definition in Ref. [4] does not terminate in general. As a consequence, RUE-resolution in strong form is not complete. Moreover, we show that ground query processing forcovered pure logic programs can be reduced to computing viability. Since the problem of ground query processing is strictly recursively enumerable even under the above restrictions, it follows that the notion of viability is undecidable. Finally, we present a modified viability check that solves the non-termination problem for ground terms.Work supported in part by NSF grants IRI-9015251 and IRI-9109755 and by Army Research office grant DAAL-03-92-G-0225.