All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given probing pattern) followed by the algorithmic reconstruction of the sequence from its spectrum. In the "standard" or "uniform" approach, the probing pattern is a string of length L and the length of reliably reconstructible sequences is known to be mlen = O(2(L)). For a fixed microarray area, higher sequencing performance can be achieved by inserting nonprobing gaps ("wild-cards") in the probing pattern. The reconstruction, however, must cope with the emergence of fooling probes due to the gaps and algorithmic failure occurs when the spectrum becomes too densely populated, although we can achieve mcomp = 0(4(L)). Despite the combinatorial success of gapped probing, all current approaches are based on a biochemically unrealistic spectrum-acquisition model (digital-spectrum). The reality of hybridization is much more complex. Departing from the conventional model, in this paper, we propose an alternative, called the analog-spectrum model, which more closely reflects the biochemical process. This novel modeling reestablishes probe length as the performance-governing factor, adopting "semidegenerate bases" as suitable emulators of currently inadequate universal bases. One important conclusion is that accurate biochemical measurements are pivotal to the success of SBH. The theoretical proposal presented in this paper should be a convincing stimulus for the needed biotechnological work.

International audience

DNA sequencing by hybridization, proposed about a decade ago as an alternative to standard electrophoresis-based sequencing techniques, is relevant not only to sequencing per se but also to diagnostics and therapeutics. The inherent structural inadequacy of traditional probe patterns and well-known hybridization shortcomings had for some time deflated the interest in this approach. Renewed interest for this topic has been generated by our recent discovery of a novel probing scheme whose performance for the first time asymptotically meets the information theory bound. After settling the question of asymptotic performance, due to the sizable volume of potential applications, the research focus has naturally shifted to issues of algorithmic fine tunings aimed at improving the performance "constants". In this paper, we introduce as a figure of merit the nucleotide-per-feature ratio (for a given confidence level), i.e., the length of a reliabily reconstructible (random) sequence divided by the number of probes placed on the sequencing array, regardless of the fabrication technology, and we explore the capabilities offered by the joint use of multiple different arrays in sequencing the same DNA sequence. In particular we consider a probing scheme based on the use of the spectra pertaining to a given probing pattern and to its reversal (referred to here as tandem spectra), and we show analytically and experimentally a performance improvement per unit of microarray area of about 4/3 (in a representative instance) over the conventional single-spectrum approach. The proposed tandem-spectrum reconstruction, in conjunction with a "voting provision" discussed elsewhere (whereby one of two competing alternatives is chosen if the corresponding probes are less numerous in the current prefix of the reconstructive sequence), is the best known technique for sequencing by hybridization.

In a recent paper [PFU99) we have introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well defined periodic pattern. It was shown in [PFU99] that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given library size of probes) is significantly better than the standard scheme based on oligomer probes.

In this paper, we reexamine in the framework of robust computation the Bentley--Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of degree 5, presumably never evaluated exactly in most implementations. Within the exact-computation paradigm we introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions. We identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only predicates of (optimal) degree 2, but its straightforward implementation appears highly inefficient. We then present algorithmic variants that have low degree under these models and achieve the same performance as the original Bentley--Ottmann algorithm. The technique is applicable to a more general case of curved segments.

Sequencing by hybridizationis a novel DNA sequencing technique in which an array (SBH chip) of short sequences of nucleotides (probes) is brought in contact with a solution of (replicas of) the target DNA sequence.A biochemical method determines the subset of probes that bind to the target sequence (the spectrum of the sequence), and a combinatorial method is used to reconstruct the DNA sequence from the spectrum.Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence an arbitrary DNA string of a given length.We show in this work that the use of universal bases (bases that bind to any nucleotide [LB94]) can drastically improve the performance of the SBH process.We present a novel probe design with performance that asymptotically approaches the information-theoretical bound up to a constant factor, and, for any number of probes, is significantly better than previously analyzed probe patterns.Furthermore, the sequencing algorithm we use is substantially simpler than the Eulerian path method used in previous work.

In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact-computation paradigm and formalize the notion of degree of a geometric algorithm as a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness. We also propose a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of our general approach where algorithm design is driven also by the degree, we consider the important classical problem of proximity queries in two and three dimensions and develop a new technique for the efficient and robust execution of such queries based on an implicit representation of Voronoi diagrams. Our new technique offers both low degree and fast query time and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number of operations, and arithmetic degree.

