We give improved lower bounds for M(n, d), for various positive integers d and n with d <; n, where M(n, d) is the largest number of permutations on n symbols with pairwise Hamming distance at least d. Permutation arrays are used for constructing error correcting permutation codes, which have been proposed for power-line communications. We describe two techniques, which use a modified Kronecker product and a tiling operation, called doubling. Our techniques improve the size of permutation arrays, and improve lower bounds on M(n, d), for infinitely many n and d, d <; n.

Abstract This article is motivated by versions of the dynamic or “on‐line” Steiner tree problem (OST) introduced by Imase and Waxman [ 4 ]. In this problem one is given an edge‐weighted graph G and a sequence σ = (x1,…,xn) of distinct vertices of G. The requirement is to construct for each i ≤ n a tree Ti spanning the first i vertices of σ subject to the condition that Ti−1⫅Ti for all i, where Ti is constructed without knowledge of the remaining vertices xj, j > i. The goal of the on‐line Steiner problem is to minimize the performance ratio; that is, the maximum (over 1 ≤ i ≤ n) of the ratio of the weight of Ti to the weight of the minimum weight tree in G spanning the first i vertices (the latter tree is called the “Steiner tree” for these vertices). In [ 4 ] a lower bound of 1 + ½⌊ log2(n−1)⌋ was proved for this ratio. The authors further made the interesting conjecture that there is some on‐line algorithm for the OST whose performance ratio achieves this lower bound. We show that a strong form of the greedy algorithm achieves a ratio that converges to the conjectured ½log2(k) + O(1) as the proportion of degree 2 vertices in the instance graph grows. Our results also imply improvements in certain cases on the known upper bound ⌈log2(n)⌉ for the performance ratio of the greedy algorithm. Our approach is to study a related graph parameter. For each sequence σ as above, define the associated cost where c(i,σ) = min1 ≤ t < idist(xi, xt). Then let Opt(n, G) be the maximum of L(σ) over all such sequences σ of length n. The problem of, given n and G, determining Opt(n, G) we call the Sequential Sum Problem (SSP). In this article we analyze the SSP, obtaining exact values and bounds on Opt(n, G) and relating these bounds to the greedy algorithm for the OST. For example, we calculate Opt(n, P) for the path P, and obtain a surprising characterization of all length n sequences σ which realize Opt(n, P). By analyzing Opt(n, P) for the “continuous” path, we derive upper bounds on the performance ratio of the greedy algorithm for the OST in arbitrary graphs. On the other hand, generalizing the lower bound argument of [ 4 ] we show that there are instances of OST, which can significantly “fool” any on‐line algorithm for OST. Specifically, given any tree T normalized to have total edge weight 1, we construct a graph G and a length k ≤ |V(T)| sequence σ of vertices of G for which the performance ratio of any on‐line algorithm for the OST with input σ is lower bounded by Opt(k, T). Finally, we show that the SSP for arbitrary G is NP‐complete. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 143–164 2005

The pancake problem concerns the number of prefix reversals ("flips") needed to sort the elements of an arbitrary permutation, which is the diameter of the n-dimensional pancake network. We restrict the problem by allowing only a few of the possible n-1 flips. Let f/sub i/ denote a flip of size i. We consider sets with either O(1) flips or log/sub 2/ n flips, and explore their corresponding Cayley networks, such as: The Subcube/sub n/ network, for n=2/sup k/, defined by the log/sub 2/ n flips {f/sub 2/,f/sub 4/,f/sub 8/...f/sub n/}. Subcube/sub n/ is isomorphic to a network obtained from an (n-1) dimensional hypercube, Q/sub n-1/, by deleting all but log/sub 2/ n of the edges incident to each of its nodes, has diameter (3n/2)-2 (we give an optimum routing algorithm), and hosts Q/sub n-1/ with nearly optimum dilation. The Triad/sub n/ network where n is odd and [n/2] mod 4/spl ne/0, defined by the set of flips {f[n/2] f[n/2] f/sub n/}. Triad/sub n/ has n! nodes and diameter /spl Theta/(n log/sub 2/ n). Both the n-dimensional shuffle-exchange and shuffle-exchange permutation networks can be emulated by Triad/sub n/ with constant slowdown.

The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n).

Abstract Let G be a graph, and denote by Q(G)/2t the hypercube of dimension ⌈log2|G|⌉ − t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2t, t ⩾ 1, when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G‐processors in Q(G)/2t, Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of >f−1(h)| over all vertices hε(G)/2t. Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1, there is a map f :G → Q(G)/2t having dilation 1 and load factor at most 1 + 2t. (2) Given certain upper bounds on the “densities” |G|/|Q(G)/4| or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8, respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.

