% 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}