In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, aa a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness.We aleo propose a formalism for the expeditious evaluation of algorithmic degree.As an application of this paradigm and an illustration of our general approach, we consider the important classical problem of proximity queries in 2 and 3 dimensions, and develop a new technique for the efficient and robust execution of such queries baaed on an implicit representation of Voronoi diagrams.Our new technique gives both low degree and fast query time, and for 2D queries is optimal with respect to both cost meixmres of the paradigm, asymptotic number of operations md arithmetic degree.

An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of x/sup v/ mod m for arbitrary integers x, y, and m represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m<2/sup n/ and 0/spl les/Ix, y

We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map $\mathcal{M}$ with n vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in $\mathcal{M}$. The space requirement is $O(n\log n)$. Point-location queries take time $O(n\log n)$. Ray-shooting and shortest-path queries take time $O(\log ^3 n)$ (plus $O(k)$ time if the k edges of the shortest path are reported in addition to its length). Updates consist of insertions and deletions of vertices and edges, and take $O(\log ^3 n)$ time (amortized for vertex updates). This is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. It is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.

An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of "x/sup y/ mod m" for arbitrary integers x, y and m. Represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m>

No abstract available.

Upper bounds are derived for the processor-time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation of messages (due to the finiteness of the speed of light).It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors.The speedups are inherent, due to the optimality of the obtained tradeoffs as established in a companion paper.Simulations are developed of multiprocessor machines by analogous machines with fewer processors.A crucial role is played by the hierarchical nature of the memory system.A divide-and-conquer technique for hierarchical memories is developed, based on the graph-theoretic notion of topological separator.For multiprocessors, this technique also requires a careful balance of memory access and interprocessor communication costs, which leads to non-intuitive orchestrations of the simulation process.

Brent’s scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm. Such a scheme preserves, under slow-down, the actual number of executed operations, also called work. In this paper we take the complementary viewpoint, and rather than consider the work-preserving slow-down of some fast parallel algorithm, we investigate the problem of the achievable speedups of computation while preserving the work of the best-known sequential algorithm for the same problem. The proposed technique, eminently applicable to problems of matrix-computational flavor, achieves its result through the interplay of two algorithms with significantly different features. Analogous but structurally different “interplays” have been used previously to improve the algorithmic efficiency of graph computations, selection, and list ranking. We demonstrate the efficacy of our technique for the computation of path aigebras in graphs and digraphs and various fundamental computations in linear algebra. Some of the fundamental new algorithms may have practical value; for instance, we substantially improve the algorithmic performance of the parallel solution of triangular and Toeplitz linear systems of equations and the computation of the transitive closure of digraphs.