Simulations of hypercube networks by certain Cayley graphs on the symmetric group are investigated. Let Q(k) be the familiar k-dimensional hypercube, and let S(n) be the star network of dimension n defined as follows. The vertices of S(n) are the elements of the symmetric group of degree n, two vertices x and y being adjacent if xo(1,i)=y for some i. That is, xy is an edge if x and y are related by a transposition involving some fixed symbol (which we take to be /spl I.bold/1). This network has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages of S(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The first step in such a simulation is the construction of a one-to-one map f:Q(k)/spl rarr/S(n) of dilation d, for d small. That is, one wants a map f such that images of adjacent points are at most distance d apart in S(n). An alternative approach, best applicable when one-to-one maps are difficult or impossible to find, is the construction of a one-to-many map g of dilation d, defined as follows. For each point x/spl isin/Q(k), there is an associated subset g(x)/spl sube/V(S(n)) such that for each edge xy in Q(k), every x'/spl isin/g(x) is at most distance d in S(n) from some y'/spl isin/g(y). Such one-to-many maps allow one to achieve the low interprocessor communication time desired in the usual one-to-one embedding underlying a simulation. This is done by capturing the local structure of Q(k) inside of S(n) (via the one-to-many embedding) when the global structure cannot be so captured. Our results are the following. 1) There exist the following one-to-many embeddings: a) f:Q(k)/spl rarr/S(3k+1) with dilation (f)=1; b) f:Q(11k+2)/spl rarr/S(13k+2) with dilation (f)=2. 2) There exists a one-to-one embedding f:Q(n2/sup n/spl minus/1/)/spl rarr/S(2/sup n/) with dilation (f)=3.>

We consider primarily the simulation of large networks by smaller ones-an important consideration, because interconnection networks are typically of a fixed size, and yet applications may employ networks of a larger size. Current research (Dingle and Sudborough, 1993) describes methods to simulate common data structures and network architectures on the pyramid. However, these simulations assume that the pyramid grows with the size of the network or data structure. Because unbounded growth is not feasible, we address the issue of mapping several points of the guest data structure or network to a single host processor. We determine how a small pyramid may efficiently simulate the computation of a larger pyramid as well as that of tree networks.>

Difference bases are discussed and their relevance to sensor arrays is described. Several new analytical difference base structures that result in near optimal low-redundancy sensor arrays are introduced. Algorithms are also presented for efficiently obtaining sparse sensor arrays and/or difference bases. New bounds, related to arrays that have both redundancies and holes in their coarray, are presented. Some extensions to the idea of difference bases that may yield useful results for sensor array design are discussed.>

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in $O(n(\log n)^{d - 2} )$ steps. This has applications to integrated circuit layout, in particular the layout of Weinberger arrays [41]. This also yields an algorithm for determining the black/white pebble demand of degree three trees. We also show that for degree three trees, cutwidth is identical to search number and give a forbidden subgraph characterization of degree three trees having cutwidth k.

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.

Bandwidth restrictions are considered on several NP-Complete problems, including the following problems:

Let SPS(f(n)) denote the solvable path system problem for path systems of bandwidth f(n) and SPS (f(n)) the corresponding problem for monotone systems. Let DTISP (poly, f(n)) denote the polynomial time and simultaneous f(n) space class and SC = UkDTISP (poly, logkn). Let ASPACE (f(n)) denote the sets accepted by f(n) space bounded alternating TMs and ASPACE (f(n)) the corresponding one-way TM family. Then, for "well-behaved" functions fεO(n)-o(log n), (1) SPS (f(n)) is ≤log-complete for DTISP (poly, f(n)), (2) {SPS(f(n)k)}k≥1 is ≤log-complete for ASPACE (logf(n)), (3) {SPS (f(n)k)}k≥1 is ≤log-complete for ASPACE (log f(n)), (4) SPS(f(n)) ε DSPACE(f(n) × log n), (5) ASPACE(log f(n)) ⊆ UkDSPACE(f(n)k), and (6) SC = CLOSURE ≤log(ASPACE(log log n)).

