A non classical approach to the logic synthesis of Boolean functions based on switching lattices is considered, for which deriving a feasible layout has not been previously studied. The problem presents new interesting combinatorial and algorithmic aspects. Our basic assumptions are that the positions of the switches in the lattice are fixed in the synthesis stage, and the layout for connecting the subsets of switches with the same input literal must be realized in superimposed planes through vias that take the same switch area. The overall goal is to minimize the number of layers needed. Since multiple choices of input literals are possible for each switch, we first study how to assign a single literal to each switch, to minimize the number of lattice portions of adjacent cells associated to the same literal (Problem 1). Then we study how to derive a feasible layout by building connections onto different layers, to minimize the number of layers (Problem 2). Problem 1 is NP-hard. Problem 2 seems to be also intractable, and exhibits limit instances that require an exceedingly number of layers or are even unsolvable. Heuristic algorithms are then developed for both problems and their encouraging performances are proved on a set of known benchmarks.

Trees are a fundamental structure in algorithmics. In this paper, we study the transformation of an arbitrary binary tree S with n vertices into a completely balanced tree T via rotations , a widely studied elementary tree operation. Combining concepts on rotation distance and data structures, we give a basic algorithm that performs the transformation in Θ( n ) time and Θ(1) space, making at most 2 n − 2 log 2n rotations and improving on known previous results. The algorithm is then improved, exploiting particular properties of S . Finally, we show tighter upper bounds and obtain a close lower bound on the rotation distance between a zig-zag tree and a completely balanced tree. We also find the exact rotation distance of a particular almost balanced tree to a completely balanced tree, and thus show that their distance is quite large despite the similarity of the two trees.

In many network applications, the computation takes place on the minimum-cost spanning tree (MST) of the network G; unfortunately, a single link or node failure disconnects the tree. The ALL NODES REPLACEMENT (ANR) problem is the problem of precomputing, for each node u in G, the new MST should u fail. This problem has been extensively investigated for serial and parallel settings, and efficient solutions have been designed for those environments. The situation is surprisingly different in distributed settings. In fact, no distributed solution exists to date which performs better than the brute-force repeated application of MST construction. In this paper, we consider for the first time the problem of computing all the replacement minimum-cost spanning trees distributively. We design a solution protocol, and we prove that the total amount of communication exchanges taking place is O(n), each exchange using at most O(n) data items. Hence, the total amount of data items communicated during the computation (the data complexity) is O(n^2). We also show how the simpler problem ALL EDGES REPLACEMENT (AER) dealing with single edge failures, which can be solved with the same costs using some existing techniques. Also for the AER problem, efficient solutions exist in the serial and parallel setting but, prior to this work, no distributed solution other than brute force was known.

Network decontamination is studied on a k-dimensional torus (n1times ldrldrldr times nk), with k ges 1 and 2 les n1lesldrldrldrles nk. The decontamination is done by a set of agents moving on the net according to a new cleaning model. After an agent leaves from a vertex, this vertex remains uncontaminated as long asmneighbors are uncontaminated. We propose algorithms valid for any m les 2k (i.e., up to the vertex degree), proving that A(k, m) synchronous agents suffice, with: A(k, 0) = 1; A(k, m) = 2m-1, for 1 les m les k + 1; A(k, m) = 22k-m+1n1n2ldrldrldr nm-k-1, for k + 2 les m les 2k. We also study the total number M(k, m) of agent moves, and prove matching lower bounds on A(k, m) and M(k, m) valid form = 3 and any k, and for all m ges k+1. Our study can be simply extended to asynchronous functioning.

We consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform the task using as small a team of antiviral agents, avoiding any recontamination of disinfected areas, and minimizing the amount of agents' movements across the network. In all the existing literature, it is assumed that the immunity level of a disinfected site is nil. In this paper we consider the network decontamination problem under a new model of immunity to recontamination: we consider the case when a disinfected vertex, after the cleaning agent has gone, will become recontaminated only if a weak majority of its neighbours are infected. We study the effects of this level of immunity on the number of antiviral agents necessary to decontaminate the entire network. We focus on tori and on trees, and establish lower-bounds on the team size; we also establish lower bounds on the number of moves performed by an optimal-size time of cleaners. We design and present strategies for disinfecting tori and trees; we prove that these strategies are optimal in terms of both team size and number of moves. In particular, the upper and lower bounds are tight for tree networks and for synchronous tori; the bounds are within a constant factor of each other in the case of asynchronous tori.

We exploit the "regularity" of Boolean functions with the purpose of decreasing the time for constructing minimal three-level expressions, in the sum of pseudoproducts (SPP) form recently developed. The regularity of a Boolean function f of n variables can be expressed by an autosymmetry degree k (with 0 /spl les/ k /spl les/ n). k = 0 means no regularity, that is we are not able to provide any advantage over standard synthesis. For k /spl ges/ 1 the function f is said to be autosymmetric, and a new function f/sub k/ depending on n - k variables only, called the restriction of f, is identified in time polynomial in the number of points of f. The relation between f and f/sub k/ is discussed in depth to show how a minimal SPP form for f can be build in linear time from a minimal SPP form for f/sub k/. The concept of autosymmetry is then extended to functions with don't care conditions, and the SPP minimization technique is duly extended to such functions. A large set of experimental results is presented, showing that 61% of the outputs for the functions in the classical ESPRESSO benchmark suite are autosymmetric. The minimization time for such functions is critically reduced, and cases otherwise intractable are solved. The quality of the corresponding circuits, measured with some well established cost functions, is also improved. Finally, we discuss the role and meaning of autosymmetric functions, and why a great amount of functions of practical interest fall in this class.