In this paper we present an O(log n) time parallel algorithm for computing the convex hull of n points in ℜ3. This algorithm uses O(n1+α) 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 (log2 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 divide-and-conquer paradigm.

Abstract. We present three explicit schemes for distributing M variables among N memory modules, where M = �(N 1.5), M = �(N 2), and M = �(N 3), respectively. Each variable is replicated into a constant number of copies stored in distinct modules. We show that N processors, directly accessing the memories through a complete interconnection, can read/write any set of N variables in worstcase time O(N 1/3), O(N 1/2), and O(N 2/3), respectively for the three schemes. The access times for the last two schemes are optimal with respect to the particular redundancy values used by such schemes. The address computation can be carried out efficiently by each processor without recourse to a complete memory map and requiring only O(1) internal storage. 1.

We study the problem of computing the set of admissible and stable placements of spider robots, a simple case of legged robots. The environment consists of a set of n points in the plane representing authorized footholds. We show that the space of admissible and stable placements of such robots has size θ(n2) and can be constructed in O(n2 log n) time and O(n2) space. We give also efficient algorithms for several related problems.

The authors consider a simple instance of the problem of planning motions of legged robots. The robot is modeled as a point where all its legs are attached, and the footholds where the robot can securely place its feet consist of a set of points in the plane. Efficient algorithms to compute stable motions in such situations are presented.>

Brent's scheduling principle provides a general simulation scheme when fewer processors are available than specified by the fastest parallel algorithm.Such a scheme preserves the actual number of executed operations, and when applicable, it provides a processor balancing technique that significantly reduces the work, expressed as the number of ezecutcdde operators.In this paper we discuss a new technique, called supereffective slow-down, that yields quite fast an algorithm with work significantly smaller than that of the fastest algorithm for the same problem.This technique can be viewed as a work-preserving acceleration of an existing recursive sequential algorithm for the considered problem.The presented examples include the computation of path algebras in graphs and digraphs and various computations in linear albegra.Some of the new algorithms may have practical value; for instance, we substantially improve the performance of the known parallel algorithms for triangular linear systems of equations.

In this paper a new approach is proposed to point-location in a three-dimensional cell-complex $\mathcal{P}$, which may be viewed as a nontrivial generalization of a corresponding two-dimensional technique due to Sarnak and Tarjan. Specifically, in a space-sweep of $\mathcal{P}$, the intersections of the sweep-plane with $\mathcal{P}$ occurring in a given slab, i.e., between two consecutive vertices, are topologically conformal planar subdivisions. If the sweep direction is viewed as time, the descriptions of the various slabs are distinct “versions” of a two-dimensional point-location data structure, dynamically updated each time a vertex is swept. Combining the persistence-addition technique of Driscoll, Sarnak, Sleator, and Tarjan [J. Comput. System. Sci., 38 (1989), pp. 86–124] with the recently discovered dynamic structure for planar point-location in monotone subdivisions, a method with query time $O(\log ^2 N)$ and space $O(N\log ^2 N)$ for point-location in a convex cell-complex with N facets is obtained.

The prefix problem consits of computing all the products $x_{0}x_{1}\cdots x_{j}(j = 0,\cdots, N-1)$, given a sequence ${\bf x} = (x_{0}, x_{1},\cdots , x_{N-1})$ of elements in a semigroup. It is shown that there are unbounded fan-in and fan-out Boolean circuits for the prefix problem with constant depth and linear size if and only if the Cayley graph of the semigroup does not contain a special type of cycle called monoidal cycle.

A discussion is presented of parallel division algorithms that can be classified among modified higher radix nonrestoring online division methods, where redundant representations are extensively utilized to speed up the operation. The network realizations of these algorithms are cellular, or even systolic with exclusively local control; they have both size (area) and time of O(n), where n is the length of the dividend representation. The same structures can also be used as a signed, digit-serial multiplier. When suitably equipped with some control and a few registers, the divider/multiplier brings remarkable performance to large modular arithmetic, RSA cryptography, and greatest common divisor computations. They are also of interest for the design of floating-point units and signal processing applications.>

We present a new technique to display a scene of three-dimensional isothetic parallelepipeds (3D-rectangles), viewed from infinity along one of the coordinate axes (axial view). In this situation, there always exists a topological sorting of the 3D-rectangles based on the relation of occlusion (a dominance relation). The arising total order is used to generate the axial view, where the two-dimensional view of each 3D-rectangle is incrementally added, starting from the closest 3D-rectangle. The proposedscene-sensitivealgorithm runs in timeO(Nlog2N+dlogN), whereNis the number of 3D-rectangles anddis the number of edges of the display. This improves over the previously best known technique based on the same approach.

In this paper, we show that distributing the memory of a parallel computer and, thereby, decreasing its granularity allows a reduction in the redundancy required to achieve polylog simulation time for each P-RAM step.Previously, realistic models of parallel computation assigned one memory module to each processor and, as a result, insisted on relatively coarse-grain memory.We propose, on the other hand, a more flexible, but equally valid model of computation, the distributed-memory, bounded-degree network (DMBDN) model.This model allows the use of fine-grain memory while maintaining the realism of a bounded-degree interconnection network.We describe a P-RAM simulation scheme, which is admitted under the DMBDN model, that exploits the increased memory bandwidth provided by a two-dimensional mesh of trees (2DMOT) network to achieve an overhead in memory redundancy lower than that required by other fast, deterministic P-RAM simulations.Specifically, for a deterministic simulation of an n-processor P-RAM on a bounded-degree network, we are able to reduce the number of copies of each variable from O(logn/loglogn) to ®(1) and still simulate each P-RAM step in polylog time.

The prefix problem consists of computing all the products x 0 x 1 … x j ( j = 0, … , N - 1), given a sequence x = ( x 0 , x 1 , … , x N- 1 ) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with Boolean networks, which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). A nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the Cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. Denoting by S and T size and computation time, respectively, we have S = Θ(( N / T )log( N / T )) for memory-inducive non-cycle-free semigroups, and S = Θ( N / T ) for all other semigroups. We have T ε [Ω(log N ), Ο( N )] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which T ε [Ω(1), Ο( N )]. The preceding results are also extended to the VLSI model of computation. Area-time optimal circuits are obtained for both boundary and nonboundary I/O protocols.

