1. Rank Predicates vs. Progress Measures in Concurrent-Program Verification by Moshe Y. Vardi, 9 February 1996

   This note describes a direct relationship between rank predicates and progress measures in concurrent-program verification.

2. Sparse Hard Sets for P Yield Space-Efficient Algorithms by Mitsunori Ogihara, 27 March 1996

   In 1978, Hartmanis conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P is a subset of DSPACE[log^2 n].

3. Optimal Virtual Path Layout in ATM Networks with Shared Routing Table Switches by Ornan Gerstel, Israel Cidon, and Shmuel Zaks, 31 October 1996.

   In this paper we present a new model for routing that occurs in high-speed ATM networks. Within this model we define a general routing problem, called a virtual path layout. Given a network of nodes (switches) and links, one must find a set of paths in the network, termed the virtual path layout, whereby each pair of nodes may connect using a route that is a concatenation of a small number of virtual paths and is also short in terms of the network links it traverses. Each such layout implies a utilization of the routing tables in the network's nodes. Our goal is to find a layout that minimizes this utilization, assuming that each such node has a central routing table. We prove that this problem is NP-complete, and consequently focus on a simpler problem, in which it is required to connect all nodes to a single switch. Next, we prove that even this problem is NP-complete, and restrict some of the assumptions to yield a practical subproblem, for which we present a polynomial-time greedy algorithm that produces an optimal solution. Finally, we use this restricted problem as a building block in finding a suboptimal solution to the original problem. The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.

4. Weakly Growing Context-Sensitive Grammars by Gerhard Buntrock and Gundula Niemann, 13 November 1996.

   This paper introduces weakly growing context-sensitive grammars. Such grammars generalize the class of growing context-sensitive grammars (studied by several authors), in that these grammars have rules that "grow" according to a position valuation.

   If a position valuation coincides with the initial part of an exponential function, it is called a steady position valuation. All others are called unsteady. The complexity of the language generated by a grammar depends crucially on whether the position valuation is steady or not. More precisely, for every unsteady position valuation, the class of languages generated by WGCSGs with this valuation coincides with the class CSL of context-sensitive languages. On the other hand, for every steady position valuation, the class of languages generated corresponds to a level of the hierarchy of exponential time-bounded languages in CSL. We show that the following three conditions are equivalent:

   • The hierarchy of exponential time-bounded languages in CSL collapses.
   • There exists a class defined by an unsteady position valuation such that there is also a normal form of order 2 (e.g., Cremers or Kuroda normal form) for that class.
   • There exists a class defined by a steady position valuation that is closed under inverse homomorphisms.
5. Uniform Self-Stabilizing Orientation of Unicyclic networks under Read/Write Atomicity by H. James Hoover and Piotr Rudnicki, 5 December 1996.

   A distributed system is self-stabilizing if its behavior is correct regardless of its initial state. A ring is a distributed system in which all processors are connected in a cycle and each processor communicates directly with only its two neighbors. A ring is oriented when all processors have a consistent notion of their left and right neighbors. A ring is uniform when all processors run the same program and have no distinguishing attributes, such as processor IDs. A well-known self-stabilizing uniform protocol for ring orientation is that of [Israeli, Jalfon]. For a ring of size n, this protocol will stabilize in expected On^2 processor activations. This assumes that processors are scheduled by a distributed demon---one in which the communication registers between processors can be atomically updated (a read followed by a write), and the processors have the ability to make random choices.

   This paper generalizes the notion of orienting a ring to that of orienting a unicyclic network, that is, a ring with trees attached. We present a very simple protocol for the self-stabilizing orientation of such unicyclic networks. It has the same expected On^2 processor activation performance as the Israeli and Jalfon protocol for rings. But ours works under the more general scheduling assumption of a read/write demon---one in which a read or write of a communication register is atomic, but an update (a read followed by a write) is not. We similarly assume the ability to make random choices. A subresult of our protocol is a uniform self-stabilizing algorithm for the two processor token-passing problem under the read/write demon.

   Our protocol is uniform in the sense that all processors of the same degree are identical. In addition, observations of the behavior of the protocol on an edge yield no information about the degree of the processors at the ends of the edge.

6. Manhattan Channel Routing is NP-complete Under Truly Restricted Settings by Martin Middendorf, 30 December 1996.

   Settling an open problem that is over ten years old, we show that Manhattan channel routing---with doglegs allowed---is NP-complete when all nets have two terminals. This result fills the gap left by Szymanski, who showed the NP-completeness for nets with four terminals. Answering a question posed by Schmalenbach and Greenberg, Jájá, and Krishnamurty, we prove that the problem remains NP-complete if in addition the nets are single-sided and the density of the bottom nets is at most one. Moreover, we show that Manhattan channel routing is NP-complete if the bottom boundary is irregular and there are only 2-terminal top nets. All of our results also hold for the restricted Manhattan model where doglegs are not allowed.

Volume 1995 Abstracts

Volume 1997 Abstracts

Volume 1996

Published articles

Last modified: 11 March 1997