Sum of Pseudoproducts (SPP) is a three level logic synthesis technique developed in recent years. In this framework we exploit the "regularity" of Boolean functions to decrease minimization time. Our main results are: 1) the regularity of a Boolean function f of n variables is expressed by its autosymmetry degree k (with 0 ≤ k ≤ n), where k = 0 means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for k ≥ 1 the function is autosymmetric, and a new function fk is identified in polynomial time; fk is "equivalent" to, but smaller than f, and depends on n-k variables only; 3) given a minimal SPP form for fk a minimal SPP form for f is built in linear time; 4) experimental results show that 61% of the functions in the classical Espresso benchmark suite are autosymmetric, and the SPP minimization time for them is critically reduced; we can also solve cases otherwise practically intractable. We finally discuss the role and meaning of autosymmetry.

We reopen the issue of finding an implicit data structure for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n locations of an array in such a way that we can efficiently perform the operations insert, delete and search. No information other than n and the data is to be retained; and the only operations which we may perform on the data values (other than reads and writes) are comparisons. Our structure supports these operations in O(log/sup 2/ n/log log n) time, marking the first improvement on the problem since the mid 1980's. En route we develop a number of space efficient techniques for handling segments of a large array in a memory hierarchy. We achieve a cost of O(log/sub B/ n) block transfers like in regular B-trees, under the realistic assumption that a block stores B = /spl Omega/(log n) keys, so that reporting r consecutive keys in sorted order has a cost of O(log/sub B/n+r/B) block transfers. Being implicit, our B-tree occupies exactly [n/B] blocks after each update.

We introduce the new masked interval routing scheme (MIRS), where a mask is added to each interval to indicate particular subsets of `consecutive' labels. We show that the interval information stored in the network is drastically reduced in some hard cases, proving first that in globe graphs of O$(N)$ vertices the number of intervals per edge goes down from $\Omega(\sqrt{N})$, as required in the classical interval routing scheme (IRS), to O$(\log N)$ in MIRS. The technique is also extended to globe graphs of arbitrary dimensions. The advantage of using MIRS is then demonstrated for butterfly graphs, where we prove that the number of intervals per edge goes down from $\Omega(\sqrt{{N}/{\log N}})$ to O$(\log N)$. This paper is aimed at introducing a new technique. The examples provided show that MIRS is powerful to some extent in the reduction of the number of labels, and may be useful in practice. This work represents a possible new direction for further research.

Consider a hypercube of 2/sup n/ points described by n Boolean variables and a subcube of 2/sup m/ points, m/spl les/n. As is well-known, the Boolean function with value 1 in the points of the subcube can be expressed as the product (AND) of n-m variables. The standard synthesis of arbitrary functions exploits this property. We extend the concept of subcube to the more powerful pseudocube. The basic set is still composed of 2/sup m/ points, but has a more general form. The function with value 1 in a pseudocube, called pseudoproduct, is expressed as the AND of n-m EXOR-factors, each containing at most m+1 variables. Subcubes are special cases of pseudocubes and their corresponding pseudoproducts reduce to standard products. An arbitrary Boolean function can be expressed as a sum of pseudoproducts (SPP). This expression is in general much shorter than the standard sum of products, as demonstrated on some known benchmarks. The logical network of an n-bit adder is designed in SPP, as a relevant example of application of this new technique. A class of symmetric functions is also defined, particularly suitable for SPP representation.

We present a parallel algorithm to solve the visibility problem among n vertical segments in a plane, which can be implemented on a VLSI chip arranged as a mesh of trees. Our algorithm determines all the pairs of segments that "see" each other in time O(log n); while the fastest sequential algorithm requires O(n log n). A lower bound to the area-time complexity of this problem of O(n2 log2 n) is also derived.

The problem of sorting n elements using VLSI chips that can sort only q(q < n) elements at a time is considered. The proposed VLSI chip consists of a mesh of trees. Two classical algorithms, i.e., merge sort and bitonic sort, are modified to efficiently solve the external sorting problem using this chip.

A VLSI chip for performing relational data base operations is proposed. The chip is a tree of processors (TOP), where each chip has elementary storage and processing capabilities. A relation will be stored in the lowest levels of a TOP. More precisely, every m-tuple will occupy a subtree whose root is s= [log2(m+1)] =1 levels above the leaves. Denoting by h the height of the tree, the upper h-s levels will be used for routing and bookkeeping purposes. A number of basic operations such as allocate and deallocate subtrees, insert and compare m-tuples etc., are defined for the TOP's. Relational operations are effectively performed as simple combinations of basic operations. The architecture of a data base machine based on TOP's is also sketched. Such a machine is feasible with the current VLSI technology and could become attractive in few years if density and performance of VLSI keep improving at the current rate.

A new balancing technique for binary search trees is presented, based on the repositioning of k + 1 nodes (k-rotation) Some properties of k-rotation are shown, and bounds to k are derived. The performance of such a technique is discussed on the basis of the length of node search and the frequency of tree rebalancing.

Height-balanced binary trees with height unbalances up to Δ are investigated, and the asymptotic value of the height h of such trees is studied for an increasing number of nodes N. It is shown that, in the worst case, the asymptotic value of h is a logarithmic function of N: [h = K log N]n→∞. Specifically, an upper bound for h can be posed as: h ≤ K1log (N+2) - K2for Δ ≤ 3; and h ≤ K1log (N+K2) - K3for Δ = 4. Less strict bounds are posed for Δ > 4.