In this paper a dynamic technique for locating a point in a monotone planar subdivision, whose current number of vertices is n, is presented. The (complete set of) update operations are insertion of a point on an edge and of a chain of edges between two vertices, and their reverse operations. The data structure uses space $O(n)$. The query time is $O(\log ^2 n)$, the time for insertion/deletion of a point is $O(\log n)$, and the time for insertion/deletion of a chain with k edges is $O(\log ^2 n + k)$, all worst-case. The technique is conceptually a special case of the chain method of Lee and Preparata and uses the same query algorithm. The emergence of full dynamic capabilities is afforded by a subtle choice of the chain set (separators), which induces a total order on the set of regions of the planar subdivision.

A simple scheme for dispersal and recovery of digital information based on the discrete Fourier transform is discussed. The author presents a different implementation of M.O. Rabin's (J. ACM, vol.36, no.2, p.335-48, Apr. 1989) scheme, whose recovery cost is O(log m+k) operations per character, assuming m= Theta (n); for example, when k= Theta (log n), this cost drops from O(m) to O(log m) per character. Since the implementation is based on the Fourier transform, it is termed holographic.>

It is shown that a planar st-graph G admits two total orders on the set V union E union F, where V, E, and F are, respectively, the sets of vertices, edges and faces of G, with mod V mod =n. An O(n) space data structure for the maintenance of the two orders is exhibited that supports an update of G (insertion of an edge and expansion of a vertex, and their inverses) in time O(log n). This data structure also supports transitive-closure queries in O(log n). Moreover, planar st-graphs provide the topological underpinning of a fully dynamic planar point location technique in monotone subdivisions, which is an interesting (unique) specialization of the chain method of Lee-Preparata (1977). While maintaining storage O(n) and query time O(log/sup 2/ n), insertion/deletion of a chain with k edges can be done in time O(log/sup 2/ n+k), and insertion/deletion of a vertex on an edge can be done in time O(log n).>

Interconnection delay of VLSI has been a major bottleneck in the design of high-speed digital systems. The authors present a rigorous analysis of the signal propagation delay in VLSI circuits. They show that wire inductance is an important factor in determining the delay when the delay is in the subnanosecond range and that this delay cannot be well estimated by the conventional modeling of the interconnection by RC circuits. The effect of feature size scaling on circuit performance is also evaluated, and the inherent limitations on scaling due to interconnection delay is discussed. Finally, the relationship between the delay and the technology parameters, such as wire resistance, wire capacitance, wire inductance, wire width, wire length, and load capacitance is investigated to provide guidelines for the interconnection technology development.>

The prefix problem consists of computing all the products x0x1…xj (j=0, …, N - 1), given a sequence x = (x0, x1, …, xN - 1) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup). Denoting by S and T size and computation time, respectively, we have S = Θ((N/T) log(N/T)), for non-cycle-free semigroups, and S = Θ(N/T), for cycle-free semigroups. In both cases, T ∈ [Ω(logN), O(N)].

We describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM’s shared memory is polynomial in n, each PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2 )$ steps of the bounded-degree network.This improves upon a previous result by Upfal and Wigderson. We also prove an $\Omega ({{(\log n)^2 } / {\log \log n}})$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, we use a new technique for dynamically averaging out a given work load among a set of processors operating in parallel.

In this paper an O ( N log N ) algorithm for routing through a rectangle is presented. Consider an n -by- m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in O ( N log N ) time; this contrasts favorably with the area of the layout that might be as large as N 2 . The layout constructed can be wired using four layers of interconnect with only O ( N ) contact cuts. A partial extension to multiterminal nets is also discussed.

Given a fixed set S of n points in E3 and a query plane π, the halfspace range search problem asks for the retrieval of all points of S on a chosen side of π. We prove that with Ο(n(log n)3(log log n)4) storage it is possible to solve this problem in Ο(κ + log n) time, where κ is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the maximum number of κ-sets realized by a set of n points in E3 is Ogr;(nkc) for a small positive constant c; a κ-set is any subset of S of size κ which can be separated from the rest of S by a plane. Incidentally, this result constitutes the only nontrivial upper bound, as a function of n and κ, known to date.

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n2) area. The design is a typical instance of a ``hybrid architecture,'' resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT2= Ω(n2log2n) lower bound for sorters of n words of length (1 + ε) log n (ε > 0).