Let DSPACE(L(n)) denote the family of languages recognized by deterministic L(n)-tape bounded Turmg machines The pnnopal result described m this paper is the equivalence of the following statements (l) The determtmsttc context-free language L~ 2) (described m the paper) is m DSPACE(Iog(n)) ( 2) The simple LL(I) languages are m DSPACE(tog(n)) (3) The simple precedence languages are in DSPACE(Iog(n)).(4) DSPACE(Iog(n)) is identical to the famdy of languages recogmzed by deterministic two-way multlhead pushdown automata m polynomml tmae These results are obtained by constructing a determlmstlc context-free language L~ 2~ which is log(n)-complete for the family of determlmstlc context-free languages In other words, a tape hardest deterministic context-free language is described The best upper bound known on the tape complexity of (deterministic) context-free languages is (log(n)) 2 KEY WORDS AND PHRASES deterministic context-free languages, tape complexity, stmple precedence languages, snnple LL(I) languages, Tunng machine, log(n)-tape reduclblhty, log(n) complete, polynomial time bounded multlhead pushdown automata, Dyck languages CR CATEGORIES 5 23, 5 25Lewis, Stearns, and Hartmanis [23] have described an algorithm to recognize every contextfree language by a deterministic (log(n))2-tape bounded Turing machine.In a recent paper [26] the author has shown that, if the context-free languages could be recogmzed by a determimstic log(n)-tape bounded Tunng machine, then nondetermmistic and deterministic L(n)-tape bounded complexity classes are identical, for L(n) >_ log(n).In this paper the tape complexity of determmisttc context-free languages is considered.It is shown that there is a single determmisttc context-free language L~ 2) which is recognized by a determinisUc [nondeterministic] log(n)-tape bounded Turing machine if, and only if, all deterministic context-free languages can be recognized by determmistic [nondetermimstic] log(n)-tape bounded Turing machines.Also, L~ 21 may be log(n)-tape reduced to a simple LL(I) language, as discussed by Korenjak and Hopcroft [221 and Aho and Ullman [2], and to a simple precedence language, as discussed by Wtrth and Weber [28] and Aho and Ullman [2].It is shown, therefore, that these proper subfamilies of the deterministic context-free languages are as difficult to recognize as the complete family of deterministic context-free languages.Furthermore, tt is shown that Lt02) is recognized by a determmisttc log(n)-tape bounded Turmg machine if, and only if, the family of languages recogmzed by deterministic multlhead two-way pushdown automata m polynomml time is identical to General permission to make fair use in teaching or research of all or part of this material IS granted to individual readers and to nonprofit hbrarles actmg for them provided that ACM's copyright notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting pnvdeges were granted by permission of the Association for Computing Machinery To otherwise repnnt a figure, table, other substantial excerpt, or the entire work reqmres speofic permission as does republication, or systematic or multiple reproduction Some of these results were presented at the

Previous results in the literature which describe separation theorems for time bounded complexity classes serve also to separate classes defined by tape bounded auxiliary pushdown automata. Results described here refine these basic relationships between classes defined by tape bounded AuxPDA. It is shown that, for auxiliary PDA fully constructable functions S0 and S1 satisfying S1 (n+1) ε o,(S0 (n)), S0 tape bounded AuxPDA are more powerful than S1 tape bounded AuxPDA. Further results refine the resulting separation by the number of worktape symbols and the number of worktape heads. Results are also described for separating classes defined by tape bounded AuxPDA with one pushdown store symbol, i.e. auxiliary counter automata (AuxCA). Refinements of the known equivalence of nondeterministic L(n)-tape bounded AuxPDA and deterministic L(n)-tape bounded AuxPDA are also described. One corollary is that every two-way nondeterministic PDA can be simulated by a two-way deterministic PDA with four input tape heads and that every context-free language can be recognized by a deterministic two-way PDA with three heads. Another corollary of these results shows that there are languages over a single letter alphabet which are recognized by (k+1)-head two-way PDA but cannot be recognized by any k-head two-way PDA. It is shown also that AuxPDA and AuxCA can fully construct very slow growing functions so that even small amounts of worktape space (e.g. that bounded by log*n) increase their computational power.

A deterministic context-free language L0 is described which is log(n)-complete for the family of languages recognized by deterministic log(n)- tape bounded auxiliary pushdown automata in polynomial time. It follows that L0 is a “hardest” deterministic context-free language (DCFL), since all DCFL's are recognized in polynomial time by deterministic pushdown automata. L0 is, moreover, a simple precedence language and a simple LL(1) language. Thus the tape complexities of these proper subfamilies are essentially the same as the tape complexity of all DCFL's.

There are essentially two results described in this paper. First, it is shown that for any random access machine (RAM) time-constructable function $T(n) \geqq n$, there are languages L such that L can be recognized in time $O(T(n))$ by a RAM (using the unit cost measure), but L cannot be recognized by any deterministic multitape Turing machine in time $O(T(n))$. Secondly, a family of random access stored program machines (RASP’S) are considered. For these RASP’S it is shown that there is an arbitrarily complex (infinitely often) partial recursive function $f(n)$. which has only 0–1 values (whenever defined) such that $f(n)$ can be computed in time $F(n)$ by some RASP, but cannot be computed in time $(1 - \varepsilon )F(n)$, for any $\varepsilon > 0$, by any RASP in this family.

No abstract available.