% The Chicago Journal of Theoretical Computer Science, Volume 1996, Abstracts
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1996 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,contents]{cjstruct}
\else
\documentclass[v1.1,contents]{cjstruct}
\fi
%
\newcommand{\textuprm}[1]{\textup{\textrm{#1}}}
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textrm}[1]{{\rm #1\/}}\fi
\mathstyleclass{\complexityclass}{\mathord}{\textuprm}
\mathstyleclass{\classoflang}{\mathord}{\textsl}
\mathstyleclass{\classofgrammar}{\mathord}{\textsl}
\newcommand\nohyphenl[1]{{\discretionary{}{}{}{#1}}}
\newcommand{\orderof}[1]{O(#1)}
%
\ifltwoe\else\newcommand{\textmd}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
%
\newcommand{\cjabsheadind}{\hspace*{1em}}
%
\newlength{\cjabsparwidth}
\newlength{\cjabspardec}
\settowidth{\cjabspardec}{\cjabsheadind}
\newlength{\cjabslabdec}
\setlength{\cjabslabdec}{1.4em}
%
\newcommand{\cjabshead}[4]{\par\addvspace{\bigskipamount}{%
  \setlength{\cjabsparwidth}{\textwidth}
  \subsection*{{%
    #1.
    \addtolength{\cjabsparwidth}{-\cjabslabdec}
    \parbox[t]{\cjabsparwidth}{{\raggedright #2\\
      \addtolength{\cjabsparwidth}{-\cjabspardec}
      \cjabsheadind\parbox[t]{\cjabsparwidth}{{\raggedright\textmd{#3}\\
        \cjabsheadind\parbox[t]{\cjabsparwidth}{\raggedright\textmd{\textit{#4}}}
      }}%
    }}%
  }}%
}}%
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
%
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D}}\)}
%
% Macros for the editors' comment
%
% The cross symbol indicates a recently deceased editor.
%
\ifx\deceased\undeftex
  \newcommand{\deceased}[1]{\dag#1}
\fi
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1996, Abstracts\\
      {\it 31 December 1996}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142; (617)253-2889; {\em journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{ftp://mitpress.mit.edu/pub/CJTCS}
    \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs}
  \end{itemize}
  \sentence
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert,\registered
  SciSearch,\registered Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered}
}
%
\copyrightstmt{%
  \copyright 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;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The {\em 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\@.
  \par
  \begin{trivlist}
    \item[{\em Editor in chief:}] Janos Simon
    \item[{\em Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[{\em Editors:}]
      \begin{tabular}[t]{lll}
        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\'o 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 & \deceased{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
      \end{tabular}
    \vspace{1ex}
    \item[{\em Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[{\em Electronic mail:}] {\em chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1996}
%
\articleid{Abstracts}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Abstracts from Volume 1996}
\shorttitle{Abstracts 1996}
\collectiontitle{}
%
\shortauthors{Editorial}
%
\begin{editinfo}
  \published{31}{12}{1996}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}
%
\cjabshead{1}{%
  Rank Predicates vs.\ Progress Measures in Concurrent-Program Verification%
}%
  {Moshe~Y.~Vardi}%
  {9 February 1996}
%
\apar{1. Abstract-1}
This note describes a direct relationship between rank predicates and
progress measures in concurrent-program verification.
%
\cjabshead{2}{%
  Sparse Hard Sets for P Yield Space-Efficient Algorithms%
}%
  {Mitsunori Ogihara}%
  {27 March 1996}
%
\apar{2. Abstract-1}
In 1978, Hartmanis conjectured that there exist no sparse complete
sets for \(\complexityclass{P}\) under logspace many-one reductions\@.
In this paper, in support of the conjecture, it is shown that if
\(\complexityclass{P}\) has sparse hard sets under logspace many-one
reductions, then
\(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\)\@.
%
\cjabshead{3}{%
  Optimal Virtual Path Layout in ATM Networks with Shared Routing
  Table Switches%
}%
  {Ornan Gerstel, Israel Cidon, Shmuel Zaks}%
  {31 October 1996}
%
\apar{3. Abstract-1}
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\@.
%
\cjabshead{4}{%
  Weakly Growing Context-Sensitive Grammars%
}%
  {Gerhard Buntrock, Gundula Niemann}%
  {13 November 1996}
%
\apar{4. Abstract-1}
This paper introduces \emph{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\@.
%
\apar{4. Abstract-2}
If a position valuation coincides with the initial part of an
exponential function, it is called a \emph{steady} position
valuation\@. All others are called \emph{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
\(\classofgrammar{WGCSG}\)s with this valuation coincides with the
class \(\classoflang{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 \(\classoflang{CSL}\)\@. We show that the
following three conditions are \nohyphenl{equivalent}:
%
\begin{itemize}
%
\item The hierarchy of exponential time-bounded languages in
\(\classoflang{CSL}\) collapses\@.
%
\item 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\@.\pagebreak[2]
%
\item There exists a class defined by a steady position valuation that
is closed under inverse homomorphisms\@.
%
\end{itemize}
%
\cjabshead{5}{%
  Uniform Self-Stabilizing Orientation of Unicyclic Networks under
  Read/Write Atomicity%
}%
  {H.\ James Hoover}%
  {5 December 1996}
%
\apar{5. Abstract-1}
A distributed system is \emph{self-stabilizing} if its behavior is
correct regardless of its initial state\@. A \emph{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 \emph{oriented} when all processors have a
consistent notion of their left and right neighbors\@. A ring is
\emph{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
Greenberg, J\'aj\'a, and Krishnamurthy\@. For a ring of size \(n\),
this protocol will stabilize in expected
\(\orderof{n^2}\) processor activations\@. This assumes that processors
are scheduled by a \emph{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\@.
%
\apar{5. Abstract-2}
This paper generalizes the notion of orienting a ring to that of
orienting a \emph{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
\(\orderof{n^2}\) processor activation performance as the Israeli and Jalfon
protocol for rings\@. But ours works under the more general scheduling
assumption of a \emph{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\@.
%
\apar{5. Abstract-3}
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\@.
%
\cjabshead{6}{%
  Manhattan Channel Routing is NP-Complete under Truly Restricted
  Settings%
}%
  {Martin Middendorf}%
  {30 December 1996}
%
\apar{6. Abstract-1}
Settling an open problem that is over ten years old, we show that
Manhattan channel routing---with doglegs allowed---is
\(\complexityclass{NP}\)-complete when all nets have two terminals\@.
This result fills the gap left by Szymanski, who showed the
\(\complexityclass{NP}\)-completeness for nets with four
terminals\@. Answering a question posed by Schmalenbach and Greenberg,
J\'aj\'a, and Krishnamurty, we prove that the problem remains
\(\complexityclass{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
\(\complexityclass{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\@.
%
\end{articletext}
%
\end{document}