According to VLSI theory, [log n, √n]is the range of computation times for which there may exist an AT2-optimal multiplier of n-bit integers. Such networks were previously known for the time range [Ω(log2 n), O(√n)]; this theoretical question is settled, by exhibition of a class of AT2-optimal multipliers with computation times [Ω(log n), O(√n)]. The designs are based on the DFT on a Fermat ring, whose elements are represented in a redundant radix-4 form to ensure O(1) addition time.

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(logn) time by a chip occupying O(n2) area. The design is a typical instance of a “hybrid architecture”, resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected-cycles; it also provably meets the AT2=omegan2log2n) lower bound for sorters of n words of length (1+\epsilon)logn(\epsilon > O).

Abstract In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n 2 ) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.

We propose a class of designs of a new interconnection network, the pleated cube-connected cycles (PCCC), which can impleement stable bitonic sorting of n records of size q in area A = O(q2n2/T2), where T, the computation time, is in the range [Ω(q log2n), O(q √n/(q+ log n))]. Thus, this network is an AT2,/R-optimal bitonic sorter in the synchronous VLSI model of computation under the word-local restriction.

We survey the state of the art of computational geometry, a discipline that deals with the complexity of geometric problems within the framework of the analysis of algorithms. This newly emerged area of activities has found numerous applications in various other disciplines, such as computer-aided design, computer graphics, operations research, pattern recognition, robotics, and statistics. Five major problem areas—convex hulls, intersections, searching, proximity, and combinatorial optimizations—are discussed. Seven algorithmic techniques—incremental construction, plane-sweep, locus, divide-and-conquer, geometric transformation, prune-and-search, and dynamization—are each illustrated with an example. A collection of problem transformations to establish lower bounds for geo-metric problems in the algebraic computation/decision model is also included.

In this paper we show that any channel routing problem of density d involving only two-terminal nets can always be solved in the knock-knee mode in a channel of width equal to the density d with three conducting layers. An algorithm is described which produces in time O(n log n) (in its simplest implementation) a layout of n nets with the following properties: 1) it has minimal width d; 2) it can be realized with three layers; 3) it has at most 3n vias; 4) any two wires share at most four grid points. Without sacrificing any of the above properties (but possibly obtaining slightly longer wires), the layout algorithm can be modified to run in time θ(n).

A family of VLSI circuits is presented to perform open convolution, i.e., polynomial multiplication. The circuits are all based on a recursive construction and are therefore particularly well adapted to automated design. All the circuits presented are optimal with respect to the area–time2 tradeoff, and, depending on the degree of paralleism or pipeline, they range from a compact but slow convolver to a large but very fast convolver.

This paper describes a VLSI network for the multiplication of two N-bit integers, for very large N. The network, with its area 0(N) and operation time 0(√N), matches, within a constant factor, the known theoretical Ω(N2) lower bound to the area × (time)2measure of complexity in the VLSI model of computation. The network, which is based on the discrete Fourier transform, has an extremely regular mesh structure, and thus all wires have approximately the same length.

In this paper we show that any channel routing problem of density d involving two-terminal nets can always be solved in the knock-knee mode in a channel of width equal the density d with three conducting layers. An algorithm is described which produces a layout of n nets with the following properties: (i) it has minimal width d; (ii) it can be realized with three layers; (iii) it has at most 3n vias; (iv) any two wires share at most four grid points.

Given a planar straight line graph G with n vertices and a point $P_0 $, locating $P_0 $ means to find the region of the planar subdivision induced by G which contains $P_0 $. Recently, Lipton and Tarjan presented a brilliant but extremely complex point location algorithm which runs in time $O(\log n)$ on a data structure using $O(n)$ storage. This paper presents a practical algorithm which runs in less than $6\lceil {\log _2 n} \rceil $ comparisons on a data structure which uses $O(n\log n)$ storage, in the worst case. The method rests crucially on a simple partition of each edge of G into $O(\log n)$ segments.

We introduce a network of processing elements, the cube-connected-cycles (CCC), complying with the present technological constraints of VLSI design. By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine with no significant degradation of performance but with a much more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems, which includes Fast-Fourier-Transform, sorting, permutations, and derived algorithms. The CCC can also be used as a general purpose parallel processor.

The kernel K(P) of a simple polygon P wah n verUces is the locus of the points internal to P from which all verUces of P are wslble Equwalently, K(P) is the mtersectmn of appropriate half-planes determined by the polygon's edges Although it is known that to find the intersection of n generic half-planes requires time O(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs m time O(n) and is therefore optimal

In this note we algorithmically show that a set of k points can be located in the planar subdivision induced by a straight-line planar graph with n vertices in time $O(k\log k) + O(n) + O(k\log n)$, given a preprocessing time $O(n\log n)$.

