Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1996, Contents 31 December 1996

ISSN 1073–0486. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/

• http://www.cs.uchicago.edu/publications/cjtcs/

• ftp://mitpress.mit.edu/pub/CJTCS

• ftp://cs.uchicago.edu/pub/publications/cjtcs Editorial Contents 1996 (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1996 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in Computer Science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Ted Herman  Michael Merritt
Jin-Yi Cai  Steve Homer  Alan Selman
Anne Condon  Neil Immerman  Nir Shavit
Cynthia Dwork †Paris Kanellakis Eva Tardos
David Eppstein Howard Karloff  Sam Toueg
Ronald Fagin Philip Klein Moshe Vardi
Lance Fortnow Phokion Kolaitis Jennifer Welch
Steven Fortune Stephen Mahaney Pierre Wolper

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

Chicago Journal of Theoretical Computer Science 1996-Contents

Contents of Volume 1996

31 December, 1996

Contents

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

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

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

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

5. Uniform Self-Stabilizing Orientation of Unicyclic Networks under Read/Write Atomicity H. James Hoover 5 December 1996

6. Manhattan Channel Routing is NP-Complete under Truly Restricted Settings Martin Middendorf 30 December 1996

1

Chicago Journal of Theoretical Computer Science 1996-Contents