In this paper, we describe a family of parallel-sorting algorithms for a multiprocessor system. These algorithms are enumeration sortings and comprise the following phases: 1) count acquisition: the keys are subdivided into subsets and for each key we determine the number of smaller keys (count) in every subset; 2) rank determination: the rank of a key is the sum of the previously obtained counts; 3) data rearrangement: each key is placed in the position specified by its rank. The basic novelty of the algorithms is the use of parallel merging to implement count acquisition. By using Valiant's merging scheme, we show that n keys can be sorted in parallel with n log2n processors in time C log2n + o(log2n); in addition, if memory fetch conflicts are not allowed, using a modified version of Batcher's merging algorithm to implement phase 1), we show that n keys can be sorted with n1 +αprocessors in time (C'/α a) log2n + o(log2n), thereby matching the performance of Hirschberg's algoithm, which, however, is not free of fetch conflicts.

In this paper we consider the problem of recoding binary data into ternary sequences for synchronous baseband data transmission systems. Our major objective is the shaping of the power spectral density of the channel process in order to combat the effects of intersymbol interference caused by the low-frequency cut-off of the channel. This motivates our interest in designing codes whose channel process has small Power in the low frequency range. Based on the MacLaurin expansion of the power density function, we use as a design heuristic the normalized second derivative Δ of the latter. To make computationally manageable the expression of Δ, we restrict ourselves to a class of codes whose autocorrelation sequence contains a finite number of nonzero terms, and present a corresponding code design algorithm. As examples, we exhibit two new codes which in many respects improve over the spectra of corresponding well-known codes.

Given a subdivision of the plane induced by a planar graph with n vertices, in this paper we consider the problem of identifying which region of the subdivision contains a given test point. We present a search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure. The search runs in time at most $O((\log n)^{2})$, while the preprocessing task runs in time at most $O(n \log n)$ and requires $O(n)$ storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most $O(n \log n)$ into one to which the preprocessing procedure is applicable. This solution of the point location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon.

In this paper we presentt family of techniques for the design of combinational networks whose objective is the reduction of the number of levels, subject to a constraint on the fan-in of the logic gates. We show that a Boolean expression with n literals and involving the connectivest AND and OR can be restructured so that the resulting network of AND and OR gates has depth at most Cllog2n + δ, where alis 1.81, 1.38, 1.18, and 1 for maximum fan-in l of 2,3,4, and 5, respectively. If we additionally require that the amount of equipment of the resulting network be bounded by a linear function of n, it is possible to bound the depth by 2 log2n with a fan-in of at most 3.

Given a subdivision of the plane induced by a planar graph with n vertices, in this paper the problem of identifying which region of the subdivision contains a given test points is considered. A search algorithm, called point-location algorithm, which operates on a suitably preprocessed data structure is presented. The search runs in time at most O((log n)2), while the preprocessing task runs in time at most O(n log n) and requires O(n) storage. The methods are quite general, since an arbitrary subdivision can be transformed in time at most O(n log n) into one to which the preprocessing procedure is applicable. This solution of the point location problem yields interesting and efficient solutions of other geometric problems, such as spatial convex inclusion and inclusion in an arbitrary polygon

Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 log 2 n + 1 and 2.08 log 2 n for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log 2 α ≈ 2.88 and 1/log 2 β ≈ 2.08, where α and β are the positive real roots of the equations z 2 = z + 1 and z 4 = 2 z + 1, respectively. While these times were known to be of order log 2 n , the best previously known coefficients were 4 and 2.15 for the two cases. The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant. The paper also gives upper bounds to the restructuring time of a given expression E and to the number of processors required for its parallel evaluation. It is shown that at most O (n 1.44 ) and O (n 1.82 ) operations are needed for restructuring general expressions and division-free expression, respectively. It is pointed out that, since the order of the compiling time is greater than n log n , the numbers of required processors exhibit the same rate of growth in n as the corresponding compiling times.

A Boolean expression wilth n literals, i.e., n distinct appearances of variables, can be evaluated by a parallel processing system in at most 1.81 log2n steps, or, equivalently, by a network constructed with two-input AND and OR gates and having at most 1.81 log2n levels.

ASSTRACT.Let U1 , U2, . . ., Ud be totally ordered sets and let V be a set of n d-dimensional vectors In U~ X Us. .X Ud .A partial ordering is defined on V in a natural way The problem of finding all maximal elements of V with respect to the partial ordering ~s considered The computational complexity of the problem is defined to be the number of required comparisons of two components and is denoted by Cd(n).It is tnwal that C~(n) = n -1 and C,~(n) < O(n 2) for d _~ 2 In this paper we show: ( 1) C2(n) = O(n logan) for d = 2, 3 and Cd(n) ~ O(n(log2n) ~-~) for d ~ 4, (2) C,t(n) >_ flog2 n!l for d _> 2 KEY WORDS AND PHRASES: maxima of a set of vectors, computattonal complexity, number of comparisons, algorithm, recurrence CR CATEaOmES.5.25, 5,31, 5.39 IntroductionLet U1, U2_, • • • , Ud be totally ordered sets and let V be a set of n d-dimensional vectors in the Cartesian product Ui X U2 X • • • X Ud.For any vector v in V, let x,(v) denote the zth component of v.A partial ordering < is defined on V in a natural way, that is, for v, u E V, v < u if and only if x,(v) <, x,(u) for all z = 1, ... , d, where _<, is the total ordering on U,. (We shall often write <_ for <,.The context should make clear the meaning of < .)For v C V, v is defined to be a maximal element (or, briefly, a maximum) of V if there does not exist u E V such that u ~ v and u ~ v.We consider the problem of finding all maximal elements of V.The computational complexity of the problem is defined to be Cd(n) = min max Ca(A, V),

A network which sorts n numbers, when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unite) symmetric Boolean functions of n arguments When sorting networks are constructed from comparator modules they have been widely conjectured to require (1) delay time or number of levels of order (log2n) 2, (2) size or number of elements of order n0og2n) ~, and (3) formula length or number of hterals of order n~°*2 ~ It IS proved constructively in the paper that, if one permits the use of negations in constructing the corresponding Boolean functions, these three measures of complexity can be reduced to the orders of log2n, n, and n ~, respectively The latter network, however, is Incapable of sorting numbers other than O's and rs and may be thought of as merely counting the number of Inputs which are 1 It is shown, however, that one may incorporate this network in a larger network which does sort and In time proportional to only logan This network is the first known example of a nonadaptive network capable of sorting in time less than (log2n) 2 CR CATEGORIES: 5 25, 5 31, 6 1 KEY WORDS AND PHRASES computational complexity, sorting, counting, symmetric Boolean functions, computation time, length of formula 1.Two basic operations often used in sorting networks are the formation of the maximum and the minimum of a pair of numbers.These operations are usually performed at the same time by a two-input, two-output device called a comparator module which may be regarded as being composed of two more basic elements.The first is a comparison element with binary output indicating which of the two inputs is larger, and the second is a crossover switch which is set by the output of the first element so as to place the larger number on one line and the smaller on the other.We may use the Boolean notation a V b and ab for the maximum and the minimum, respectively, of two numbers a and b.The convenience of this notation has been observed by several authors [1, 3], since Boolean expressions can be used in the analysis of sorting networks.The interpretation of these expressions, however, depends upon the domain of the variables.A network of comparator modules sorts n numbers if and only if, when interpreted as a network of AND and OR gates, it realizes the n frontal (unite) symmetric Boolean functions of n variables [3].This fact is easily seen, since a sorting network can also be used with numbers which are of just two sizes, 0 and 1.Conversely, if all input configurations of O's and l's are properly sorted, the output functions are uniquely defined as the frontal symmetric functions.These functions are also the ones which, when reinterpreted as ap-

A code of integers into binary sequences is called a difference-preserving code (DP code) if it has the following two properties: 1) if the absolute value of the difference between two integers is less than or equal to a certain threshold, the Hamming distance between their codewords is equal to this value and 2) if the absolute value of the difference between two integers exceeds the threshold, then the Hamming distance between their codewords also exceeds this threshold. Such codes (or slight modifications thereof) have also been called path codes, circuit codes, or snake-in-the-box codes. This paper discusses the application of DP codes to pattern recognition and classification problems and presents a construction of efficient DP codes whose information content is asymptotically (in the length of codewords) of the order of theoretical upper bounds.

By considering universal logic modules whose terminals may be interconnected, new designs are presented for six, nine, and ten arguments, whose numbers of terminals represent substantial improvements over previously known designs.

A Boolean function U( z1,...,zm) is universal for given n≥1 and a set I of variables if it realizes all Boolean functions f(x1,..., xn) by substituting for each zj a variable of I. Designs of universal Boolean functions for various specifications of I are considered for the practical cases of n<10. Assuming the number m of input terminals as criterion of simplicity, the designs obtained are the best known to be offered by a systematic procedure for the same specifications.

Using as logic modules two-input one-output arbitrary logic gates, this note considers the problem of the longest chain (number of levels) in a tree-type interconnection realizing a Boolean function of n variables. Specifically, we are interested in the minimum number of levels L(n) by which we can constructively realize all Boolean functions of n variables. It was previously shown that L(n)≤n for n=3, 4 and it was so conjectured for n= 5; in this note we are able to show that this holds for n=5, 6, 7, 8.

Stochastic (or, indifferently, probabilistic) sequential machines have been recognized to be important mathematical models for several classes of information processing systems with memory, in which random disturbances cannot be neglected. As examples it suffices to mention the models of finite-state discrete channels for information transmission, sequential machines constructed from unreliable components, and adaptive learning systems. From a more abstract and less engineering-motivated angle, the stochastic sequential machine (SSM) represents the natural generalization of the deterministic one, on which a considerable body of knowledge exists. Not to be overlooked, finally, is the fact that the rich underlying structure promises elegant results and this undeniable aesthetic dimension certainly contributes an additional interest to this per se attractive topic.

The (23, 12) binary Golay code is a member of a class of linear codes, obtained by extending nonlinear double-error-correcting codes recently discovered. While all other codes of the class have minimum distanced_m= 6, the (23, 12) code owes its unique property (d_m= 7) to the nonexistence of the BCH code of length 7 andd_m= 6.

Abstract—This paper analyzes invertible length-preserving convolutional transformations of binary sequences, when the perfect inverse feedback transducer is replaced by a finite feedforward (i. e., convolutional) transducer which represents an approximation of the former. This replacement eliminates the error propagation effect, but the finiteness of the "inverse" transducer (decoder) results in a restriction on the input sequences, for which exact replication is achieved in the two-way transduction (transformation and recovery). The entity of the input restriction can be taken as a measure of performance for sets of transformations, and can be described in terms of the upper bound of the entropies of the binary sources which are "matched" to the system (direct and inverse transducers). This bound is clearly the capacity of the system viewed as a noiseless channel. It is shown that, if r is the number of decoder stages, the channel capacity has an asymptotic expression C≃1-Abr, where the parameters b < 1 and A depend solely upon the structure of the set of resynchronizing states (RS cluster) possessed by the given set of transformations.

This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u1, u2, . . . , un, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit of the system tests a subset of units, and a proper diagnosis can be arrived at for any diagnosable fault pattern. Methods for optimal assignments are given for instantaneous and sequential diagnosis procedures.

Nonfeedback shift registers (finite-memory encoders) can be profitably adopted to perform transformations of binary sequences. The output sequence is convolutionally obtained by ``sliding'' the encoding device along the input sequence and producing a symbol at each shift. Invertible transformations are characterized and decoding schemes are analyzed. The crucial point in the decoding problem is that the simple finite-memory feedback decoder presents the undesirable well-known error propagation effect, while the nonfeedback decoder contains, in general, an indefinite number of stages. Finite-memory nonfeedback decoding is feasible, however, if some constraint is imposed on the input sequences, or, equivalently, if some decoding error is tolerated. The analysis is conducted through the concepts of resynchronizing states of Boolean functions. The algebraic properties of resynchronizing states are carefully analyzed; it is shown that they can be assigned only in special sets, termed clusters, which form a lattice. Moreover, each cluster of resynchronizing states is possessed by a set of Boolean functions, which form a subspace of the vector space of all Boolean functions. The presented analysis provides a formal tool to relate finite-memory nonfeedback decoding to the constraint imposed on the input generating source.

A procedure for testing the realizability of complete 2n-state directed graphs by means of n-stage synchronous autonomous sequential networks of particular types, supplying at the same time state assignments pertaining to realizations of a specified class, is described. The analysis is confined to decomposed and linear networks, although the outlined method, based on the matrix representation of sequential circuits, can be applied to other types of networks. The similarity between transition matrices and corresponding logic matrices permits deriving circuit results through sole consideration of state graph structures. By resorting to the classical theory of rational canonical matrices, with any transition matrix a unique set of invariant vector subspaces of the 2n-dimensional space is systematically associated, upon which the prescribed realizability test is performed.

A new theoretical approach to the description of state-logic relations is presented, which applies to linear as well as nonlinear autonomous networks. A formal link, based on a matrix algorithm, is found between the internal logic of the network and its terminal behavior. The application of matrix algebra is the most attractive and encouraging aspect of this theory, in view of possible systematic minimization procedures.