Last update:
Fri Oct 20 15:21:03 MDT 2023
R. L. Graham An efficient algorithm for determining
the convex hull of a finite planar set 132--133
T. D. Bui On an $L$-stable method for stiff
differential equations . . . . . . . . . 158--161
A. Bykat Convex hull of a finite set of points in
two dimensions . . . . . . . . . . . . . 296--298
J. M. Morris A starvation-free solution to the mutual
exclusion problem . . . . . . . . . . . 76--80
Bengt Aspvall and
Michael F. Plass and
Robert Endre Tarjan A linear-time algorithm for testing the
truth of certain quantified Boolean
formulas . . . . . . . . . . . . . . . . 121--123
Alain Fournier Comments on convex hull of a finite set
of points in two dimensions [Inform.
Process. Lett. \bf 7 (1978), no. 6,
296--298; MR 80b:68041] . . . . . . . . 173--173
T. D. Bui Erratum: ``On an $L$-stable method for
stiff differential equations'' . . . . . 218--218
Charles J. Colbourn The complexity of symmetrizing matrices 108--109
F. Dévai and
T. Szendrényi Comments on convex hull of a finite set
of points in two dimensions . . . . . . 141--142
A. M. Andrew Another efficient algorithm for convex
hulls in two dimensions . . . . . . . . 216--219
Michael J. C. Gordon The denotational semantics of sequential
machines . . . . . . . . . . . . . . . . 1--3
H. Olivié On the relationship between son-trees
and symmetric binary $B$-trees . . . . . 4--8
V. J. Rayward-Smith and
R. N. Rolph Finding Linear and Circular Sequences of
Minimal and Maximal Total Adjacency . . 9--13
Peter Honeyman and
Richard E. Ladner and
Mihalis Yannakakis Testing the universal instance
assumption . . . . . . . . . . . . . . . 14--19
Ashoke Deb Conflict-free access of arrays --- a
counter example . . . . . . . . . . . . 20--20
Miros\law Truszczy\'nski Once more on storage for consecutive
retrieval . . . . . . . . . . . . . . . 21--24
Leslie M. Goldschlager A space efficient algorithm for the
monotone planar circuit value problem 25--27
Errol L. Lloyd List Scheduling Bounds for UET Systems
with Resources . . . . . . . . . . . . . 28--31
Carlo Zaniolo Mixed transitivity for functional and
multivalued dependencies in database
relations . . . . . . . . . . . . . . . 32--34
T. D. Bui A note on an improved bisection
algorithm . . . . . . . . . . . . . . . 35--36
Daniel D. K. D. B. Sleator A $2.5$ times optimal algorithm for
packing in two dimensions . . . . . . . 37--40
Dilip V. Sarwate A note on: ``Universal classes of hash
functions'' [J. Comput. System Sci. \bf
18 (1979), no. 2, 143--154; MR
80f:68110a] by J. L. Carter and M. N.
Wegman . . . . . . . . . . . . . . . . . 41--45
Bruce Anderson Encoded Pointers --- an Interesting
Data-Structure for Modern SIL's . . . . 47--50
Jan van Leeuwen and
Derick Wood Dynamization of decomposable searching
problems . . . . . . . . . . . . . . . . 51--56
V. K. Sabel\cprimefel\cprimed The logic-termal equivalence is
polynomial-time decidable . . . . . . . 57--62
Solomon Passy Structured programs for Turing machines 63--67
Thomas C. Wilson and
Joseph Shortt An $O(\log n)$ algorithm for computing
general order-$k$ Fibonacci numbers . . 68--75
Frank M. Liang A lower bound for on-line bin packing 76--79
Manuel Blum and
Ashok K. Chandra and
Mark N. Wegman Equivalence of free Boolean graphs can
be decided probabilistically in
polynomial time . . . . . . . . . . . . 80--82
Paul M. B. Vitányi Achievable high scores of
$\varepsilon$-moves and running times in
DPDA computations . . . . . . . . . . . 83--86
Nicola Santoro Extending the Four Russians' Bound to
General Matrix Multiplication . . . . . 87--88
Hanan Samet and
Leo Marcus Purging in an Equality Data Base . . . . 89--95
Mordechai Ben-Ari A simplified proof that regular
resolution is exponential . . . . . . . 96--98
Alexandre Brandwajn and
Rene Joly A scheme for a fault-tolerant virtual
memory . . . . . . . . . . . . . . . . . 99--103
Frank G. Pagan On the generation of compilers from
language definitions . . . . . . . . . . 104--107
M. Jazayeri An improvement in the iterative data
flow analysis algorithm . . . . . . . . 108--110
R. K. Arora and
S. P. Rana Analysis of the Module Assignment
Problem in Distributed Computing Systems
with Limited Storage . . . . . . . . . . 111--115
O. Watanabe Another application of recursion
introduction . . . . . . . . . . . . . . 116--119
Peter J. L. Wallis and
Bernard W. Silverman Efficient Implementation of the Ada
Overloading Rules . . . . . . . . . . . 120--123
C. Hemerik Formal derivation of a list processing
program . . . . . . . . . . . . . . . . 124--126
David G. Kirkpatrick A note on Delaunay and optimal
triangulations . . . . . . . . . . . . . 127--128
Patrick Shen-Pei Wang Some new results on isotonic array
grammars . . . . . . . . . . . . . . . . 129--131
Peter van Emde Boas On the $\Omega(n\log n)$ lower bound for
convex hull and maximal vector
determination . . . . . . . . . . . . . 132--136
Wojciech Cellary and
Daniel Mayer A simple model of query scheduling in
distributed data base systems . . . . . 137--147
J. A. Barnden A characterization of systems derived
from terminating concurrent histories 148--152
Ludwik Czaja Parallel System Schemas and Their
Relation to Automata . . . . . . . . . . 153--158
J. L. W. I. Kessels The readers and writers problem avoided 159--162
M. van der Nat A Fast Sorting Algorithm, a Hybrid of
Distributive and Merge Sorting . . . . . 163--167
A. M. Andrew Corrigendum: ``Another efficient
algorithm for convex hulls in two
dimensions'' (Inform. Process. Lett. \bf
9 (1979), no. 5, 216--219) . . . . . . . 168--168
Robert Melville and
David Gries Controlled Density Sorting . . . . . . . 169--172
Alan A. Bertossi On the complexity of scheduling jobs on
dedicated resources to minimize set-up
costs . . . . . . . . . . . . . . . . . 173--177
Aviezri S. Fraenkel and
Yaacov Yesha Complexity of solving algebraic
equations . . . . . . . . . . . . . . . 178--179
F. Luccio and
S. Mazzone A cryptosystem for multiple
communication . . . . . . . . . . . . . 180--183
Thomas Lengauer and
Robert E. Tarjan The space complexity of pebble games on
trees . . . . . . . . . . . . . . . . . 184--188
Arthur M. Farley Levelling Terrain Trees: a Transshipment
Problem . . . . . . . . . . . . . . . . 189--192
M. Broy and
M. Wirsing Program development: from enumeration to
backtracking . . . . . . . . . . . . . . 193--197
F. W. Burton and
G. N. Lewis A robust variation of interpolation
search . . . . . . . . . . . . . . . . . 198--201
Carla Savage Maximum matchings and trees . . . . . . 202--205
R. W. Doran and
L. K. Thomas Variants of the software solution to
mutual exclusion . . . . . . . . . . . . 206--208
Mark H. Overmars and
Jan van Leeuwen Further comments on A. Bykat's convex
hull algorithm: ``Convex hull of a
finite set of points in two dimensions''
[Inform. Process. Lett. \bf 7 (1978),
no. 6, 296--298; MR 80b:68041] . . . . . 209--212
Henk Meijer and
Selim G. Akl The Design and Analysis of a New Hybrid
Sorting Algorithm . . . . . . . . . . . 213--218
Akira Nakamura and
Katsushi Inoue A remark on two-dimensional finite
automata: ``Some properties of
two-dimensional on-line tessellation
acceptors'' [Inform. Sci. \bf 13 (1977),
no. 2, 95--121; MR 80e:68143] . . . . . 219--222
A. Ehrenfeucht and
G. Rozenberg On the emptiness of the intersection of
two D0S languages problem . . . . . . . 223--225
K. M. Chung and
F. Luccio and
C. K. Wong A new permutation algorithm for bubble
memories . . . . . . . . . . . . . . . . 226--230
Corrado Böhm and
Antonio Mach\`i and
Giovanna Sontacchi Complexity bounds for equivalence and
isomorphism of Latin squares . . . . . . 231--233
Ludwik Czaja Deadlock and Fairness in Parallel
Schemas: a Set-Theoretic
Characterization and Decision Problems 234--239
Kellogg S. Booth Lexicographically least circular
substrings . . . . . . . . . . . . . . . 240--242
Peter Buneman and
Leon Levy The Towers of Hanoi problem . . . . . . 243--244
Katsushi Inoue and
Itsuo Takanami A note on decision problems for
three-way two-dimensional finite
automata . . . . . . . . . . . . . . . . 245--248
Edsger W. Dijkstra and
C. S. Scholten Termination detection for diffusing
computations . . . . . . . . . . . . . . 1--4
W\lodzimierz Dobosiewicz An Efficient Variation of Bubble Sort 5--6
D. C. S. Allison and
M. T. Noga Selection by distributive partitioning 7--8
Tomasz Krawczyk Error correction by mutational grammars 9--15
Kabekode V. S. Bhat On the complexity of testing a graph for
$n$-cube . . . . . . . . . . . . . . . . 16--19
Jan Grabowski The decidability of persistence for
vector addition systems . . . . . . . . 20--23
Michael C. Loui A note on the pebble game . . . . . . . 24--26
J. D. Day On the internal $S$-stability of
Rosenbrock methods . . . . . . . . . . . 27--30
J. D. Day Comments on: ``On an $L$-stable method
for stiff differential equations''
[Inform. Process. Lett. 6 (1977), no. 5,
158--161; MR \bf 56 #10015] by T. D. Bui 31--32
G. Loizou On a cycle finding algorithm . . . . . . 33--36
Donna J. Brown An improved BL lower bound . . . . . . . 37--39
J. L. Peterson A note on colored Petri nets . . . . . . 40--43
L. G. Valiant Computing multivariate polynomials in
parallel . . . . . . . . . . . . . . . . 44--45
R. P. Brent On the area of binary tree layouts . . . 46--48
Charles R. Dyer A fast parallel algorithm for the
closest pair problem . . . . . . . . . . 49--52
Luc Devroye A note on finding convex hulls via
maximal vectors . . . . . . . . . . . . 53--56
E. L. Lloyd Errata: ``List scheduling bounds for UET
systems with resources'' [Inform.
Process. Lett. \bf 10 (1980), no. 1,
28--31; MR 81a:68042] . . . . . . . . . 57--57
J. van Leeuwen and
D. Wood Errata: ``List scheduling bounds for UET
systems with resources'' [Inform.
Process. Lett. \bf 10 (1980), no. 1,
28--31; MR 81a:68042] . . . . . . . . . 57--57
Lech Banachowski A complement to Tarjan's result about
the lower bound on the complexity of the
set union problem . . . . . . . . . . . 59--65
Friedrich J. Urbanek An $O(\log n)$ algorithm for computing
the $n$th element of the solution of a
difference equation . . . . . . . . . . 66--67
David Gries and
Gary Levin Computing Fibonacci numbers (and
similarly defined functions) in log time 68--69
Jürgen Ebert A note on odd and even factors of
undirected graphs . . . . . . . . . . . 70--72
Lishing Liu and
Alan Demers An algorithm for testing lossless join
property in relational databases . . . . 73--76
Franco P. Preparata and
Jean E. Vuillemin Area-Time Optimal VLSI Networks for
Multiplying Matrices . . . . . . . . . . 77--80
K. M. Chung and
F. Luccio and
C. K. Wong Minimum number of steps for permutation
in a bubble memory . . . . . . . . . . . 81--83
Andrew C. Yao A Note on the Analysis of Extendible
Hashing . . . . . . . . . . . . . . . . 84--86
M. Broy Transformational Semantics for
Concurrent Programs . . . . . . . . . . 87--91
Robert B. Johnson, Jr. The complexity of a VLSI adder . . . . . 92--93
J. Calmet and
R. Loos An improvement of Rabin's probabilistic
algorithm for generating irreducible
polynomials over GF($p$) . . . . . . . . 94--95
Charles J. Colbourn and
Brendan D. McKay A correction to Colbourn's paper on the
complexity of matrix symmetrizability:
``The complexity of symmetrizing
matrices'' [Inform. Process. Lett. \bf 9
(1979), no. 3, 108--109; MR 81a:68045] 96--97
Paris C. Kanellakis On the computational complexity of
cardinality constraints in relational
databases . . . . . . . . . . . . . . . 98--101
E. Luque and
A. Ripoll Tuning Architecture via Microprogramming 102--109
E. Leiss A note on a signature system based on
probabilistic logic . . . . . . . . . . 110--113
Joseph Y.-T. Leung and
M. L. Merrill A note on preemptive scheduling of
periodic, real-time tasks . . . . . . . 115--118
J. M. Robson Storage allocation is NP-hard . . . . . 119--125
David Avis Comments on a lower bound for convex
hull determination: ``On the
$\Omega(n\log n)$ lower bound for convex
hull and maximal vector determination''
by van Emde Boas [Inform. Process. Lett.
\bf 10(3), 18 April 1980, pp. 132--136] 126--126
Arnaldo Moura A note on grammatical covers . . . . . . 127--129
T. A. Bailey and
R. G. Dromey Fast string searching by finding subkeys
in subtext . . . . . . . . . . . . . . . 130--133
Francesco Romani Shortest-path problem is not harder than
matrix multiplication . . . . . . . . . 134--136
H. Erkio Internal merge sorting with delayed
selection . . . . . . . . . . . . . . . 137--140
N. Dershowitz The Schorr--Waite marking algorithm
revisited . . . . . . . . . . . . . . . 141--143
E. B. Kinber On inclusion problem for deterministic
multitape automata . . . . . . . . . . . 144--146
A. Laut Safe procedural implementations of
algebraic types . . . . . . . . . . . . 147--151
J. Paredaens and
F. Ponsaert Grant levels in an authorization
mechanism . . . . . . . . . . . . . . . 152--155
Greg N. Frederickson Probabilistic analysis for simple one-
and two-dimensional bin packing
algorithms . . . . . . . . . . . . . . . 156--161
Oscar H. Ibarra and
Shlomo Moran and
Louis E. Rosier A note on the parallel complexity of
computing the rank of order $n$ matrices 162--162
D. R. Hanson Code improvement via lazy evaluation . . 163--167
J. H. ter Bekke Convertibility in databases . . . . . . 168--171
Alberto Pettorossi Derivation of an $O(k^2\,\log n)$
algorithm for computing order-$k$
Fibonacci numbers from the $O(k^3\,\log
n)$ matrix multiplication method . . . . 172--179
M. H. Williams Cubic map configurations . . . . . . . . 180--185
M. H. Williams Batch sizes for the batching method of
colouring planar maps . . . . . . . . . 186--189
Mila E. Majster-Cederbaum A simple relation between relational and
predicate transformer semantics for
nondeterministic programs . . . . . . . 190--192
Rossella Petreschi and
Bruno Simeone A switching algorithm for the solution
of quadratic Boolean equations . . . . . 193--198
R. K. Arora and
S. P. Rana Heuristic algorithms for process
assignment in distributed computing
systems . . . . . . . . . . . . . . . . 199--203
Hiroya Kawai A formal system for parallel programs in
discrete time and space . . . . . . . . 204--210
J. ten Hoopen Consecutive retrieval with redundancy:
an optimal linear and an optimal cyclic
arrangement and their storage space
requirements . . . . . . . . . . . . . . 211--217
Peter Kandzia and
Margret Mangelmann On covering Boyce-Codd normal forms . . 218--223
Seppo Pajunen On two theorems of Lenstra . . . . . . . 224--228
Alfons J. Jammel and
Helmut G. Stiegler On expected costs of deadlock detection 229--231
S. Mauceri and
A. Restivo A family of codes commutatively
equivalent to prefix codes . . . . . . . 1--4
Krzysztof Dudzi\'nski and
Andrzej Dydek On a Stable Minimum Storage Merging
Algorithm . . . . . . . . . . . . . . . 5--8
Eugene L. Lawler and
Charles U. Martel Scheduling Periodically Occurring Tasks
on Multiple Processors . . . . . . . . . 9--12
C. Choffrut A closure property of deterministic
context-free languages . . . . . . . . . 13--16
Nai Kuan Tsao The numerical instability of Bini's
algorithm . . . . . . . . . . . . . . . 17--19
Harold N. Gabow A linear-time recognition algorithm for
interval dags . . . . . . . . . . . . . 20--22
Dorothy E. Denning and
Fred B. Schneider Master keys for group sharing . . . . . 23--25
Eric C. R. Hehner Bunch theory: a simple set theory for
computer science . . . . . . . . . . . . 26--30
S. H. Whitesides An algorithm for finding clique cut-sets 31--32
P. Hell and
D. G. Kirkpatrick On generalized matching problems . . . . 33--35
M. Bruynooghe Solving combinatorial search problems by
intelligent backtracking . . . . . . . . 36--39
Errol L. Lloyd Coffman--Graham scheduling of UET task
systems with $0$-$1$ resources . . . . . 40--45
S. Ceri and
G. Pelagatti An upper bound on the number of
execution nodes for a distributed join 46--48
Mark H. Overmars and
Jan van Leeuwen Some principles for dynamizing
decomposable searching problems . . . . 49--53 (or 49--54??)
M. Hatzopoulos and
J. G. Kollias Optimal policy for database backup and
recovery . . . . . . . . . . . . . . . . 55--58
D. M. Harland Concurrency in a language employing
messages . . . . . . . . . . . . . . . . 59--62
Ingemar Ingemarsson and
C. K. Wong A user authentication scheme for shared
data based on a trap-door one-way
function . . . . . . . . . . . . . . . . 63--67
J. J. Pansiot The Morse sequence and iterated
morphisms . . . . . . . . . . . . . . . 68--70
A. Borodin and
L. J. Guibas and
N. A. Lynch and
A. C. Yao Efficient searching using partial
ordering . . . . . . . . . . . . . . . . 71--75
C. P. Schnorr How many polynomials can be approximated
faster than they can be evaluated? . . . 76--78
Joxan Jaffar Presburger arithmetic with array
segments . . . . . . . . . . . . . . . . 79--82
David Steinberg and
Michael Rodeh A layout for the shuffle-exchange
network with $\Theta(N^2\log N)$ area 83--88
Yossi Shiloach Another look at the degree constrained
subgraph problem . . . . . . . . . . . . 89--92
Kurt Mehlhorn and
Mark H. Overmars Optimal dynamization of decomposable
searching problems . . . . . . . . . . . 93--98
Mark H. Overmars General methods for ``all elements'' and
``all pairs'' problems . . . . . . . . . 99--102
Silvio Micali Two-way deterministic finite automata
are exponentially more succinct than
sweeping automata . . . . . . . . . . . 103--105
Martin Tompa An extension of Savitch's theorem to
small space bounds . . . . . . . . . . . 106--108
R. Petreschi and
B. Simeone Erratum: ``A switching algorithm for the
solution of quadratic Boolean
equations'' . . . . . . . . . . . . . . 109--109
Bruno Courcelle The simultaneous accessibility of two
configurations of two equivalent DPDAs 111--114
G. L. Peterson Myths about the mutual exclusion problem 115--116
W. Leland and
R. Finkel and
Li Qiao and
M. Solomon and
L. Uhr High density graphs for processor
interconnection . . . . . . . . . . . . 117--120
Ronald V. Book The undecidability of a word problem: on
a conjecture of Strong,
Maggiolo-Schettini and Rosen . . . . . . 121--122
Gerhard Lischke Two types of properties for complexity
measures . . . . . . . . . . . . . . . . 123--126
Reinhard Wilhelm A modified tree-to-tree correction
problem . . . . . . . . . . . . . . . . 127--132
Robert J. Fowler and
Michael S. Paterson and
Steven L. Tanimoto Optimal packing and covering in the
plane are NP-complete . . . . . . . . . 133--137
Jerzy W. Jaromczyk Linear decision trees are too weak for
convex hull problem . . . . . . . . . . 138--141
Alberto Bertoni and
Giancarlo Mauri On Efficient Computation of the
Coefficients of Some Polynomials with
Applications to Some Enumeration
Problems . . . . . . . . . . . . . . . . 142--145
W. Erni and
R. Lapsien On the time and tape complexity of weak
unification . . . . . . . . . . . . . . 146--150
P. Ancilotti and
M. Boari Information Streams Sharing a Finite
Buffer: Protection Problems . . . . . . 151--159
Franco P. Preparata and
Kenneth J. Supowit Testing a simple polygon for
monotonicity . . . . . . . . . . . . . . 161--164
C. M. Eastman Optimal bucket size for nearest neighbor
searching in $k$-$d$ trees . . . . . . . 165--167
M. H. Overmars and
J. van Leeuwen Worst-case optimal insertion and
deletion methods for decomposable
searching problems . . . . . . . . . . . 168--173
C. Frougny Simple deterministic NTS languages . . . 174--178
H. Meijer A note on ``A cryptosystem for multiple
communication'' [Inform. Process. Lett.
\bf 10(4--5), 5 July 1980, pp. 180--183] 179--181
M. E. Hellman Another cryptanalytic attack on ``A
cryptosystem for multiple
communication'' [Inform. Process. Lett.
\bf 10(4--5), 5 July 1980, pp. 180--183] 182--183
T. Ottmann and
A. Salomaa and
D. Wood Sub-regular grammar forms . . . . . . . 184--187
Ichir\=o Semba Generation of all the balanced
parenthesis strings in lexicographical
order . . . . . . . . . . . . . . . . . 188--192
Aldo de Luca A combinatorial property of the
Fibonacci words . . . . . . . . . . . . 193--195
E. C. R. Hehner and
R. K. Shyamasundar An implementation of $P$ and $V$ . . . . 196--198
D. Maier and
S. C. Salveter Hysterical $B$-trees . . . . . . . . . . 199--202
Christos H. Papadimitriou and
Mihalis Yannakakis On minimal Eulerian graphs . . . . . . . 203--205
Masao Iri and
Kazuo Murota and
Shouichi Matsui Linear-Time Approximation Algorithms for
Finding the Minimum-Weight Perfect
Matching on a Plane . . . . . . . . . . 206--209
J. Mauney and
C. N. Fischer An improvement to immediate error
detection in Strong LL(1) parsers . . . 211--212
Lloyd K. Konneker and
Yaakov L. Varol A note on heuristics for dynamic
organization of data structures . . . . 213--216
M. Snir On the complexity of simplifying
quadratic forms . . . . . . . . . . . . 217--220
David M. Harland On Facilities for Interprocess
Communication . . . . . . . . . . . . . 221--226
Oscar H. Ibarra and
Shlomo Moran and
Louis E. Rosier Probabilistic Algorithms and
Straight-Line Programs for Some Rank
Decision Problems . . . . . . . . . . . 227--232
J.-J. Pansiot A note on Post's correspondence problem 233--233
Bing Chao Huang An algorithm for inverting a permutation 237--238
Jozef Winkowski Protocols of Accessing Overlapping Sets
of Resources . . . . . . . . . . . . . . 239--243
Max Crochemore An optimal algorithm for computing the
repetitions in a word . . . . . . . . . 244--250
M. Y. Vardi The decision problem for database
dependencies . . . . . . . . . . . . . . 251--254
Jürgen Ebert A sensitive transitive closure algorithm 255--258
Osamu Watanabe A fast algorithm for finding all
shortest paths . . . . . . . . . . . . . 1--3
Gilbert N. Lewis and
Nancy J. Boynton and
F. Warren Burton Expected Complexity of Fast Search with
Uniformly Distributed Data . . . . . . . 4--7
James A. Storer Constructing Full Spanning Trees for
Cubic Graphs . . . . . . . . . . . . . . 8--11
Oscar H. Ibarra and
Shlomo Moran Deterministic and probabilistic
algorithms for maximum bipartite
matching via fast matrix multiplication 12--15
James F. Korsh Greedy Binary Search Trees are Nearly
Optimal . . . . . . . . . . . . . . . . 16--19
A. K. Agrawala and
S. K. Tripathi On the optimality of semidynamic routing
schemes . . . . . . . . . . . . . . . . 20--22
K. Ramamohanarao and
R. Sacks-Davis Hardware Address Translation for
Machines with a Large Virtual Memory . . 23--29
G. Senizergues A new class of C.F.L. for which the
equivalence is decidable . . . . . . . . 30--34
Hamish I. E. Gunn and
David M. Harland Degrees of Constancy in Programming
Languages . . . . . . . . . . . . . . . 35--38
Yu. G. Stoyan and
S. V. Smelyakov An approach to the problems of routing
optimization in the regions of intricate
shape . . . . . . . . . . . . . . . . . 39--43
Mireille Clerbout and
Michel Latteux The inclusion of D0L in MULTI-RESET . . 45--47
O. M. Makarov Using duality for the synthesis of an
optimal algorithm involving matrix
multiplication . . . . . . . . . . . . . 48--49
R. Hood and
R. Melville Real-time queue operations in Pure LISP 50--54
Mikhail J. Atallah and
S. Rao Kosaraju An adversary-based lower bound for
sorting . . . . . . . . . . . . . . . . 55--57
Wojciech Rytter The dynamic simulation of recursive and
stack manipulating programs . . . . . . 58--63
Mireille Regnier On the Average Height of Trees in
Digital Search and Dynamic Hashing . . . 64--66
Ysmar V. Silva Filho Optimal Choice of Discriminators in a
Balanced $k$-$d$ Binary Search Tree . . 67--70
V. Ya. Pan The lower bounds on the additive
complexity of bilinear problems in terms
of some algebraic quantities . . . . . . 71--72
Ronald V. Book NTS grammars and Church--Rosser systems 73--76
J. S. Vitter A Shared-Memory Scheme for Coalesced
Hashing . . . . . . . . . . . . . . . . 77--79
Akira Nakamura Some Remarks on One-Pebble Rectangular
Array Acceptors . . . . . . . . . . . . 80--84
Shlomo Moran A note on: ``Shortest-path problem is
not harder than matrix multiplication''
[Inform. Process. Lett. \bf 11 (1980),
no. 3, 134--136; MR 81k:68036] by F.
Romani. With a reply by Romani . . . . . 85--86
Oscar H. Ibarra and
Louis E. Rosier On the Decidability of Equivalence for
Deterministic Pushdown Transducers . . . 89--93
Hideki Yamasaki On Weak Persistency of Petri Nets . . . 94--97
Tat Hung Chan Deciding Freeness for Program Schemes
with a Single Unary Function . . . . . . 98--102
R. H. Barlow and
D. J. Evans and
J. Shanehichi A parallel merging algorithm . . . . . . 103--106
Refael Hassin Maximum flow in $(s,\,t)$ planar
networks . . . . . . . . . . . . . . . . 107--107
A. Ehrenfeucht and
G. Rozenberg On the subword complexity of D0L
languages with a constant distribution 108--113
R. S. Bird The jogger's problem . . . . . . . . . . 114--117
M. D. Atkinson The cyclic Towers of Hanoi . . . . . . . 118--119
Donald MacDavid Tolle and
William E. Siddall On the Complexity of Vector Computations
in Binary Tree Machines . . . . . . . . 120--124
D. E. Denning and
H. Meijer and
F. B. Schneider More on master keys for group sharing 125--126
J. L. A. Van De Snepscheut Synchronous Communication Between
Asynchronous Components . . . . . . . . 127--130
Christos H. Papadimitriou and
Mihalis Yannakakis The clique problem for planar graphs . . 131--133
Gerhard Barth An Alternative for the Implementation of
the Knuth--Morris--Pratt Algorithm . . . 134--137
R. H. Davis and
C. Rinaldi and
C. J. Trebilcock Data Compression in Limited Capacity
Microcomputer Systems . . . . . . . . . 138--141
Wojciech Rytter Time complexity of languages recognized
by one-way multihead pushdown automata 142--144
Wojciech Rytter A hardest language recognized by two-way
nondeterministic pushdown automata . . . 145--146
V. K. Sabel\cprimefel\cprimed Tree equivalence of linear recursive
schemata is polynomial-time decidable 147--153
Alan A. Bertossi The edge Hamiltonian path problem is
NP-complete . . . . . . . . . . . . . . 157--159
L. Siklóssy Efficient query evaluation in relational
data bases with missing values . . . . . 160--163
M. Blum and
R. M. Karp and
O. Vornberger and
C. H. Papadimitriou and
M. Yannakakis The complexity of testing whether a
graph is a superconcentrator . . . . . . 164--167
Jacob T. Schwartz Finding the minimum distance between two
convex polygons . . . . . . . . . . . . 168--170
M. Ancona and
V. Gianuzzi A new method for implementing ${\rm
LR}(k)$ tables . . . . . . . . . . . . . 171--176
H. Edelsbrunner and
H. A. Maurer On the intersection of orthogonal
objects . . . . . . . . . . . . . . . . 177--181
Akira Nakamura and
Kunio Aizawa Acceptors for isometric parallel
context-free array languages . . . . . . 182--186
M. H. Williams A systematic test for extended operator
precedence . . . . . . . . . . . . . . . 187--190
Hiroto Yasuura Width and Depth of Combinational Logic
Circuits . . . . . . . . . . . . . . . . 191--194
R\=usi\lfhookn\vs Freivalds Projections of languages recognizable by
probabilistic and alternating finite
multitape automata . . . . . . . . . . . 195--198
R. K. Arora and
N. K. Sharma Guarded Procedure: a Distributed
Programming Concept . . . . . . . . . . 199--203
G. Guida and
M. Somalvico Multi-problem-solving: knowledge
representation and system architecture 204--214
J. M. Troya and
A. Vaquero An approximation algorithm for reducing
expected head movement in linear storage
devices . . . . . . . . . . . . . . . . 218--220
Alfred Schmitt On the computational power of the floor
function . . . . . . . . . . . . . . . . 1--3
Ben-Zion Chor Arithmetic of finite fields . . . . . . 4--6
Dhruva Nath and
S. N. Maheshwari Parallel Algorithms for the Connected
Components and Minimal Spanning Tree
Problems . . . . . . . . . . . . . . . . 7--11
Andries E. Brouwer and
Peter van Emde Boas A note on: ``Master keys for group
sharing'' [Inform. Process. Lett. \bf 12
(1981), no. 1, 23--25; MR 82d:94046] by
D. E. Denning and F. B. Schneider . . . 12--14
Ronald Backhouse Writing a number as the sum of two
squares: a new solution . . . . . . . . 15--17
E. Gelenbe and
D. Gardy On the size of projections . . . . . . . 18--21
Hamish I. E. Gunn Compile Time Type Checking of Structure
Field Accessing . . . . . . . . . . . . 22--25
R. Endre Tarjan A hierarchical clustering algorithm
using strong components . . . . . . . . 26--29
Robert Endre Tarjan Sensitivity analysis of minimum spanning
trees and shortest path trees . . . . . 30--33
Jan van Leeuwen and
Maurice Nivat Efficient recognition of rational
relations . . . . . . . . . . . . . . . 34--38
Ker-I Ko Some observations on the probabilistic
algorithms and NP-hard problems . . . . 39--43
Shmuel Zaks Generation and ranking of $K$-ary trees 44--48
L. Fariñas Del Cerro A simple deduction method for modal
logic . . . . . . . . . . . . . . . . . 49--51
A. O. Slisenko Context-free grammars as a tool for
describing polynomial-time subclasses of
hard problems . . . . . . . . . . . . . 52--56
M. H. Graham and
A. O. Mendelzon Strong equivalence of relational
expressions under dependencies . . . . . 57--62
J. C. Lagarias and
D. E. Swartwout Minimal storage representations for
binary relations . . . . . . . . . . . . 63--66
Guiseppina Gini The automatic synthesis of iterative
programs . . . . . . . . . . . . . . . . 67--73
H. Edelsbrunner and
H. A. Maurer and
D. G. Kirkpatrick Polygonal intersection searching . . . . 74--79
J. A. Bergstra and
J.-J. Ch. Meyer A simple transfer lemma for algebraic
specifications . . . . . . . . . . . . . 80--85
Eliezer Upfal Formal correctness proofs of a
nondeterministic program . . . . . . . . 86--92
Lud\vek Ku\vcera Parallel computation and conflicts in
memory access . . . . . . . . . . . . . 93--96
Takashi Yokomori and
Derick Wood and
Klaus-Jörn Lange A three-restricted normal form theorem
for ETOL languages . . . . . . . . . . . 97--100
Jorma Tarhio LR Parsing of Some Ambiguous Grammars 101--103
Dietmar Wätjen and
Werner Struckmann An algorithm for verifying equations of
morphisms in a category . . . . . . . . 104--108
K. N. King and
Barbara Smith-Thomas An optimal algorithm for sink-finding 109--111
J.-L. Lassez and
V. L. Nguyen and
E. A. Sonenberg Fixed point theorems and semantics: a
folk tale . . . . . . . . . . . . . . . 112--116
R. H. Barlow and
D. J. Evans and
J. Shanehchi Parallel multisection for the
determination of the eigenvalues of
symmetric quindiagonal matrices . . . . 117--118
Johannes Röhrich A hybrid of Quicksort with $O(n \log n)$
worst case complexity . . . . . . . . . 119--123
Herbert Edelsbrunner and
Mark H. Overmars On the equivalence of some rectangle
problems . . . . . . . . . . . . . . . . 124--127
Calvin C. Elgot and
Alan J. Perlis and
Lawrence Snyder A syntax-free semantics for the APL
operators . . . . . . . . . . . . . . . 128--131
Dzenan Ridjanovic and
Michael L. Brodie Defining Database Dynamics with
Attribute Grammars . . . . . . . . . . . 132--138
J. F. Korsh Growing nearly optimal binary search
trees . . . . . . . . . . . . . . . . . 139--143
Dario Bini Reply to the paper: ``The numerical
instability of Bini's algorithm''
[Inform. Process. Lett. \bf 12 (1981),
no. 1, 17--19; MR 82i:65029] by N. K.
Tsao . . . . . . . . . . . . . . . . . . 144--145
M. Jakobsson Evaluation of a hierarchical bit-vector
compression technique . . . . . . . . . 147--149
Jack A. Orenstein Multidimensional Tries Used for
Associative Searching . . . . . . . . . 150--157
Hiroshi Umeo and
Kenichi Morita and
Kazuhiro Sugata Deterministic One-Way Simulation of
Two-Way Real-Time Cellular Automata and
its Related Problems . . . . . . . . . . 158--161
G. Beretta Monte Carlo estimation of numerical
stability in fast algorithms for systems
of bilinear forms . . . . . . . . . . . 162--167
Paul Franchi-Zannettacci An extension to trees of the Sardinas
and Patterson algorithm . . . . . . . . 168--173
R. Demolombe Generalized division for relational
algebraic language . . . . . . . . . . . 174--178
Ernst-E. E. Doberkat Asymptotic estimates for the higher
moments of the expected behavior of
straight insertion sort . . . . . . . . 179--182
Michael J. Fischer and
Nancy A. Lynch A lower bound for the time to assure
interactive consistency . . . . . . . . 183--186
Jiann H. Jou and
Patrick C. Fischer The complexity of recognizing $3{\rm
NF}$ relation schemes . . . . . . . . . 187--190
Jack Minker and
Guy Zanon An extension to linear resolution with
selection function . . . . . . . . . . . 191--194
Bengt Aspvall and
Michael F. Plass and
Robert Endre Tarjan Erratum: ``A linear-time algorithm for
testing the truth of certain quantified
Boolean formulas'' [Inform. Process.
Lett. \bf 8 (1979), no. 3, 121--123; MR
80b:68050] . . . . . . . . . . . . . . . 195--195
Clelia De Felice On the triangle conjecture . . . . . . . 197--200
F. Warren Burton A linear space translation of functional
programs to Turner combinators . . . . . 201--204
F. Warren Burton An efficient functional implementation
of FIFO queues . . . . . . . . . . . . . 205--206
Anton Nijholt A note on the sufficiency of
Soko\lowski's criterion for context-free
languages . . . . . . . . . . . . . . . 207--207
P. G. Reddy and
Subhash Bhalla and
B. E. Prasad A model of concurrency control in
distributed database systems . . . . . . 208--213
J. G. Shanthikumar A recursive algorithm to generate joint
probability distribution of arrivals
from exponential sources during a random
time interval . . . . . . . . . . . . . 214--217
Johnson M. Hart Permutation Inversions and
Multidimensional Cumulative Distribution
Functions . . . . . . . . . . . . . . . 218--222
David A. Carlson and
John E. Savage Extreme time-space tradeoffs for graphs
with small space requirements . . . . . 223--227
Reuven Bar-Yehuda and
Uzi Vishkin Complexity of finding $k$-path-free
dominating sets in graphs . . . . . . . 228--232
Carla Savage Depth-First Search and the Vertex Cover
Problem . . . . . . . . . . . . . . . . 233--235
Heinz Zemanek Obituary: Victor Mikha\uìlovich Glushkov
(1923--1982) . . . . . . . . . . . . . . 236--237
R. E. Krichevsky Letter to the editor: ``A family of
codes commutatively equivalent to prefix
codes'' [Inform. Process. Lett. \bf 12
(1981), no. 1, 1--4; MR 82j:94021] by S.
Mauceri and A. Restivo . . . . . . . . . 238--238
F. Luccio and
L. Pagli A linear algorithm to determine minimal
spanning forests in chain graphs . . . . 1--4
Wojciech Rytter A note on two-way nondeterministic
pushdown automata . . . . . . . . . . . 5--9
J.-C. Bermond and
C. Delorme and
J.-J. Quisquater Tables of large graphs with given degree
and diameter . . . . . . . . . . . . . . 10--13
Larry J. Stockmeyer and
Vijay V. Vazirani NP-completeness of some generalizations
of the maximum matching problem . . . . 14--19
C. Bron and
E. J. Dijkstra and
S. D. Swierstra A memory management unit for the optimal
exploitation of a small address space 20--22
C. H. C. Leung Optimal database reorganisation: some
practical difficulties . . . . . . . . . 23--27
Maciej M. Sys\lo A labeling algorithm to recognize a line
digraph and output its root graph . . . 28--30
Albert C. Greenberg and
Richard E. Ladner and
Michael S. Paterson and
Zvi Galil Efficient Parallel Algorithms for Linear
Recurrence Computation . . . . . . . . . 31--35
Peter M. Winkler On computability of the mean deviation 36--38
Karel Culik, II and
Derick Wood A note on some tree similarity measures 39--42
Leon S. Levy An improved list-searching algorithm . . 43--45
G. K. Manacher Steady-paced-output and
fractional-on-line algorithms on a RAM 47--52
C. M. Eastman and
M. Zemankova Partially Specified Nearest Neighbor
Searches Using $k$-$d$ Trees . . . . . . 53--56
Jean Pierre Jouannaud and
Pierre Lescanne On Multiset Orderings . . . . . . . . . 57--63
T. R. Walsh The Towers of Hanoi revisited: moving
the rings by counting the moves . . . . 64--67
Michael G. Main Permutations are not context-free: an
application of the Interchange Lemma . . 68--71
Allen Goldberg and
Paul Purdom and
Cynthia Brown Average Time Analyses of Simplified
Davis--Putnam Procedures . . . . . . . . 72--75
Leon \Lukaszewicz Universal Grammars . . . . . . . . . . . 76--80
Ingo Wegener Best possible asymptotic bounds on the
depth of monotone functions in
multivalued logic . . . . . . . . . . . 81--83
J. L. Balcazar and
J. Diaz A note on a theorem by Ladner . . . . . 84--86
Amir Schoor Fast Algorithm for Sparse Matrix
Multiplication . . . . . . . . . . . . . 87--89
Michael Spyratos A homomorphism theorem for data base
mappings . . . . . . . . . . . . . . . . 91--96
Anton Nijholt On the relationship between the ${\rm
LL}(k)$ and ${\rm LR}(k)$ grammars . . . 97--101
Wojciech Rytter Time complexity of unambiguous path
systems . . . . . . . . . . . . . . . . 102--104
P. G. Reddy and
S. Bhalla and
B. E. Prasad Robust, centralized certifier based
concurrency control for distributed
databases . . . . . . . . . . . . . . . 105--110
Waldemar Korczy\'nski and
Józef Winkowski A communication concept for distributed
systems . . . . . . . . . . . . . . . . 111--114
To-Yat Cheung A statistical model for estimating the
number of records in a relational
database . . . . . . . . . . . . . . . . 115--118
Teofilo F. Gonzalez and
Donald B. Johnson Sorting numbers in linear expected time
and optimal extra space . . . . . . . . 119--124
Hiroshi Imai Finding connected components of an
intersection graph of squares in the
Euclidean plane . . . . . . . . . . . . 125--128
Edsger W. Dijkstra and
A. J. M. van Gasteren An Introduction to Three Algorithms for
Sorting in Situ . . . . . . . . . . . . 129--134
M. Becker and
W. Degenhardt and
J. Doenhardt and
S. Hertel and
G. Kaninke and
W. Keber and
K. Mehlhorn and
S. Näher and
H. Rohnert and
T. Winter A probabilistic algorithm for vertex
connectivity of graphs . . . . . . . . . 135--136
F. L. Morris Another compacting garbage collector . . 139--142
J. A. Bergstra and
J. V. Tucker Two Theorems About the Completeness of
Hoare's Logic . . . . . . . . . . . . . 143--149
Jan Ma\luszy\'nski and
Jörgen Fischer Nilsson Grammatical Unification . . . . . . . . 150--158
A. W\lodzimierz Mostowski Determinancy of sinking automata on
infinite trees and inequalities between
various Rabin's pair indices . . . . . . 159--163
Katsushi Inoue and
Itsuo Takanami and
Hiroshi Taniguchi A note on alternating on-line Turing
machines . . . . . . . . . . . . . . . . 164--168
Mamoru Hoshi and
Toshitsugu Yuba A counter example to a monotonicity
property of $k$-$d$ trees . . . . . . . 169--173
S. Ceri and
G. Pelagatti A solution method for the non-additive
resource allocation problem in
distributed system design . . . . . . . 174--178
L. Goh and
D. Rotem Recognition of Perfect Elimination
Bipartite Graphs . . . . . . . . . . . . 179--182
Micha Sharir Fast Composition of Sparse Maps . . . . 183--185
Peter J. Slater A linear algorithm for the number of
degree constrained subforests of a tree 186--188
Timo Leipälä On Optimal Multilevel Indexed Sequential
Files . . . . . . . . . . . . . . . . . 191--195
P. T. Highnam The ears of a polygon . . . . . . . . . 196--198
Andrzej Szepietowski A finite $5$-pebble-automaton can search
every maze . . . . . . . . . . . . . . . 199--204
Lutz M. Wegner Sorting a linked list with equal keys 205--208
George S. Lueker and
Dan E. Willard A data structure for dynamic range
queries . . . . . . . . . . . . . . . . 209--213
Tatsuya Motoki A note on upper bounds for the selection
problem . . . . . . . . . . . . . . . . 214--219
Harry R. Lewis and
Richard Statman Unifiability is complete for
co-NLogSpace . . . . . . . . . . . . . . 220--222
Patrick Shen-pei Wang A new hierarchy of two-dimensional array
languages . . . . . . . . . . . . . . . 223--226
Markku Tamminen Extendible Hashing with Overflow . . . . 227--232
Quentin F. Stout Drawing Straight Lines with a Pyramid
Cellular Automaton . . . . . . . . . . . 233--237
Arthur M. Farley and
Andrzej Proskurowski Directed Maximal-Cut Problems . . . . . 238--241
Friedhelm Meyer Auf Der Heide Infinite Cube-Connected Cycles . . . . . 1--2
Alan A. Bertossi and
Maurizio A. Bonuccelli Preemptive Scheduling of Periodic Jobs
in Uniform Multiprocessor Systems . . . 3--6
A. Ehrenfeucht and
G. Rozenberg On the Subword Complexity of Locally
Catenative DOL Languages . . . . . . . . 7--9
Vitit Kantabutra Traveling salesman cycles are not always
subgraphs of Vorono\uì duals . . . . . . 11--12
Ronald Fagin and
Moshe Y. Vardi Armstrong Databases for Functional and
Inclusion Dependencies . . . . . . . . . 13--19
A. Perko A representation of disjoint sets with
fast initialization . . . . . . . . . . 21--21
Kenneth L. Clarkson A modification of the greedy algorithm
for vertex cover . . . . . . . . . . . . 23--25
Michel Latteux On a language without star . . . . . . . 27--30
Yves Métivier About the rewriting systems produced by
the Knuth Bendix completion algorithm 31--34
Ralf Hartmut Güting Stabbing $C$-Oriented Polygons . . . . . 35--40
Ingo Wegener Relating monotone formula size and
monotone depth of Boolean functions . . 41--42
Lewis Neale Lester Accuracy of Approximating Queueing
Network Departure Processes with
Independent Renewal Processes . . . . . 43--48
Joanna J\polhkedrzejowicz On the enlargement of the class of
regular languages by the shuffle closure 51--54
Juris Hartmanis On sparse sets in ${\rm NP}-{\rm P}$ . . 55--60
Lloyd Allison Stable Marriages by Coroutines . . . . . 61--65
Christopher W. Fraser A generalization of two code ordering
optimizations . . . . . . . . . . . . . 67--70
S. Eichholz Optimal networks for distributing
nonsequential programs . . . . . . . . . 71--74
Bernard Chazelle A decision procedure for optimal
polyhedron partitioning . . . . . . . . 75--78
B. Alpern and
F. B. Schneider Key exchange using keyless cryptography 79--81
Micha Hofri Should the Two-Headed Disk Be Greedy?
--- Yes, It Should . . . . . . . . . . . 83--85
Dan Gusfield Connectivity and edge-disjoint spanning
trees . . . . . . . . . . . . . . . . . 87--89
T. R. Walsh Iteration strikes back---at the cyclic
Towers of Hanoi . . . . . . . . . . . . 91--93
T. Ibaraki and
N. Katoh On-line computation of transitive
closures of graphs . . . . . . . . . . . 95--97
Christopher R. Wood and
Eduardo B. Fernandez and
Tomas Lang Minimization of Demand Paging for the
LRU Stack Model of Program Behavior . . 99--104
Robert L. Constable Programs as proofs: a synopsis . . . . . 105--112
Robert J. McGlinn Is SSS$^*$ better than alpha-beta . . . 113--120
Eljas Soisalon-Soininen On computing approximate convex hulls 121--126
Wojciech Rytter Time Complexity of Loop-Free Two-Way
Pushdown Automata . . . . . . . . . . . 127--129
Markku Tamminen Analysis of $N$-trees . . . . . . . . . 131--137
Toshitsugu Yuba and
Yoshinori Yamaguchi and
Toshio Shimada A control mechanism of a Lisp-based
data-driven machine . . . . . . . . . . 139--143
Rakesh Agrawal and
David J. Dewitt Updating Hypothetical Data Bases . . . . 145--146
I. K. Rystsov Polynomial complete problems in automata
theory . . . . . . . . . . . . . . . . . 147--151
Marco A. Casanova The theory of functional and subset
dependencies over relational expressions 153--160
J. L. Deléage An application of a transfer lemma . . . 161--163
Stefan Hertel Smoothsort's Behavior on Presorted
Sequences . . . . . . . . . . . . . . . 165--170
Greg N. Frederickson Scheduling Unit-Time Tasks with Integer
Release Times and Deadlines . . . . . . 171--173
Errol L. Lloyd On a Simple Deadlock Recovery Problem 175--178
Max Crochemore and
Michel Le Rest and
Philippe Wender An optimal test on finite unavoidable
sets of words . . . . . . . . . . . . . 179--180
Chee K. Yap A hybrid algorithm for the shortest path
between two nodes in the presence of few
negative arcs . . . . . . . . . . . . . 181--182
Takao Tsuda and
Takashi Sato and
Takaaki Tatsumi Generalization of Floyd's model on
permuting information in idealized
two-level storage . . . . . . . . . . . 183--188
Masanori Fushimi Increasing the orders of
equidistribution of the leading bits of
the Tausworthe sequence . . . . . . . . 189--192
Bernard Chazelle An improved algorithm for the
fixed-radius neighbor problem . . . . . 193--198
Wojciech Rytter A simulation result for two-way pushdown
automata . . . . . . . . . . . . . . . . 199--202
A. Bossi and
N. Cocco and
L. Colussi A divide-and-conquer approach to general
context-free parsing . . . . . . . . . . 203--208
Uwe Schöning On the structure of $\Delta^p_2$ . . . . 209--211
Allen Goldberg and
Paul Purdom and
Cynthia Brown Corrigendum: ``Average time analyses of
simplified Davis--Putnam procedures''
[Inform. Process. Lett. \bf 15 (1982),
no. 2, 72--75] . . . . . . . . . . . . . 213--213
Edsger W. Dijkstra and
W. H. J. Feijen and
A. J. M. van Gasteren Derivation of a Termination Detection
Algorithm for Distributed Computations 217--219
Andrzej Duda The effects of checkpointing on program
execution time . . . . . . . . . . . . . 221--229
Arturo Carpi On the size of a square-free morphism on
a three letter alphabet . . . . . . . . 231--235
F. Murtagh Expected-time complexity results for
hierarchic clustering algorithms which
use cluster centres . . . . . . . . . . 237--241
K. Ozawa Considerations on the similarity
measures between index terms . . . . . . 243--246
Jacques Cohen A note on a fast algorithm for sparse
matrix multiplication . . . . . . . . . 247--248
John Zahorjan and
Barbara J. Bell and
Kenneth C. Sevcik Estimating Block Transfers When Record
Access Probabilities are Non-Uniform . . 249--252
Robert Endre Tarjan Updating a Balanced Search Tree in
$O(1)$ Rotations . . . . . . . . . . . . 253--257
H. P. Kriegel and
Y. S. Kwong Insertion-Safeness in Balanced Trees . . 259--264
Rudolf Freund Init and Anf operating on
$\omega$-languages . . . . . . . . . . . 265--269
M. C. Er Computing Sums of Order-$k$ Fibonacci
Numbers in Log Time . . . . . . . . . . 1--5
Michael Willett Trapdoor Knapsacks without
Superincreasing Structure . . . . . . . 7--11
F. Cesarini and
G. Soda An algorithm to construct a compact
$B$-tree in case of ordered keys . . . . 13--16
Ronald C. Richards Shape Distribution of Height-Balanced
Trees . . . . . . . . . . . . . . . . . 17--20
Henry R. Tirri Simulation, Reduction and Preservation
of Correctness Properties of Parallel
Systems . . . . . . . . . . . . . . . . 21--27
Manfred Broy Denotational Semantics of Communicating
Processes Based on a Language for
Applicative Multiprogramming . . . . . . 29--35
Robert E. Tarjan An improved algorithm for hierarchical
clustering using strong components . . . 37--41
S. P. Rana A distributed solution of the
distributed termination problem . . . . 43--46
M. H. Williams Is an Exit Statement Sufficient? . . . . 47--51
Cornelius Croitoru and
Emilian Suditu Perfect Stables in Graphs . . . . . . . 53--56
Jerzy R. Nawrocki Contiguous Segmentation with Limited
Compacting . . . . . . . . . . . . . . . 57--62
Michael J. Magazine Optimality of Intuitive Checkpointing
Policies . . . . . . . . . . . . . . . . 63--66
Man-Tak Shing Optimum Ordered Bi-Weighted Binary Trees 67--70
Jozef Vysko\vc A note on the power of integer division 71--72
Po Tong and
E. L. Lawler A faster algorithm for finding
edge-disjoint branchings . . . . . . . . 73--76
Adi Shamir Embedding Cryptographic Trapdoors in
Arbitrary Knapsack Systems . . . . . . . 77--79
Dan E. Willard Log-Logarithmic Worst-Case Range Queries
are Possible in Space $\Theta (N)$ . . . 81--84
Youichi Kobuchi Stability of desynchronized 0L systems 85--90
Paul De Bra and
Jan Paredaens An Algorithm for Horizontal
Decompositions . . . . . . . . . . . . . 91--95
Alan A. Bertossi Finding Hamiltonian Circuits in Proper
Interval Graphs . . . . . . . . . . . . 97--101
Amir Schorr Physical Parallel Devices are not Much
Faster Than Sequential Ones . . . . . . 103--106
Lud\vek Ku\vcera Erratum and addendum to: ``Parallel
computation and conflicts in memory
access'' [Inform. Process. Lett. \bf 14
(1982), no. 2, 93--96; MR 83g:68038] . . 107--107
J. J. Martin Precise typing and filters . . . . . . . 109--112
Luis Fariñas Space as time . . . . . . . . . . . . . 113--115
Vladimir Lifschitz and
Leon Pesotchinsky A note on the complexity of a partition
algorithm . . . . . . . . . . . . . . . 117--120
A. Ehrenfeucht and
G. Rozenberg On the Subword Complexity of $m$-Free
D0L Languages . . . . . . . . . . . . . 121--124
Sven Skyum A measure in which Boolean negation is
exponentially powerful . . . . . . . . . 125--128
Mark Weiser Reconstructing Sequential Behavior from
Parallel Behavior Projections . . . . . 129--135
Takashi Yokomori and
Aravind K. Joshi Semi-Linearity, Parikh-Boundedness and
Tree Adjunct Languages . . . . . . . . . 137--143
Gadiel Seroussi and
Fai Ma On the Arithmetic Complexity of Matrix
Kronecker Powers . . . . . . . . . . . . 145--148
C. Choffrut and
K. Culik, II Folding of the Plane and the Design of
Systolic Arrays . . . . . . . . . . . . 149--153
Ali Mili Verifying Programs by Induction on Their
Data Structure: General Format and
Applications . . . . . . . . . . . . . . 155--160
Piotr Wyrostek On the ``correct prefix property'' in
precedence parsers . . . . . . . . . . . 161--165
Zhi Jie Zheng The duodirun merging algorithm: a new
fast algorithm for parallel merging . . 167--168
M. H. Williams The problem of absolute privacy . . . . 169--171
W. F. Clocksin Real-Time Functional Queue Operations
Using the Logical Variable . . . . . . . 173--175
John J. Bartholdi, III and
Loren K. Platzman A fast heuristic based on space filling
curves for minimum-weight matching in
the plane . . . . . . . . . . . . . . . 177--180
Erkki Mäkinen Boundedness Testing for Unambiguous
Context-Free Grammars . . . . . . . . . 181--183
Oded Shmueli Dynamic Cycle Detection . . . . . . . . 185--188
S. Ramesh and
S. L. Mehndiratta The liveness property of on-the-fly
garbage collector---a proof . . . . . . 189--195
Anil R. Gangolli and
Steven L. Tanimoto Two Pyramid Machine Algorithms for Edge
Detection in Noisy Binary Images . . . . 197--202
Norbert Blum A note on the ``parallel computation
thesis'' . . . . . . . . . . . . . . . . 203--205
Mikhail J. Atallah A linear time algorithm for the
Hausdorff distance between convex
polygons . . . . . . . . . . . . . . . . 207--209
Brian H. Mayoh Models of Programs and Processes . . . . 211--214
Clemens Lautemann BPP and the polynomial hierarchy . . . . 215--217
Leo J. Guibas and
Jorge Stolfi On computing all north-east nearest
neighbors in the $L_1$ metric . . . . . 219--223
Teruo Hikita Listing and Counting Subtrees of Equal
Size of a Binary Tree . . . . . . . . . 225--229
J. S. Rohl A faster lexicographical $N$ queens
algorithm . . . . . . . . . . . . . . . 231--233
Yao Tin Yu and
Mohamed G. Gouda Unboundedness Detection for a Class of
Communicating Finite-State Machines . . 235--240
Eugene W. Myers An applicative random-access stack . . . 241--248
Michael J. Fischer and
Michael S. Paterson Storage Requirements for Fair Scheduling 249--250
Seiichi Nishihara and
Katsuo Ikeda Address Calculation Algorithms for
Ordered Sets of Combinations . . . . . . 251--253
D. T. Barnard Recursive descent parsing using
implementation languages requiring
definition before use . . . . . . . . . 255--258
T. Ida Some FP algebra with Currying operation 259--261
Reiner Kolla Where-Oblivious is not Sufficient . . . 263--268
Yung H. Tsin and
Francis Y. Chin A general program scheme for finding
bridges . . . . . . . . . . . . . . . . 269--272
Hitohisa Asai A consideration of a practical
implementation for a new convergence
division . . . . . . . . . . . . . . . . 273--281
V. N. Kas\cprimeyanov Loop Cleaning . . . . . . . . . . . . . 1--6
Jan Magott Performance Evaluation of Concurrent
Systems Using Petri Nets . . . . . . . . 7--13
A. Saoudi Infinitary Tree Languages Recognized by
$\omega$-automata . . . . . . . . . . . 15--19
Hans-Jörg Kreowski and
Grzegorz Rozenberg Note on node-rewriting graph grammars 21--24
Neil C. Rowe Diophantine Inference on a Statistical
Database . . . . . . . . . . . . . . . . 25--31
Rodney W. Topor Termination Detection for Distributed
Computations . . . . . . . . . . . . . . 33--36
Mikhail J. Atallah Parallel Strong Orientation of an
Undirected Graph . . . . . . . . . . . . 37--39
Francis Chin and
Cao An Wang Minimum vertex distance between
separable convex polygons . . . . . . . 41--45
Xiao Long Jin Large Processors are Good in VLSI Chips 47--49
Eiji Yodogawa A note on array grammars . . . . . . . . 51--54
R. Geist Perception-based configuration design of
computer systems . . . . . . . . . . . . 55--57
M. E. Dyer and
A. M. Frieze A partitioning algorithm for minimum
weighted Euclidean matching . . . . . . 59--62
M. Elizabeth C. Hull A parallel view of stable marriages . . 63--66
Jan Schlörer Insecurity of Set Controls for
Statistical Databases . . . . . . . . . 67--71
Russell Turpin and
Brian A. Coan Extending Binary Byzantine Agreement to
Multivalued Byzantine Agreement . . . . 73--76
Leszek Holenderski A note on specifying and verifying
concurrent processes . . . . . . . . . . 77--85
Hirofumi Katsuno When Do Non-Conflict-Free Multivalued
Dependency Sets Appear? . . . . . . . . 87--92
Heung-Soon S. Ihm and
Simeon C. Ntafos On Legal Path Problems in Digraphs . . . 93--98
F. Scarioni and
H. G. Speranza A probabilistic analysis of an
error-correcting algorithm for the
Towers of Hanoi puzzle . . . . . . . . . 99--103
Satoru Miyano Remarks on Two-Way Automata with
Weak-Counters . . . . . . . . . . . . . 105--107
C. C. Lee and
D. T. Lee On a Circle-Cover Minimization Problem 109--115
Herbert S. Wilf Backtrack: an $O(1)$ expected time
algorithm for the graph coloring problem 119--121
Eitan Zemel An $O(n)$ algorithm for the linear
multiple choice Knapsack problem and
related problems . . . . . . . . . . . . 123--128
Peter Moller-Nielsen and
Jorgen Staunstrup Experiments with a Fast String Searching
Algorithm . . . . . . . . . . . . . . . 129--135
J. H. Remmers A technique for developing loop
invariants . . . . . . . . . . . . . . . 137--139
G. Alia and
F. Barsi and
E. Martinelli A fast VLSI conversion between binary
and residue systems . . . . . . . . . . 141--145
Stuart J. Berkowitz On Computing the Determinant in Small
Parallel Time Using a Small Number of
Processors . . . . . . . . . . . . . . . 147--150
György Turán The critical complexity of graph
properties . . . . . . . . . . . . . . . 151--153
A. Apostolico and
R. Giancarlo Pattern matching machine implementation
of a fast test for unique
decipherability . . . . . . . . . . . . 155--158
Gordon V. Cormack and
R. Nigel Horspool Algorithms for Adaptive Huffman Codes 159--165
Alfonso Miola Algebraic approach to $p$-adic
conversion of rational numbers . . . . . 167--171
Thomas Lickteig A note on border rank . . . . . . . . . 173--178
Gianna Cioni and
Antoni Kreczmar Programmed Deallocation without Dangling
Reference . . . . . . . . . . . . . . . 179--187
Alistair Moffat and
Tadao Takaoka A priority queue for the all pairs
shortest path problem . . . . . . . . . 189--193
D. C. S. Allison and
M. T. Noga The $L_1$ traveling salesman problem . . 195--199
Jürgen Tiekenheinrich A $4n$-lower bound on the monotone
network complexity of a one-output
Boolean function . . . . . . . . . . . . 201--202
Heikki Mannila and
Esko Ukkonen A simple linear-time algorithm for in
situ merging . . . . . . . . . . . . . . 203--208
Susumu Yamasaki and
Mikio Yoshida and
Shuji Doshita and
Mikito Hirata A new combination of input and unit
deductions for Horn sentences . . . . . 209--213
Eike Best Fairness and conspiracies . . . . . . . 215--220
Vladimir Lifschitz On verification of programs with GOTO
statements . . . . . . . . . . . . . . . 221--225
T. Ohya and
M. Iri and
K. Murota A fast Voronoi-diagram algorithm with
quaternary tree bucketing . . . . . . . 227--231
Paolo Atzeni and
Nicola M. Morfuni Functional Dependencies in Relations
with Null Values . . . . . . . . . . . . 233--238
B. Monien Deterministic Two-Way One-Head Pushdown
Automata are Very Powerful . . . . . . . 239--242
M. P. Flé and
G. Roucairol Multiserialization of Iterated
Transactions . . . . . . . . . . . . . . 243--247
Gerhard Barth An analytical comparison of two string
searching algorithms . . . . . . . . . . 249--256
Moshe Y. Vardi A note on lossless database
decompositions . . . . . . . . . . . . . 257--260
Nathan Goodman and
Y. C. Tay A characterization of multivalued
dependencies equivalent to a join
dependency . . . . . . . . . . . . . . . 261--266
J. Blazewicz and
J. Weglarz and
M. Drabowski Scheduling independent $2$-processor
tasks to minimize schedule length . . . 267--273
M. B. Trakhtenbrot Some Equivalent Transformations of
Recursive Programs Based on Their
Schematic Properties . . . . . . . . . . 275--283
Bruno Courcelle Some negative results concerning DPDAs 285--289
Shinsei Tazawa On the consecutive retrieval property
for generalized binary queries . . . . . 291--293
D. K. Friesen and
M. A. Langston A storage-size selection problem . . . . 295--296
Stanislav \vZák Letter to the editor: ``Finitary and
infinitary interpretations of
languages'' [Math. Systems Theory \bf 15
(1981/82), no. 3, 251--265; MR
83h:68119] by H. A. Maurer, A. Salomaa
and D. Wood . . . . . . . . . . . . . . 297--298
Hari Madduri and
Raphael Finkel Extension of the Banker's Algorithm for
Resource Allocation in a Distributed
Operating System . . . . . . . . . . . . 1--8
Michio Oyamaguchi Some Remarks on Subclass Containment
Problems for Several Classes of DPDA's 9--12
Nam Sung Woo and
Carl H. Smith and
Ashok Agrawala A proof of the determinacy property of
the data flow schema . . . . . . . . . . 13--16
J. R. Parker On Converting Character Strings to
Integers . . . . . . . . . . . . . . . . 17--19
Ulrich Bechtold and
Klaus Küspert On the Use of Extendible Hashing without
Hashing . . . . . . . . . . . . . . . . 21--26
Ulrich Faigle and
Rainer Schrader Minimizing Completion Time for a Class
of Scheduling Problems . . . . . . . . . 27--29
Walter J. Savitch and
Paul M. B. Vitányi On the Power of Real-Time Two-Way
Multihead Finite Automata with Jumps . . 31--35
Alan A. Bertossi Dominating sets for split and bipartite
graphs . . . . . . . . . . . . . . . . . 37--40
P. A. Subrahmanyam and
J.-H. You On Embedding Functions in Logic . . . . 41--46
Selim G. Akl An optimal algorithm for parallel
selection . . . . . . . . . . . . . . . 47--50
Udi Manber A probabilistic lower bound for checking
disjointness of sets . . . . . . . . . . 51--53
Paul Spirakis and
Chee K. Yap Strong NP-hardness of moving many discs 55--59
Helmut Alt and
Kurt Mehlhorn and
J. Ian Munro Partial Match Retrieval in Implicit Data
Structures . . . . . . . . . . . . . . . 61--65
Alain J. Martin and
Martin Rem A presentation of the Fibonacci
algorithm . . . . . . . . . . . . . . . 67--68
G. P. McKeown and
V. J. Rayward-Smith Communication Problems on MIMD Parallel
Computers . . . . . . . . . . . . . . . 69--73
Prashant Palvia and
Salvatore T. March Approximating Block Accesses in Database
Organizations . . . . . . . . . . . . . 75--79
E. Luque and
A. Ripoll Integer Linear Programming for
Microprograms Register Allocation . . . 81--85
Ewa Klupsz A linear algorithm of a deadlock
avoidance for nonpreemptible resources 87--94
Grazia Lotti Area-time tradeoff for rectangular
matrix multiplication in VLSI models . . 95--98
Witold Lipski, Jr. An $O(n \log n)$ Manhattan path
algorithm . . . . . . . . . . . . . . . 99--102
E. J. Weyuker The complexity of data flow criteria for
test data selection . . . . . . . . . . 103--109
Piotr Wyrostek Erratum: ``On the `correct prefix
property' in precedence parsers''
[Inform. Process. Lett. \bf 17 (1983),
no. 3, 161--165, MR 85a:68112] . . . . . 111--111
A. Shamir and
C. P. Schnorr Cryptanalysis of Certain Variants of
Rabin's Signature Scheme . . . . . . . . 113--115
Joseph M. Treat and
Timothy A. Budd Extensions to Grid Selector Composition
and Compilation in APL . . . . . . . . . 117--123
David Avis Non-Partitionable Point Sets . . . . . . 125--129
Peter Eades and
Brendan McKay An algorithm for generating subsets of
fixed size with a strong minimal change
property . . . . . . . . . . . . . . . . 131--133
Dale Johnson and
Barrett R. Bryant Formal Syntax Methods for Natural
Language . . . . . . . . . . . . . . . . 135--143
Tomasz Kowaltowski and
Antonio Palma Another Solution of the Mutual Exclusion
Problem . . . . . . . . . . . . . . . . 145--146
R. G. Gupta and
V. S. P. Srivastava On Synthesis of Scheduling Algorithms 147--150
Joachim Biskup Some Variants of the Take-Grant
Protection Model . . . . . . . . . . . . 151--156
D. Maio and
M. R. Scalas and
P. Tiberio On Estimating Access Costs in Relational
Databases . . . . . . . . . . . . . . . 157--161
Eike Best Erratum: ``Fairness and conspiracies''
[Inform. Process. Lett. \bf 18 (1984),
no. 4, 215--220; MR 85h:68053] . . . . . 162--162
Wojciech Rytter On Linear Context-Free Languages and
One-Way Multihead Automata . . . . . . . 163--166
M. Chrobak and
B. S. Chlebus Probabilistic Turing Machines and
Recursively Enumerable Dedekind Cuts . . 167--171
Ph. Darondeau and
L. Kott Towards a Formal Proof System for
$\omega$-Rational Expressions . . . . . 173--177
Marek Chrobak A note on bounded-reversal multipushdown
machines . . . . . . . . . . . . . . . . 179--180
Dick Grune How to produce all sentences from a
two-level grammar . . . . . . . . . . . 181--185
Arturo Carpi On the Centers of the Set of Weakly
Square-Free Words on a Two Letter
Alphabet . . . . . . . . . . . . . . . . 187--190
J. Kral On software equations . . . . . . . . . 191--196
Michael Kallay The complexity of incremental convex
hull algorithms in ${\bf R}^d$ . . . . . 197--197
Clement H. C. Leung Approximate storage utilisation of
$B$-trees: a simple derivation and
generalisations . . . . . . . . . . . . 199--201
T. R. Walsh How Evenly Should One Divide to Conquer
Quickly? . . . . . . . . . . . . . . . . 203--208
Lawrence W. Dowdy and
Derek L. Eager and
Karen D. Gordon and
Lawrence V. Saxton Throughput Concavity and Response Time
Convexity . . . . . . . . . . . . . . . 209--212
Juhani Karhumäki and
Derick Wood Inverse Morphic Equivalence on Languages 213--218
Greg N. Frederickson On Linear-Time Algorithms for
Five-Coloring Planar Graphs . . . . . . 219--224
Erkki Mäkinen On Derivation Preservation . . . . . . . 225--228
Derick Wood The contour problem for rectilinear
polygons . . . . . . . . . . . . . . . . 229--236
Paul Bourret How to Estimate the Sizes of Domains . . 237--243
George Tourlakis An inductive number-theoretic
characterization of NP . . . . . . . . . 245--247
Jozef Vysko\vc A note on Boolean matrix multiplication 249--251
Pierre McKenzie Permutations of Bounded Degree Generate
Groups of Polynomial Diameter . . . . . 253--254
Goker Gursel and
Peter Scheuermann Asserting the optimality of serial SJRPs
in processing simple queries in chain
networks . . . . . . . . . . . . . . . . 255--260
Christine Duboc Some Properties of Commutation in Free
Partially Commutative Monoids . . . . . 1--4
Ronald V. Book and
Friedrich Otto Cancellation Rules and Extended Word
Problems . . . . . . . . . . . . . . . . 5--11
A. Mirzaian and
E. Arjomandi Selection in $x + y$ and Matrices with
Sorted Rows and Columns . . . . . . . . 13--17
Erkki Mäkinen A note on undercover relation . . . . . 19--21
G. P. McKeown A special purpose MIMD parallel
processor . . . . . . . . . . . . . . . 23--27
S. Upendra Rao and
A. K. Majumdar An algorithm for local compaction of
horizontal microprograms . . . . . . . . 29--33
Solomon Passy and
Tinko Tinchev PDL with data constants . . . . . . . . 35--41
Silvio Lemos Meira A linear applicative solution for the
set union problem . . . . . . . . . . . 43--45
Adam C. Bounas Direct determination of a ``seed''
binary matrix . . . . . . . . . . . . . 47--50
Sushil Jajodia On Equivalence of Relational and Network
Database Models . . . . . . . . . . . . 51--54
G. Bilardi and
F. P. Preparata The VLSI optimality of the AKS sorting
network . . . . . . . . . . . . . . . . 55--59
David A. Plaisted The undecidability of self-embedding for
term rewriting systems . . . . . . . . . 61--64
Jan L. A. Van de Snepscheut Evaluating Expressions with a Queue . . 65--66
John McLean A comment on the `basic security
theorem' of Bell and LaPadula . . . . . 67--70
Kohei Noshita Translation of Turner combinators in
${O(n \log n)}$ space . . . . . . . . . 71--74
P. Widmayer and
C. K. Wong An optimal algorithm for the maximum
alignment of terminals . . . . . . . . . 75--82
Satish R. Thatte On the Correspondence Between Two
Classes of Reduction Systems . . . . . . 83--85
David Harel and
David Peleg More on Looping Vs. Repeating in Dynamic
Logic . . . . . . . . . . . . . . . . . 87--90
A. J. Auzins and
E. B. Kinber On Separation of the Emptiness and
Equivalence Problems for Program Schemes 91--93
D. Beauquier and
D. Perrin Codeterministic Automata on Infinite
Words . . . . . . . . . . . . . . . . . 95--98
Esko Ukkonen Upper bounds on the size of ${\rm
LR}(k)$ parsers . . . . . . . . . . . . 99--103
Michael G. Main An infinite square-free co-CFL . . . . . 105--107
Subhash C. Kak How to Detect Tampering of Data . . . . 109--110
Ernest C. Njau Details of Distortions in the Computed
Fourier Transforms of Signals. Part I.
Short Periodic Signals . . . . . . . . . 111--113
Eduardo D. Sontag Real Addition and the Polynomial
Hierarchy . . . . . . . . . . . . . . . 115--120
Mee Yee Chan A note on redundant Disk Modulo
allocation . . . . . . . . . . . . . . . 121--123
Alain J. Martin The probe: an addition to communication
primitives . . . . . . . . . . . . . . . 125--130
E. Lodi and
F. Luccio Split Sequence Hash Search . . . . . . . 131--136
Richard Cole and
Chee K. Yap A parallel median algorithm . . . . . . 137--139
Erkki Mäkinen An undecidable problem for context-free
grammars . . . . . . . . . . . . . . . . 141--142
Yung Hyang Tsin An optimal parallel processor bound in
strong orientation of an undirected
graph . . . . . . . . . . . . . . . . . 143--146
Baruch Awerbuch A new distributed depth-first-search
algorithm . . . . . . . . . . . . . . . 147--150
Jeffrey Shallit and
Adi Shamir Number-Theoretic Functions Which are
Equivalent to Number of Divisors . . . . 151--153
Hugo Volger Some Results on Addition/Subtraction
Chains . . . . . . . . . . . . . . . . . 155--160
W. M. Beynon and
C. S. Iliopoulos Computing a Basis for a Finite Abelian
$p$-Group . . . . . . . . . . . . . . . 161--163
Emo Welzl Constructing the Visibility Graph for
$n$-Line Segments in ${O}(n^2)$ Time . . 167--171
Mathai Joseph On a Problem in Real-Time Computing . . 173--177
Nicola Santoro and
Jeffrey B. Sidney Interpolation-Binary Search . . . . . . 179--181
K. Rangarajan and
S. Arun-Kumar Fair Derivations in E0L Systems . . . . 183--188
Carroll Morgan Global and Logical Time in Distributed
Algorithms . . . . . . . . . . . . . . . 189--194
David S. Wise Representing Matrices as Quadtrees for
Parallel Processors . . . . . . . . . . 195--199
J. Mark Keil Finding Hamiltonian Circuits in Interval
Graphs . . . . . . . . . . . . . . . . . 201--206
W. J. Van Gils How to Cope with Faulty Processors in a
Completely Connected Network of
Communicating Processors . . . . . . . . 207--213
Costas S. Iliopoulos Analysis of Algorithms on Problems in
General Abelian Groups . . . . . . . . . 215--220
Amiram Yehudai A note on chains of deterministic
pushdown transducers . . . . . . . . . . 221--222
Maciej Slusarek A note on the dynamic storage allocation
problem . . . . . . . . . . . . . . . . 223--227
John H. Reif Depth-First Search is Inherently
Sequential . . . . . . . . . . . . . . . 229--234
Uzi Vishkin On Efficient Parallel Strong Orientation 235--240
Juris Hartmanis Independence Results About Context-Free
Languages and Lower Bounds . . . . . . . 241--248
James R. Bitner Storing Matrices on Disk for Efficient
Row and Column Retrieval . . . . . . . . 249--254
Luc Devroye A note on the expected time required to
construct the outer layer . . . . . . . 255--257
Christos H. Papadimitriou An algorithm for shortest-path motion in
three dimensions . . . . . . . . . . . . 259--263
Hanan Samet Bidirectional Coroutines . . . . . . . . 1--6
Juraj Hromkovi\vc Alternating Multicounter Machines with
Constant Number of Reversals . . . . . . 7--9
M. Negri and
G. Pelagatti Join During Merge: an Improved Sort
Based Algorithm . . . . . . . . . . . . 11--16
Gerald Guralnik and
Charles Zemach and
Tony Warnock An algorithm for uniform random sampling
of points in and on a hypersphere . . . 17--21
Linda Pagli Self-Adjusting Hash Tables . . . . . . . 23--25
Deepak Kapur and
Mukkai S. Krishnamoorthy Worst-Case Choice for the Stable
Marriage Problem . . . . . . . . . . . . 27--30
Se Man Oh and
J. C. H. Park A note on removing loops from
table-driven code generators . . . . . . 31--34
Mordechai M. Yung A secure and useful `keyless
cryptosystem' . . . . . . . . . . . . . 35--38
H. Edelsbrunner and
H. A. Maurer Finding Extreme Points in Three
Dimensions and Solving the Post-Office
Problem in the Plane . . . . . . . . . . 39--47
Ingo Wegener Optimal search with positive switch cost
is NP-hard . . . . . . . . . . . . . . . 49--52
Takashi Yokomori and
Derick Wood and
Klaus-Jörn Lange Erratum: ``A three-restricted normal
form theorem for ETOL languages''
[Inform. Process. Lett. \bf 14 (1982),
no. 3, 97--100; MR 83g:68115] . . . . . 53--53
Vladimir J. Lumelsky On Fast Computation of Distance Between
Line Segments . . . . . . . . . . . . . 55--61
Thomas Rauchle and
Sam Toueg Exposure to Deadlock for Communicating
Processes is Hard to Detect . . . . . . 63--68
Anne Kaldewaij On the Decomposition of Sequences into
Ascending Subsequences . . . . . . . . . 69--69
Juraj Hromkovi\vc Linear Lower Bounds on Unbounded Fan-In
Boolean Circuits . . . . . . . . . . . . 71--74
Ladislav Janiga and
Václav Koubek A note on finding minimum cuts in
directed planar networks by parallel
computations . . . . . . . . . . . . . . 75--78
Dario Bini and
Victor Ya. Pan Fast Parallel Polynomial Division via
Reduction to Triangular Toeplitz Matrix
Inversion and to Polynomial Inversion
Modulo a Power . . . . . . . . . . . . . 79--81
Dietmar Wätjen Feedback Automata and Their Languages 83--86
Paul M. B. Vitányi Square Time is Optimal for Simulation of
One Pushdown Store or One Queue by an
Oblivious One-Head Tape Unit . . . . . . 87--91
Van Nguyen The incompleteness of Misra and Chandy's
proof systems . . . . . . . . . . . . . 93--96
Alain J. Martin and
Jerry R. Burch Fair mutual exclusion with unfair $P$
and $V$ operations . . . . . . . . . . . 97--100
Clemens Lautemann and
Friedhelm Meyer auf der Heide Lower Time Bounds for Integer
Programming with Two Variables . . . . . 101--105
Alain J. Martin Erratum: ``The probe: an addition to
communication primitives'' . . . . . . . 107--107
Clark D. Thompson VLSI Design with Multiple Active Layers 109--111
Suresh C. Kothari and
K. V. S. Ramarao General Algorithms for the Address
Calculation of Lexicographically Ordered
Tuples . . . . . . . . . . . . . . . . . 113--116
D. T. Lee and
Y. T. Ching The power of geometric duality revisited 117--122
Joseph JáJá and
Jean Takche Improved Lower Bounds for Some Matrix
Multiplication Problems . . . . . . . . 123--127
Ted Herman and
K. Mani Chandy On Distributed Search . . . . . . . . . 129--133
M. Jantzen A note on a special one-rule semi-Thue
system . . . . . . . . . . . . . . . . . 135--140
Timothy A. Budd Creation and Reflexive Rights in
Grammatical Protection Systems . . . . . 141--145
Paul M. B. Vitányi An $n^{1.618}$ lower bound on the time
to simulate one queue or two pushdown
stores by one tape . . . . . . . . . . . 147--152
Chae Woo Yoo An approach to the transportation of
computer software . . . . . . . . . . . 153--157
B. Codenotti and
F. Romani and
G. Lotti VLSI Implementation of Fast Solvers for
Band Linear Systems with Constant
Coefficient Matrix . . . . . . . . . . . 159--163
Ralf Hartmut Güting Fast Dynamic Intersection Searching in a
Set of Isothetic Line Segments . . . . . 165--171
Jean-Paul Laumond Enumeration of Articulation Pairs of a
Planar Graph . . . . . . . . . . . . . . 173--179
Bowen Alpern and
Fred B. Schneider Defining Liveness . . . . . . . . . . . 181--185
M. D. Atkinson On Zigzag Permutations and Comparisons
of Adjacent Elements . . . . . . . . . . 187--189
Yves Robert and
Maurice Tchuente A systolic array for the longest common
subsequence problem . . . . . . . . . . 191--198
J. L. Keedy and
B. Freisleben On the Efficient Use of Semaphore
Primitives . . . . . . . . . . . . . . . 199--205
Ching C. Hsiao and
Nien-Tsu Shen $k$-Fold Bitonic Sort on a
Mesh-Connected Parallel Computer . . . . 207--212
A. Marchetti-Spaccamela and
G. Romano On Different Approximation Criteria for
Subset Product Problems . . . . . . . . 213--218
Bertrand Meyer Incremental String Matching . . . . . . 219--227
Jan Magott Performance Evaluation of Systems of
Cyclic Sequential Processes with Mutual
Exclusion Using Petri Nets . . . . . . . 229--232
A. J. Kfoury The unwind property for programs with
bounded memory . . . . . . . . . . . . . 233--238
W\lodzimierz Dobosiewicz A note on natural selection . . . . . . 239--243
Pavol \vDuri\vs and
Ondrej Sýkora and
Imrich V\vr\softto and
Clark D. Thompson Tight Chip Area Lower Bounds for
Discrete Fourier and Walsh-Hadamard
Transformations . . . . . . . . . . . . 245--247
Kenneth J. Supowit Decomposing a Set of Points into Chains,
with Applications to Permutation and
Circle Graphs . . . . . . . . . . . . . 249--252
Ulrich Derigs An Efficient Dijkstra-Like Labeling
Method for Computing Shortest Odd/Even
Paths . . . . . . . . . . . . . . . . . 253--258
Ingrid J. M. Birkhoff A direct routing algorithm for the
bit-reversal permutation on a
shuffle-exchange network . . . . . . . . 259--268
Heikki Mannila and
Kurt Mehlhorn A fast algorithm for renaming a set of
clauses as a Horn set . . . . . . . . . 269--272
Philippe Chatelin On Transformations of Algorithms to
Multiply $2 \times 2$ Matrices . . . . . 1--5
Jean Berstel Every iterated morphism yields a co-CFL 7--9
Victor Ya. Pan The Trade-Off Between the Additive
Complexity and the Asynchronicity of
Linear and Bilinear Algorithms . . . . . 11--14
Bernd Baumgarten and
Peter Ochsenschläger On termination and phase changes in the
presence of unreliable communication . . 15--20
Kenneth L. Clarkson Linear Programming in ${O}(n \times
3^{d^2})$ time . . . . . . . . . . . . . 21--24
Andrzej Lingas The Greedy and Delauney triangulations
are not bad in the average case . . . . 25--31
Louis E. Rosier A Note on Presburger Arithmetic with
Array Segments, Permutation and Equality 33--35
Mirko K\vrivánek Hexagonal unit network---a tool for
proving the NP-completeness results of
geometric problems . . . . . . . . . . . 37--41
Christiaan T. M. Jacobs and
Peter Van Emde Boas Two Results on Tables . . . . . . . . . 43--48
V. Kriau\vciukas Tree-Like Parse and Polynomial
Subclasses of Search Problems . . . . . 49--54
Ivan Stojmenovi\'c and
Eljas Soisalon-Soininen A Note on Approximate Convex Hulls . . . 55--56
Amos Israeli and
Y. Shiloach An Improved Parallel Algorithm for
Maximal Matching . . . . . . . . . . . . 57--60
Ke-Chang Dai EDISON-80, a language for modular
programming of parallel processes . . . 61--72
M. D. Grigoriadis and
B. Kalantari A Lower Bound to the Complexity of
Euclidean and Rectilinear Matching
Algorithms . . . . . . . . . . . . . . . 73--76
Amos Israeli and
A. Itai A fast and simple randomized parallel
algorithm for maximal matching . . . . . 77--80
Charles U. Martel Lower bounds on parallel algorithms for
finding the first maximal independent
set . . . . . . . . . . . . . . . . . . 81--85
Marta Cialdea Some remarks on the possibility of
extending resolution proof procedures to
intuitionistic logic . . . . . . . . . . 87--90
Pavel Goral\vcík and
Václav Koubek Verifying nonrigidity . . . . . . . . . 91--95
Marc Snir Exact Balancing is not Always Good . . . 97--102
Max B. Webster and
Paul W. Baker A Class of Differential Equations for
Testing Variable Step-Size Integration 103--107
P. Srinivas Kumar and
M. Manohar On Probability of Forest of Quadtrees
Reducing to Quadtrees . . . . . . . . . 109--111
Klaus Ambos-Spies Inhomogeneities in the polynomial-time
degrees: the degrees of super sparse
sets . . . . . . . . . . . . . . . . . . 113--117
Franz Aurenhammer The one-dimensional weighted
Vorono\uìdiagram . . . . . . . . . . . . 119--123
Arturo Carpi and
Aldo De Luca Square-free words of partially
commutative free monoids . . . . . . . . 125--131
Yoshio Hattori Nonisomorphic graphs with the same
$T$-polynomial . . . . . . . . . . . . . 133--134
F. Gire Two decidability problems for infinite
words . . . . . . . . . . . . . . . . . 135--140
R. John Muir Hughes A Novel Representation of Lists and its
Application to the Function `Reverse' 141--144
Sylvianne R. Schwer On the rationality of Petri net
languages . . . . . . . . . . . . . . . 145--146
Lin Chen $O(1)$ space complexity deletion for AVL
trees . . . . . . . . . . . . . . . . . 147--149
E. J. Cockayne and
D. E. Hewgill Exact computation of Steiner Minimal
Trees in the plane . . . . . . . . . . . 151--156
Robert C. Shock Computing the minimum cover of
functional dependencies . . . . . . . . 157--159
Michael Kallay Convex hull made easy . . . . . . . . . 161--161
Brigitte Jaumard and
Michel Minoux An Efficient Algorithm for the
Transitive Closure and a Linear
Worst-Case Complexity Result for a Class
of Sparse Graphs . . . . . . . . . . . . 163--169
J. Mark Keil Total domination in interval graphs . . 171--174
Wolfgang Panny A note on the higher moments of the
expected behavior of straight insertion
sort . . . . . . . . . . . . . . . . . . 175--177
Mark C. Hamburg Two Tagless Variations on the
Deutsch--Schorr--Waite Algorithm . . . . 179--183
Michael C. Loui and
Teresa A. Matsushita and
Douglas B. West Election in a Complete Network with a
Sense of Direction . . . . . . . . . . . 185--187
Svante Carlsson \sc Splitmerge: a fast stable merging
algorithm . . . . . . . . . . . . . . . 189--192
B. Codenotti and
G. Lotti A note on the VLSI counter . . . . . . . 193--195
Hania Gajewska and
Robert E. Tarjan Deques with heap order . . . . . . . . . 197--200
Dana Richards Data compression and Gray-code sorting 201--205
Key-Sun S. Choi and
Gil Chang Kim A Controlled Quantification in Parsing
of Montague Grammar . . . . . . . . . . 207--216
P. T. Highnam Optimal Algorithms for Finding the
Symmetries of a Planar Point Set . . . . 219--222
Shaunak Pawagi and
I. V. Ramakrishnan An $O(\log n)$ algorithm for parallel
update of minimum spanning trees . . . . 223--229
Ming Li and
Yaacov Yesha String-Matching Cannot Be Done by a
Two-Head One-Way Deterministic Finite
Automaton . . . . . . . . . . . . . . . 231--235
John B. Evans Experiments with Trees for the Storage
and Retrieval of Future Events . . . . . 237--242
G. K. Gupta and
B. Srinivasan Approximate storage utilization of
$B$-trees . . . . . . . . . . . . . . . 243--246
Paul Bourret and
R. Souza de Oliveira Lower and upper bounds of the sizes of
domains: estimates and experiments . . . 247--253
Herbert J. Bernstein Determining the shape of a convex
$n$-sided polygon by using $2n+k$
tactile probes . . . . . . . . . . . . . 255--260
Arthur M. Keller Set-Theoretic Problems of Null
Completion in Relational Databases . . . 261--265
Yannis Manolopoulos Batched Search of Index Sequential Files 267--272
Timo O. Alanko and
R. L. Smelianski On the calculation of control transition
probabilities in a program . . . . . . . 273--276
Thomas Lickteig Gaussian elimination is optimal for
solving linear equations in dimension
two . . . . . . . . . . . . . . . . . . 277--279
Yoshito Hanatani and
Ronald Fagin A Simple Characterization of Database
Dependency Implication . . . . . . . . . 281--283
Ian Parberry On recurrent and recursive
interconnection patterns . . . . . . . . 285--289
Dan Gusfield and
Leonard Pitt Equivalent approximation algorithms for
node cover . . . . . . . . . . . . . . . 291--294
Kunio Aizawa and
Akira Nakamura Direction-independent application of
productions on two-dimensional arrays 295--301
Frank Dehne $O(n^{1/2})$ algorithms for the maximal
elements and ECDF searching problem on a
mesh-connected parallel computer . . . . 303--306
Krzysztof R. Apt and
Dexter C. Kozen Limits for automatic verification of
finite-state concurrent systems . . . . 307--309
R. K. Arora and
S. P. Rana and
M. N. Gupta Distributed termination detection
algorithm for distributed computations 311--314
Sandra Sattolo An Algorithm to Generate a Random Cyclic
Permutation . . . . . . . . . . . . . . 315--317
Ernst L. Leiss and
Chamaiporn Jitmedha Horizontally and vertically bounded
propagation of privileges . . . . . . . 319--327
Tadao Takaoka An On-Line Pattern Matching Algorithm 329--330
Wojciech Rytter The Space Complexity of the Unique
Decipherability Problem . . . . . . . . 1--3
Ferng-Ching Lin and
Wei Kuan Shih Long edges in the layouts of
shuffle-exchange and cube-connected
cycles graphs . . . . . . . . . . . . . 5--9
G. Tinhofer and
H. Schreck The Bounded Subset Sum Problem is Almost
Everywhere Randomly Decidable in $O(N)$ 11--17
Hartmut Schmeck On the maximum edge length in VLSI
layouts of complete binary trees . . . . 19--23
José L. Balcázar On $\Delta^{\rm P}_2$-immunity . . . . . 25--28
Karel Culik, II and
Juhani Karhumäki A Note on the Equivalence Problem of
Rational Formal Power Series . . . . . . 29--31
K. Kakuta and
H. Nakamura and
S. Iida A Parallel Reference Counting Algorithm 33--37
Bernd-Jürgen J. Falkowski and
Lothar Schmitz A Note on the Queens' Problem . . . . . 39--46
O. M. Vikas and
Suresh Kumar Basandra Data algebra and its application in
database design . . . . . . . . . . . . 47--54
Ivan Lavallée and
Gérard Roucairol A Fully Distributed (Minimal) Spanning
Tree Algorithm . . . . . . . . . . . . . 55--62
Alberto Apostolico Improving the worst-case performance of
the Hunt-Szymanski strategy for the
longest common subsequence of two
strings . . . . . . . . . . . . . . . . 63--69
Hans Rohnert Shortest paths in the plane with convex
polygonal obstacles . . . . . . . . . . 71--76
Rob R. Hoogerwoord An Implementation of Mutual Inclusion 77--80
Wojciech Rytter An Application of Mehlhorn's Algorithm
for Bracket Languages to $\log(N)$ Space
Recognition of Input-Driven Languages 81--84
Janusz Laski An Algorithm for the Derivation of
Codefinitions in Computer Programs . . . 85--90
J. K. Annot and
M. D. Janssens and
A. J. Van De Goor Comments on Morris's starvation-free
solution to the mutual exclusion problem
[Inform. Process. Lett. \bf 8(2), 15
February 1979, pp. 76--80] . . . . . . . 91--97
Simeon Ntafos On gallery watchmen in grids . . . . . . 99--102
John Franco On the probabilistic performance of
algorithms for the satisfiability
problem . . . . . . . . . . . . . . . . 103--106
Bruno Codenotti and
Grazia Lotti Area-time tradeoffs for bilinear forms
computations in VLSI . . . . . . . . . . 107--109
Bruno Codenotti and
Grazia Lotti A VLSI Fast Solver for Tridiagonal
Linear Systems . . . . . . . . . . . . . 111--114
O. M. Makarov A Noncommutative Algorithm for
Multiplying $5 \times 5$ Matrices Using
102 Multiplications . . . . . . . . . . 115--117
Ten-Hwang H. Lai and
Alan Sprague A Note on Anomalies in Parallel
Branch-And-Bound Algorithms with
One-To-One Bounding Functions . . . . . 119--122
Jack Cooper and
Selim G. Akl Efficient selection on a binary tree . . 123--126
Patricio V. Poblete Approximating functions by their Poisson
transform . . . . . . . . . . . . . . . 127--130
Alan A. Bertossi Total domination in interval graphs . . 131--134
Wojciech Szpankowski On an asymptotic analysis of a tree-type
algorithm for broadcast communications 135--142
Klaus W. Wagner On the intersection of the class of
linear context-free languages and the
class of single-reset languages . . . . 143--146
G. Mints and
E. Tyugu Semantics of a declarative language . . 147--151
Kazem Taghva Some characterizations of finitely
specifiable implicational dependency
families . . . . . . . . . . . . . . . . 153--158
Jan Tijmen Udding Absence of individual starvation using
weak semaphores . . . . . . . . . . . . 159--162
R. B. Tan and
G. Tel and
J. van Leeuwen Comments on: ``Distributed termination
detection algorithm for distributed
computations'' [Inform. Process. Lett.
\bf 22 (1986), no. 6, 311--314; MR
87j:68034a] by R. K. Arora, S. P. Rana
and M. N. Gupta . . . . . . . . . . . . 163--163
Patrick Dehornoy Turing complexity of the ordinals . . . 167--170
M. Latteux and
E. Timmerman Finitely Generated $\omega$-Languages 171--175
Bowen Alpern and
Alan J. Demers and
Fred B. Schneider Safety without stuttering . . . . . . . 177--180
David R. O'Hallaron and
Paul F. Reynolds, Jr. A Generalized Deadlock Predicate . . . . 181--188
Lenore Blum Towards an asymptotic analysis of
Karmarkar's algorithm . . . . . . . . . 189--194
Alan A. Bertossi and
Maurizio A. Bonuccelli Hamiltonian circuits in interval graph
generalizations . . . . . . . . . . . . 195--200
Susumu Yamasaki and
Shuji Doshita Resolution deduction to detect
satisfiability for another class
including non-Horn sentences in
propositional logic . . . . . . . . . . 201--207
Dan Gordon Eliminating the flag in threaded binary
search trees . . . . . . . . . . . . . . 209--214
O. J. Murphy and
S. M. Selkow The Efficiency of Using $k$-$d$ Trees
for Finding Nearest Neighbors in
Discrete Space . . . . . . . . . . . . . 215--218
R. E. Tarjan Corrigendum: ``Sensitivity analysis of
minimum spanning trees and shortest path
trees'' [Inform. Process. Lett. \bf
14(1), 27 March 1982, pp. 30--33] . . . 219--219
R. Sommerhalder and
S. C. Van Westrhenen A Parallel ${O}(\log n)$ Algorithm for
the Drawing of Algebraic Curves in an $n
\times n$ Square . . . . . . . . . . . . 221--226
Klaus Ambos-Spies A Note on Complete Problems for
Complexity Classes . . . . . . . . . . . 227--230
Jan L. A. Van de Snepscheut and
Jan Tijmen Udding An Alternative Implementation of
Communication Primitives . . . . . . . . 231--238
David John Evans and
Nadia Y. Yousif Merging by the parallel jump searching
algorithm . . . . . . . . . . . . . . . 239--246
G. Chen and
M. H. Williams The Value of an Array Facility in Prolog 247--251
Manfred Broy Denotational semantics of communicating
sequential programs . . . . . . . . . . 253--259
Jordan Stojanovski A note on implementing Prolog in Lisp 261--264
C. C. Handley An in situ distributive sort . . . . . . 265--270
Erkki Mäkinen A Note on Pure Grammars . . . . . . . . 271--274
Ernst L. Leiss The Inaccessible Set: a Classification
by Query Type of Security Risks in
Statistical Databases . . . . . . . . . 275--279
Mich\`ele Benois and
Jacques Sakarovitch On the Complexity of Some Extended Word
Problems Defined by Cancellation Rules 281--287
Herbert Edelsbrunner and
Emo Welzl Halfplanar range search in linear space
and ${O}(n^{0.695})$ query time . . . . 289--293
Alain J. Martin A New Generalization of Dekker's
Algorithm for Mutual Exclusion . . . . . 295--297
Leszek Holenderski The Correctness of Nondeterministic
Programs Revisited . . . . . . . . . . . 299--303
Lloyd Allison and
Trevor I. Dix A Bit-String Longest-Common-Subsequence
Algorithm . . . . . . . . . . . . . . . 305--310
Kwang-Moo M. Choe and
Chun-Hyon H. Chang Efficient computation of the locally
least-cost insertion string for the LR
error repair . . . . . . . . . . . . . . 311--316
Frank Harary and
Peter J. Slater A Linear Algorithm for the Cutting
Center of a Tree . . . . . . . . . . . . 317--319
Richard B. Kieburtz When chasing your tail saves time graph
theory . . . . . . . . . . . . . . . . . 321--324
Ikuo Nakata and
Masataka Sassa L-attributed LL(1)-grammars are
LR-attributed . . . . . . . . . . . . . 325--328
Athanasios Alexandrakis and
Symeon Bozapalidis Weighted grammars and Kleene's theorem 1--4
Stuart A. Kurtz and
Michael J. O'Donnell and
James S. Royer How to prove representation-independent
independence results . . . . . . . . . . 5--10
W. H. J. Feijen and
A. J. M. Van Gasteren and
David Gries In-situ inversion of a cyclic
permutation . . . . . . . . . . . . . . 11--14
Taenam Kim and
Kyung-Yong Y. Chwa An ${O}(n \log n \log \log n)$ Parallel
Maximum Matching Algorithm for Bipartite
Graphs . . . . . . . . . . . . . . . . . 15--17
Peter Hochschild Multiple cuts, input repetition, and
VLSI complexity . . . . . . . . . . . . 19--24
Raphael Finkel and
Hari H. Madduri An Efficient Deadlock Avoidance
Algorithm . . . . . . . . . . . . . . . 25--30
Masataka Sassa and
Harushi Ishizuka and
Ikuo Nakata ECLR-attributed grammars: a practical
class of LR-attributed grammars . . . . 31--41
A. J. Bernstein Predicate transfer and timeout in
message passing systems . . . . . . . . 43--52
R. S. Bird and
John Hughes The Alpha-Beta Algorithm: an Exercise in
Program Transformation . . . . . . . . . 53--57
Toshitsugu Yuba and
Mamoru Hoshi Binary search networks: a new method for
key searching . . . . . . . . . . . . . 59--65
V. Arvind and
S. Biswas An ${O}(n^2)$ Algorithm for the
Satisfiability Problem of a Subset of
Propositional Sentences in CNF That
Includes All Horn Sentences . . . . . . 67--69
Maciej Slusarek An Off-Line Storage Allocation Algorithm 71--75
E. Allen Emerson Uniform inevitability is tree automaton
ineffable . . . . . . . . . . . . . . . 77--79
Anne Grazon An Infinite Word Language Which is Not
co-CFL . . . . . . . . . . . . . . . . . 81--85
Ouri Wolfson Concurrent execution of transaction
copies . . . . . . . . . . . . . . . . . 87--93
Dan Field A note on a new data structure for
in-the-past queries . . . . . . . . . . 95--96
Claudio Rey and
Rabab Ward On determining the on-line minimax
linear fit to a discrete point set in
the plane . . . . . . . . . . . . . . . 97--101
Bogdan Korel The program dependence graph in static
program testing . . . . . . . . . . . . 103--108
Georg Gottlob Subsumption and implication . . . . . . 109--111
Masataka Sassa and
Ikuo Nakata A simple realization of LR-parsers for
regular right part grammars . . . . . . 113--120
Richard Anderson and
Ernst W. Mayr Parallelism and the maximal path problem 121--126
C. A. R. Hoare and
Jifeng He The weakest prespecification . . . . . . 127--132
Mihalis Yannakakis and
F\uanic\ua Gavril The maximum $k$-colorable subgraph
problem for chordal graphs . . . . . . . 133--137
A. K. Pujari and
S. Gupta Comment on: ``Worst-case choice for the
stable marriage problem'' [Inform.
Process. Lett. \bf 21 (1985), no. 1,
27--30; MR 87b:68081] by D. Kapur and M.
S. Krishnamoorthy . . . . . . . . . . . 139--139
Marek Kubale The complexity of scheduling independent
two-processor tasks on dedicated
processors . . . . . . . . . . . . . . . 141--147
Mark W. Krentel A note on the transaction backout
problem . . . . . . . . . . . . . . . . 149--152
Richard P. Anstee A polynomial algorithm for
$b$-matchings: an alternative approach 153--157
M. Roussille and
P. Dufour Generation of convex polygons with
individual angular constraints . . . . . 159--164
W. F. McColl and
M. S. Paterson The planar realization of Boolean
functions . . . . . . . . . . . . . . . 165--170
D\~ung T. Hu\`ynh On solving hard problems by
polynomial-size circuits . . . . . . . . 171--176
Dick Grune How to compare the incomparable . . . . 177--181
M. Castan and
M.-H. Durand and
M. Lemaî tre A set of combinators for abstraction in
linear space . . . . . . . . . . . . . . 183--188
D. C. Van Leijenhorst and
Th. P. Van der Weide On a recursion connected with tree
balancing algorithms . . . . . . . . . . 189--192
Varol Akman An algorithm for determining an opaque
minimal forest of a convex polygon . . . 193--198
Michel Raynal A distributed algorithm to prevent
mutual drift between $n$ logical clocks 199--202
Leonard Pitt A Note on Extending Knuth's Tree
Estimator to Directed Acyclic Graphs . . 203--206
D. J. Evans and
W. S. Yousif Explicit solution of block tridiagonal
systems of linear equations . . . . . . 207--209
J. Bazewicz and
G. Finke Minimizing mean weighted execution time
loss on identical and uniform processors A259--A263
Jan L. A. Van De Snepscheut ``Algorithms for on-the-fly garbage
collection'' revisited . . . . . . . . . 211--216
Shaunak R. Pawagi and
P. S. Gopalakrishnan and
I. V. Ramakrishnan Computing dominators in parallel . . . . 217--221
D. C. Van Leijenhorst A note on the formula size of the
`$\bmod k$' functions . . . . . . . . . 223--224
M. Zubair and
B. B. Madan Time efficient systolic architecture for
matrix*vector multiplication . . . . . . 225--231
Dario Bini and
Victor Ya. Pan A logarithmic Boolean time algorithm for
parallel polynomial division . . . . . . 233--237
Anders Edenbrandt Chordal graph recognition is in NC . . . 239--241
Prakash Ramanan Obtaining lower bounds using artificial
components (fixed order algebraic
decision tree model) . . . . . . . . . . 243--246
Svante Carlsson A variant of Heapsort with almost
optimal number of comparisons . . . . . 247--250
Martin Charles Golumbic A general method for avoiding cycling in
a network . . . . . . . . . . . . . . . 251--253
Silvio Romero de Lemos Meira Strict Combinators . . . . . . . . . . . 255--258
J. B\la\.zewicz and
G. Finke Minimizing mean weighted execution time
loss on identical and uniform processors 259--263
R. Nigel Horspool and
Michael R. Levy Correctness of an extended
operator-precedence parsing algorithm 265--273
Jonathan Ruby A liveness property of a parallel
algorithm . . . . . . . . . . . . . . . 275--277
Jayme Luiz Szwarcfiter A note on the computation of the
$k$-closure of a graph . . . . . . . . . 279--280
Klaus Madlener and
Friedrich Otto Using string-rewriting for solving the
word problem for finitely presented
groups . . . . . . . . . . . . . . . . . 281--284
Takao Asano and
Tetsuo Asano and
Hiroshi Imai Shortest path between two simple
polygons . . . . . . . . . . . . . . . . 285--288
M. D. Atkinson and
H. W. Chang Computing the number of mergings with
constraints . . . . . . . . . . . . . . 289--292
Cyrus Hazari and
Hussein Zedan A distributed algorithm for distributed
termination . . . . . . . . . . . . . . 293--297
Gregers Koch Automating the semantic component . . . 299--305
D. S. Hirschberg and
Dennis James Volper Improved Update/Query Algorithms for the
Interval Valuation Problem . . . . . . . 307--310
Ernest J. H. Chang and
Gaston H. Gonnet and
Doron Rotem On the costs of self-stabilization . . . 311--316
Mark Valentine and
Robert H. Davis The automated solution of logic puzzles 317--324
Marek Chrobak and
Wojciech Rytter Remarks on string-matching and one-way
multihead automata . . . . . . . . . . . 325--329
R. D. Tennent A note on undefined expression values in
programming logics . . . . . . . . . . . 331--333
Peter Widmayer and
Derick Wood Time- and space-optimal contour
computation for a set of rectangles . . 335--338
Michael B. Dillencourt Traveling salesman cycles are not always
subgraphs of Delaunay triangulations or
of minimum weight triangulations . . . . 339--342
J. R. Kennaway and
M. R. Sleep Variable abstraction in $O(n\log n)$
space . . . . . . . . . . . . . . . . . 343--349
Heinrich Müller Sorting Numbers Using Limited Systolic
Coprocessors . . . . . . . . . . . . . . 351--354
Georg Gottlob On the size of nonredundant FD-covers 355--360
Andrzej Szepietowski There are no fully space constructible
functions between $\log \log n$ and
$\log n$ . . . . . . . . . . . . . . . . 361--362
Ian Parberry An improved simulation of space and
reversal bounded deterministic Turing
machines by width and depth bounded
uniform circuits . . . . . . . . . . . . 363--367
Hanan Samet and
Clifford A. Shaffer and
Robert E. Webber Digitizing the plane with cells of
nonuniform size . . . . . . . . . . . . 369--375
Anselm Blumer and
Andrzej Ehrenfeucht and
David Haussler and
Manfred K. Warmuth Occam's Razor . . . . . . . . . . . . . 377--380
M. Bajantri and
David B. Skillicorn A fast multiprocessor message passing
implementation . . . . . . . . . . . . . 381--389
Christopher W. Fraser and
David R. Hanson Optimization of argument evaluation
order . . . . . . . . . . . . . . . . . 391--395
Raymond Marie and
Kishor S. Trivedi A note on the effect of preemptive
policies on the stability of a priority
queue . . . . . . . . . . . . . . . . . 397--401
William E. Wright A note on external sorting using almost
single input buffering . . . . . . . . . 403--405
M. K. Sridhar A new algorithm for parallel solution of
linear equations . . . . . . . . . . . . 407--412
Herbert Edelsbrunner and
Mark H. Overmars Zooming by repeated range detection . . 413--417
Jik H. Chang and
Oscar H. Ibarra and
Bala Ravikumar and
Leonard Berman Some observations concerning alternating
Turing machines using small space . . . 1--9
Avraham A. Melkman On-line construction of the convex hull
of a simple polyline . . . . . . . . . . 11--12
Bernd Kirsig and
Klaus-Jörn J. Lange Separation with the Ruzzo, Simon, and
Tompa relativization implies ${\sc
Dspace}(\log n)\not= {\sc Nspace}(\log
n)$ . . . . . . . . . . . . . . . . . . 13--15
Richard G. Hamlet Probable correctness theory . . . . . . 17--25
Rodney R. Howell and
Louis E. Rosier and
Hsu-Chun Yen An ${O}(n^{1.5})$ algorithm to decide
boundedness for conflict-free vector
replacement systems . . . . . . . . . . 27--33
George Cybenko and
David W. Krumme and
K. N. Venkataraman Fixed Hypercube embedding . . . . . . . 35--39
Jean-Paul P. Laumond Obstacle growing in a nonpolygonal world 41--50
Joseph Naor A fast parallel coloring of planar
graphs with five colors . . . . . . . . 51--53
Cao An Wang and
Yung H. Tsin An $O(\log n)$ time parallel algorithm
for triangulating a set of points in the
plane . . . . . . . . . . . . . . . . . 55--60
Gary A. Hyslop and
Edmund A. Lamagna Performance of distributive partitioned
sort in a demand paging environment . . 61--64
John H. Reif A topological approach to dynamic graph
connectivity . . . . . . . . . . . . . . 65--70
C. A. R. Hoare and
Jifeng He and
J. W. Sanders Prespecification in data refinement . . 71--76
Jyrki Katajainen and
Olli Nevalainen and
Jukka Teuhola A linear expected-time algorithm for
computing planar relative neighbourhood
graphs . . . . . . . . . . . . . . . . . 77--86
Mikhail Atallah and
Chanderjit Bajaj Efficient algorithms for common
transversals . . . . . . . . . . . . . . 87--91
Manfred Broy Predicative Specifications for
Functional Programs Describing
Communicating Networks . . . . . . . . . 93--101
K. B. Lakshmanan and
N. Meenakshi and
K. Thulasiraman A time-optimal message-efficient
distributed algorithm for
depth-first-search . . . . . . . . . . . 103--109
A. M. Frieze Parallel algorithms for finding Hamilton
cycles in random graphs . . . . . . . . 111--117
F. Miller Maley An observation concerning
constraint-based compaction . . . . . . 119--122
V. J. Rayward-Smith The complexity of preemptive scheduling
given interprocessor communication
delays . . . . . . . . . . . . . . . . . 123--125
Ravi B. Boppana and
Johan Håstad and
Stathis Zachos Does co-NP have short interactive
proofs? . . . . . . . . . . . . . . . . 127--132
R. D. Tennent Quantification in Algol-like languages 133--137
G. Mints and
E. Tyugu Corrigendum: ``Semantics of a
declarative language'' [Inform. Process.
Lett. \bf 23(3), 22 October 1997, pp.
147--151] . . . . . . . . . . . . . . . 139--139
Yoshihito Toyama Counterexamples to termination for the
direct sum of term rewriting systems . . 141--143
J. Pierre Verjus On the proof of a distributed algorithm 145--147
Michael B. Dillencourt A non-Hamiltonian, nondegenerate
Delaunay Triangulation . . . . . . . . . 149--151
Ten H. Lai and
Tao H. Yang On distributed snapshots . . . . . . . . 153--158
Andrew Klapper A lower bound on the complexity of the
convex hull problem for simple polyhedra 159--161
Ozalp Babaoglu Stopping times of distributed consensus
protocols: A probabilistic analysis . . 163--169
Satoru Kawai Local authentication in insecure
environments . . . . . . . . . . . . . . 171--174
Michael J. Fischer and
Neil Immerman Interpreting logics of knowledge in
propositional dynamic logic with
converse . . . . . . . . . . . . . . . . 175--181
Tae-Choong Chung and
Jung-Wan Cho History sensitive string for multiple
alphabets . . . . . . . . . . . . . . . 183--188
T. H. Tse On the detection of unstructuredness in
flowgraphs . . . . . . . . . . . . . . . 189--193
Dieter Zöbel Transformations for communication
fairness in CSP . . . . . . . . . . . . 195--198
N. A. Alexandridis and
P. D. Tsanakas An Encoding Scheme for the Efficient
Representation of Hierarchical Image
Structures . . . . . . . . . . . . . . . 199--206
Joseph M. Morris Varieties of weakest liberal
preconditions . . . . . . . . . . . . . 207--210
Jean-Michel Autebert and
Philippe Flajolet and
Joaquim Gabarró Prefixes of infinite words and ambiguous
context-free languages . . . . . . . . . 211--216
Bettina Brustmann and
Ingo Wegener The complexity of symmetric functions in
bounded-depth circuits . . . . . . . . . 217--219
Edward Ochmanski Inevitability in concurrent systems . . 221--225
Rainer Kemp A note on the number of leftist trees 227--232
J. G. Wiltink A deficiency of natural deduction . . . 233--234
Alberto Apostolico Remark on the Hsu--Du new algorithm for
the longest common subsequence problem 235--236
David Gries and
Adriano Pascoletti and
Luigi Sbriz Horner's rule and the computation of
linear recurrences . . . . . . . . . . . 237--240
Andrew V. Goldberg and
Serge A. Plotkin Parallel ($\delta + 1$)-Coloring of
Constant-Degree Graphs . . . . . . . . . 241--245
Christos Levcopoulos An $\Omega(\sqrt{n})$ lower bound for
the nonoptimality of the greedy
triangulation . . . . . . . . . . . . . 247--251
Matthias Reichling A simplified solution of the $N$ queens'
problem . . . . . . . . . . . . . . . . 253--255
Anatoli\uì O. Buda Multiprocessor automata . . . . . . . . 257--261
Sandeep N. Bhatt and
Stavros S. Cosmadakis The complexity of minimizing wire
lengths in VLSI layouts . . . . . . . . 263--267
O. Fries and
K. Mehlhorn and
S. Näher and
A. Tsakalidis A $\log \log n$ data structure for
three-sided range queries . . . . . . . 269--273
Andrew W. Appel Garbage collection can be faster than
stack allocation . . . . . . . . . . . . 275--279
Vijay Raghavan and
Shankar M. Venkatesan On bounds for a board covering problem 281--284
Jeffrey S. Salowe and
W. L. Steiger Stable Unmerging in Linear Time and
Constant Space . . . . . . . . . . . . . 285--294
K. Venkatesh and
T. Radhakrishnan and
H. F. Li Optimal checkpointing and local
recording for domino-free rollback
recovery . . . . . . . . . . . . . . . . 295--303
Jerzy R. Nawrocki and
J. Martinek A storage allocation method with
invalidating dangling references . . . . 305--310
Cristian Calude Super-exponentials nonprimitive
recursive, but rudimentary . . . . . . . 311--315
S. S. Ravi and
H. B. Hunt, III An application of the Planar Separator
Theorem to counting problems . . . . . . 317--321
David Gries and
Ivan Stojmenovic A Note on Graham's Convex Hull Algorithm 323--327
Yun Zhou Zhu and
To Yat Cheung A new distributed breadth-first-search
algorithm . . . . . . . . . . . . . . . 329--333
Rina Suros and
E. Montagne Fitted diagonals for reducing I/O
bandwidth in systolic systems . . . . . 335--341
Stuart A. Friedberg and
Gary L. Peterson An efficient solution to the mutual
exclusion problem using weak semaphores 343--347
G. Tel and
J. Van Leeuwen Comments on ``A distributed algorithm
for distributed termination'' [Inform.
Process. Lett. \bf 24(5), 16 March 1987,
pp. 293--297] . . . . . . . . . . . . . 349--349
Kadri Krause and
Lawrence L. Larmore and
Dennis James Volper Packing items from a triangular
distribution . . . . . . . . . . . . . . 351--361
Joanna J\polhkedrzejowicz Nesting of shuffle closure is important 363--367
Jean Pallo On the rotation distance in the lattice
of binary trees . . . . . . . . . . . . 369--373
Ricardo A. Baeza-Yates Some average measures in $m$-ary search
trees . . . . . . . . . . . . . . . . . 375--382
Shlomo Moran Generalized lower bounds derived from
Håstad's main lemma (small depth
circuits) . . . . . . . . . . . . . . . 383--388
Manfred Kunde and
Horst Steppat On the worst-case ratio of a compound
multiprocessor scheduling algorithm . . 389--396
Imrich V\vr\softto The area-time complexity of the VLSI
counter . . . . . . . . . . . . . . . . 397--400
F. Peper Determining connected components in
linear time by a linear number of
processors . . . . . . . . . . . . . . . 401--406
Udo Kelter The complexity of strict serializability
revisited . . . . . . . . . . . . . . . 407--411
Youichi Kobuchi A note on symmetrical cellular spaces 413--415
Shaunak R. Pawagi and
P. S. Gopalakrishnan and
I. V. Ramakrishnan Corrigendum: ``Computing dominators in
parallel'' . . . . . . . . . . . . . . . 417--417
Brigitte Jaumard and
Bruno Simeone On the complexity of the maximum
satisfiability problem for Horn formulas 1--4
James R. Driscoll and
Sheau-Dong Lang and
LeRoy A. Franklin Modeling $B$-tree insertion activity . . 5--18
Alfs T. Berztiss A notation for distributed operations 19--21
Jean Berstel and
Sre\vcko Brlek On the length of word chains . . . . . . 23--28
Ronald V. Book and
Hai-Ning Liu Rewriting systems and word problems in a
free partially commutative monoid . . . 29--32
Svante Carlsson The Deap --- a Double-Ended Heap to
Implement Double-Ended Priority Queues 33--36
Janet Incerpi and
Robert Sedgewick Practical variations of Shellsort . . . 37--43
Jean Claude Bermond and
Jean Michel Fourneau and
Alain Jean-Marie Equivalence of multistage
interconnection networks . . . . . . . . 45--50
László Babai Random oracles separate ${\rm PSPACE}$
from the polynomial-time hierarchy . . . 51--53
Y. Métivier and
E. Ochmanski On Lexicographic Semi-Commutations . . . 55--59
Xiaojun Shen and
Herbert Edelsbrunner A tight lower bound on the size of
visibility graphs . . . . . . . . . . . 61--64
Michael Rusinowitch On termination of the direct sum of
term-rewriting systems . . . . . . . . . 65--70
Andranik Mirzaian A halving technique for the longest
stuttering subsequence problem . . . . . 71--75
Jan Magott Performance evaluation of concurrent
systems using conflict-free and
persistent Petri nets . . . . . . . . . 77--80
Zvi Galil and
Moti Yung Partitioned encryption and achieving
simultaneity by partitioning . . . . . . 81--88
C. Mathieu and
Claude Puech and
Hossein Yahia Average efficiency of data structures
for binary image processing . . . . . . 89--93
K. G. Subramanian and
Rani Siromoney and
P. Jeyanthi Abisha A D0L-T0L public key cryptosystem . . . 95--97
Ajay K. Gupta and
Susanne E. Hambrusch Optimal three-dimensional layouts of
complete binary trees . . . . . . . . . 99--104
Matthew Thazhuthaveetil and
J. and
Andrew R. Pleszkun On the structural locality of reference
in LISP list access streams . . . . . . 105--110
Andrzej Sza\las Arithmetical Axiomatization of
First-Order Temporal Logic . . . . . . . 111--116
O. Sýkora and
I. V\vr\softto Tight chip area lower bounds for string
matching . . . . . . . . . . . . . . . . 117--119
Mingfa Zhu and
Nan K. Loh and
Pepe Siy Towards the minimum set of primitive
relations in temporal logic . . . . . . 121--126
Y. Hou Trinity algebra and its application to
machine decompositions . . . . . . . . . 127--134
A. S. M. Sajeev and
J. Olszewski Manipulation of data structures without
pointers . . . . . . . . . . . . . . . . 135--143
Shlomo Moran and
Yaron Wolfstahl Extended impossibility results for
asynchronous complete networks . . . . . 145--151
Johan Håstad One-way permutations in ${\rm NC}^0$ . . 153--155
Michael R. Fellows and
Michael A. Langston Nonconstructive advances in
polynomial-time complexity . . . . . . . 157--162
H. Balsters Comments on: ``A deficiency of natural
deduction'' [Inform. Process. Lett. \bf
25 (1987), no. 4, 233--234; MR
88i:03020a] by J. G. Wiltink . . . . . . 163--164
K. R. Apt and
Luc Bougé and
Ph. Clermont Two normal form theorems for CSP
programs . . . . . . . . . . . . . . . . 165--171
Michael T. Goodrich Finding the convex hull of a sorted
point set in parallel . . . . . . . . . 173--179
Ursula Martin Extension functions for multiset
orderings . . . . . . . . . . . . . . . 181--186
Shlomit S. Pinter and
Yaron Wolfstahl Embedding ternary trees in VLSI arrays 187--191
U. Guntzer and
M. Paul Jump interpolation search trees and
symmetric binary numbers . . . . . . . . 193--204
Tadao Takaoka A decomposition rule for the Hoare logic 205--208
Alberto Apostolico and
Susanne E. Hambrusch Finding maximum cliques on circular-arc
graphs . . . . . . . . . . . . . . . . . 209--215
C. Baleanu and
D. Tomescu An architecture for symbolic processing 217--222
Claudio Arbib A polynomial characterization of some
graph partitioning problems . . . . . . 223--230
Karel Culik, II and
Juhani Karhumäki On totalistic systolic networks . . . . 231--236
Andrzej Sieminski Fast decoding of the Huffman codes . . . 237--241
Carroll C. Morgan Data refinement by miracles . . . . . . 243--246
Patrick W. Dymond Input-driven languages are in $\log n$
depth . . . . . . . . . . . . . . . . . 247--250
Eljas Soisalon-Soininen and
Jorma Tarhio Looping LR parsers . . . . . . . . . . . 251--253
Klaus Hinrichs and
Jürg Nievergelt and
Peter Schorn Plane-sweep solves the closest pair
problem elegantly . . . . . . . . . . . 255--261
O. Y. De Vel and
E. V. Krishnamurthy An iterative pipelined array
architecture for the generalized matrix
inversion . . . . . . . . . . . . . . . 263--267
Stephen A. Cook Short propositional formulas represent
nondeterministic computations . . . . . 269--270
Erkki Mäkinen On the rotation distance of binary trees 271--272
Joel Seiferas A Variant of Ben-Or's Lower Bound for
Algebraic Decision Trees . . . . . . . . 273--276
Ganesh C. Gopalakrishnan and
Mandayam K. Srivas Implementing functional programs using
mutable abstract data types . . . . . . 277--286
Tat Hung Chan The boundedness problem for
three-dimensional vector addition
systems with states . . . . . . . . . . 287--289
Bruce M. Maggs and
Serge A. Plotkin Minimum-cost spanning tree as a
path-finding problem . . . . . . . . . . 291--293
Richard John Cole An optimally efficient selection
algorithm . . . . . . . . . . . . . . . 295--299
Isreal Cidon Yet another distributed
depth-first-search algorithm . . . . . . 301--305
Rolf G. Karlsson and
Mark H. Overmars Normalized divide-and-conquer: a scaling
technique for solving multi-dimensional
problems . . . . . . . . . . . . . . . . 307--312
Ludwik Czaja Cause-effect structures . . . . . . . . 313--319
Marc Bezem and
Jan Van Leeuwen On estimating the complexity of
logarithmic decompositions . . . . . . . 321--324
John Russell Gilbert Some nested dissection order is nearly
optimal . . . . . . . . . . . . . . . . 325--328
M. Balakrishnan and
S. Sutarwala and
A. K. Majumdar and
D. K. Banerji and
J. G. Linders and
J. C. Majithia A semantic approach for modular
synthesis of VLSI systems . . . . . . . 1--7
Ming Li A separator theorem for one-dimensional
graphs under linear mapping . . . . . . 9--11
Mikhail J. Atallah and
Greg N. Frederickson and
S. Rao Kosaraju Sorting with efficient use of
special-purpose sorters . . . . . . . . 13--15
G. Ramalingam and
C. Pandu Rangan Total domination in interval graphs
revisited . . . . . . . . . . . . . . . 17--21
Gordon Lyon A tagless marking that is linear over
subtrees . . . . . . . . . . . . . . . . 23--28
Mark B. Josephs The data refinement calculator for $Z$
specifications . . . . . . . . . . . . . 29--33
Douglas Lea Digital and Hilbert ${K}$-${D}$ Trees 35--41
Alan M. Gibbons and
Amos Israeli and
Wojciech Rytter Parallel $O(\log n)$ time edge-colouring
of trees and Halin graphs . . . . . . . 43--51
Jik H. Chang and
Oscar H. Ibarra and
Bala Ravikumar Erratum: ``Some observations concerning
alternating Turing machines using small
space'' [Inform. Process. Lett. \bf 25
(1987), no. 1, 1--9; MR 88e:68026] by
the authors and L. Berman . . . . . . . 53--53
Bogdan S. Chlebus A parallel bucket sort . . . . . . . . . 57--61
Jacek Witaszek A practical method for finding the
optimum postponement transformation for
LR(k) parsers . . . . . . . . . . . . . 63--67
Mukesh Singhal and
Yelena Yesha A polynomial algorithm for computation
of the probability of conflicts in a
database under arbitrary data access
distribution . . . . . . . . . . . . . . 69--74
Satoru Miyano A parallelizable lexicographically first
maximal edge- induced subgraph problem 75--78
C. C. Chang and
C. H. Chang An Ordered Minimal Perfect Hashing
Scheme with Single Parameter . . . . . . 79--83
Robin Liu and
Simeon Ntafos On decomposing polygons into uniformly
monotone parts . . . . . . . . . . . . . 85--89
Franz Baader A note on unification type zero . . . . 91--93
Ravinderpal S. Sandhu Cryptographic implementation of a tree
hierarchy for access control . . . . . . 95--98
Nicholas J. Patterson and
Kenneth J. Supowit Finding the vertices nearest to a point
in a hypercube . . . . . . . . . . . . . 99--102
Alan M. Frieze On the random construction of heaps . . 103--109
Leszek Holenderski and
Andrzej Sza\las Propositional description of finite
cause-effect structures . . . . . . . . 111--117
David S. Johnson and
Mihalis Yannakakis and
Christos H. Papadimitriou On generating all maximal independent
sets . . . . . . . . . . . . . . . . . . 119--123
Kurt Mehlhorn A faster approximation algorithm for the
Steiner problem in graphs . . . . . . . 125--128
Sharat Chandran and
Azriel Rosenfeld Order statistics on a hypercube . . . . 129--132
Alan A. Bertossi Parallel circle-cover algorithms . . . . 133--139
Stephen A. Cook and
Michael Luby A simple parallel algorithm for finding
a satisfying truth assignment to a
$2$-CNF formula . . . . . . . . . . . . 141--145
Joel Berman and
Willem J. Blok Positive Boolean dependencies . . . . . 147--150
Osamu Watanabe On hardness of one-way functions . . . . 151--157
Jacek Leszczylowski and
Staffan Bonnier and
Jan Maluszy\'nski Logic programming with external
procedures: introducing $S$-unification 159--165
Yung Hyang Tsin On Handling Vertex Deletion in Updating
Minimum Spanning Trees . . . . . . . . . 167--168
K. V. S. Ramarao and
Robert Daley and
Rami Melhem Message complexity of the set
intersection problem . . . . . . . . . . 169--174
Hans Rohnert Time and space efficient algorithms for
shortest paths between convex polygons 175--179
Richard Koo and
Sam Toueg Effects of message loss on the
termination of distributed protocols . . 181--188
Ulrich Faigle and
Rainer Schrader On the convergence of stationary
distributions in simulated annealing
algorithms . . . . . . . . . . . . . . . 189--194
Abdol Hossein Esfahanian and
S. Louis Hakimi On computing a conditional
edge-connectivity of a graph . . . . . . 195--199
Andrzej Szepietowski Remarks on languages acceptable in $\log
\log n$ space . . . . . . . . . . . . . 201--203
D. Roelants van Baronaigien and
Frank Ruskey Generating $t$-ary Trees in ${A}$-Order 205--213
Khaled M. Bugrara and
Paul W. Purdom An exponential lower bound for the pure
literal rule . . . . . . . . . . . . . . 215--219
Carla Savage Recognizing majority on a one-way mesh 221--225
Hermann Jung and
Kurt Mehlhorn Parallel algorithms for computing
maximal independent sets in trees and
for updating minimum spanning trees . . 227--236
T. Krishnaprasad On the computability of circumscription 237--243
Bob P. Weems A study of page arrangements for
extendible hashing . . . . . . . . . . . 245--248
Ashok Kumar and
V. M. Malhotra A new computation rule for Prolog . . . 249--252
Kozo Itano and
Yutaka Sato and
Hidemi Hirai and
Tomoyoshi Yamagata An incremental pattern matching
algorithm for the pipelined lexical
scanner . . . . . . . . . . . . . . . . 253--258
Harold N. Gabow and
Robert E. Tarjan A linear-time algorithm for finding a
minimum spanning pseudoforest . . . . . 259--263
Mirko K\vrivánek The complexity of ultrametric partitions
on graphs . . . . . . . . . . . . . . . 265--270
G. Ramalingam and
C. Pandu Rangan A unified approach to domination
problems on interval graphs . . . . . . 271--274
Ji\vrí Matou\vsek Line arrangements and range search . . . 275--280
Aldo de Luca and
Stefano Varricchio On the factors of the Thue--Morse word
on three symbols . . . . . . . . . . . . 281--285
Hans L. Bodlaender A better lower bound for distributed
leader finding in bidirectional,
asynchronous rings of processors . . . . 287--290
Meichun Hsu and
Stuart E. Madnick Shifting timestamps for concurrency
control in an information hierarchy . . 291--297
Shay Kutten Optimal fault-tolerant distributed
construction of a spanning forest . . . 299--307
Ewa Or\lowska Proof System for Weakest
Prespecification . . . . . . . . . . . . 309--313
M. A. Sridhar On the connectivity of the De Bruijn
graph . . . . . . . . . . . . . . . . . 315--318
Xiaoqiu Huang A lower bound for the edit-distance
problem under an arbitrary cost function 319--321
David Fernández-Baca Nonserial dynamic programming
formulations of satisfiability . . . . . 323--326
M. Sakkinen Comments on ``Manipulation of data
structures without pointers'' [Inform.
Process. Lett. \bf 26(3), 23 November
1997, pp. 135--143] . . . . . . . . . . 327--328
M. Latteux and
E. Timmerman Bifaithful starry transductions . . . . 1--4
Giuseppe F. Italiano Finding paths and deleting edges in
directed acyclic graphs . . . . . . . . 5--11
Wojciech Szpankowski The evaluation of an alternative sum
with applications to the analysis of
some data structures . . . . . . . . . . 13--19
David A. Lamb and
Robin Dawes Testing for class membership in
multi-parent hierarchies . . . . . . . . 21--25
José D. P. Rolim and
Sheila A. Greibach On the IO-complexity and approximation
languages . . . . . . . . . . . . . . . 27--31
Joanna J\polhkedrzejowicz Infinite Hierarchy of Expressions
Containing Shuffle Closure Operator . . 33--37
Wei-Pang Chin and
Simeon Ntafos Optimum watchman routes . . . . . . . . 39--44
Andrew Dwelly Synchronizing the I/O behavior of
functional programs with feedback . . . 45--51
Stephan Olariu Paw-Free Graphs . . . . . . . . . . . . 53--54
Walter W. Kirchherr Transportation of an $l \times l$ Matrix
Requires $\Omega(\log l)$ Reversals on
Conservative Turing Machines . . . . . . 55--59
Hillel Gazit and
Gary L. Miller An improved parallel algorithm that
computes the BFS numbering of a directed
graph . . . . . . . . . . . . . . . . . 61--65
Frank Dehne and
Ivan Stojmenovi\'c An ${O}(\sqrt{n})$ time algorithm for
the ECDF searching problem for arbitrary
dimensions on a mesh-of-processors . . . 67--70
Victor Pan Computing the determinant and the
characteristic polynomial of a matrix
via solving linear systems of equations 71--75
Joost Engelfriet and
Hendrik Jan Hoogeboom Prefix and equality languages of
rational functions are co-context-free 77--79
Daniel P. Bovet and
S. De Agostino and
R. Petreschi Parallelism and the feedback vertex set
problem . . . . . . . . . . . . . . . . 81--85
Yves Auffray Linear strategy for propositional modal
resolution . . . . . . . . . . . . . . . 87--92
Jürgen Ebert Computing Eulerian trails . . . . . . . 93--97
James H. Anderson and
Mohamed G. Gouda Atomic semantics of nonatomic programs 99--103
Catherine A. Schevon and
Jeffrey Scott Vitter A parallel algorithm for recognizing
unordered depth-first search . . . . . . 105--110
Alexandre Brandwajn Load imbalance in DASD dynamic
reconnection . . . . . . . . . . . . . . 111--119
Prateek Mishra Strictness Analysis of the Untyped
$\lambda$-Calculus . . . . . . . . . . . 121--125
J. Aguilar-Martin and
Claudi Alsina Characterizations of some rescaling
functions . . . . . . . . . . . . . . . 127--132
Mark Allen Weiss and
Robert Sedgewick Bad cases for Shaker-sort . . . . . . . 133--136
John F. Morrison Parallel $p$-adic computation . . . . . 137--140
Fabrizio Luccio and
A. Pietracaprina and
G. Pucci A probabilistic simulation of PRAMs on a
bounded degree network . . . . . . . . . 141--147
M. Y. Chan and
W. L. Chung Optimal multidisk partial match file
designs . . . . . . . . . . . . . . . . 149--155
Hasan Ural and
Bo Yang A structural test selection criterion 157--163
Colm Ó'Dúnlaing A tight lower bound for the complexity
of path-planning for a disc . . . . . . 165--170
Makoto Imase and
Yoshifumi Manabe Fault-Tolerant Routings in a
$\kappa$-Connected Network . . . . . . . 171--175
Moon Jung Chung and
M. S. Krishnamoorthy Algorithms of placing recovery points 177--181
Jianzhong Du and
Joseph Y.-T. T. Leung Scheduling tree-structured tasks with
restricted execution times . . . . . . . 183--188
Daniel J. Rosenkrantz and
Harry B. Hunt, III Matrix multiplication for finite
algebraic systems . . . . . . . . . . . 189--192
Yuji Takada Grammatical Inference for Even Linear
Languages Based on Control Sets . . . . 193--199
Guan-Ing Chen and
Ten Hwang Lai Preemptive scheduling of independent
jobs on a hypercube . . . . . . . . . . 201--206
Gilles Brassard and
Sampath Kannan The generation of random permutations on
the fly . . . . . . . . . . . . . . . . 207--212
Ichiro Suzuki Proving properties of a ring of
finite-state machines . . . . . . . . . 213--214
Katsushi Inoue and
Itsuo Takanami Some considerations about ${\rm
NPRIORITY(1)}$ without ROM . . . . . . . 215--219
Antoni Mazurkiewicz Solvability of the asynchronous ranking
problem . . . . . . . . . . . . . . . . 221--224
Ananth V. Iyer and
H. Donald Ratliff and
G. Vijayan Optimal node ranking of trees . . . . . 225--229
Don Platt and
Moneeb A. Magdy Adaptive control using switched
capacitor filters . . . . . . . . . . . 231--234
Shuo-Yen Robert Li Reconstruction of polygons from
projections . . . . . . . . . . . . . . 235--240
Howard J. Karloff and
Ramamohan Paturi and
Janos Simon Universal traversal sequences of length
$n^{O(\log n)}$ for cliques . . . . . . 241--243
Jean-François Romeuf Shortest path under rational constraint 245--248
Lance Fortnow and
Michael Sipser Are there interactive protocols for
CO-NP languages? . . . . . . . . . . . . 249--251
Paolo Ciaccia and
Dario Maio and
Paolo Tiberio A unifying approach to evaluating block
accesses in database organizations . . . 253--257
P. K. Das and
D. Q. M. Fay Fault-tolerant and flexible
interconnection of multiple processors 259--268
Leslie L. Miller and
S. K. Gadia and
S. Kothari and
K. C. Liu Completeness issues for join
dependencies derived from the universal
relation join dependency . . . . . . . . 269--274
Alan A. Bertossi On the domatic number of interval graphs 275--280
D. W. Wang and
Yue-Sun Kuo A study on two geometric location
problems . . . . . . . . . . . . . . . . 281--286
K. Vidyasankar Converting Lamport's regular register to
atomic register . . . . . . . . . . . . 287--290
Juris Hartmanis and
Lane Hemachandra On sparse oracles separating feasible
complexity classes . . . . . . . . . . . 291--295
Gen-Huey Chen and
M. S. Yu and
L. T. Liu Two algorithms for constructing a binary
tree from its traversals . . . . . . . . 297--299
Chin Wen Ho and
Richard C. T. Lee Efficient parallel algorithms for
finding maximal cliques, clique trees,
and minimum coloring on chordal graphs 301--309
Maciej Li\'skiewicz and
Krzysztof Lory\'s Alternating real-time computations . . . 311--316
Edward P. F. Chan and
Hector J. Hernandez Testing unboundedness of database
schemes and functional dependencies . . 317--326
Michael C. Loui and
Teresa A. Matsushita and
Douglas B. West Corrigendum: ``Election in a Complete
Network with a Sense of Direction''
[Inform. Process. Lett. \bf 22(4), 17
April 1986, pp. 185--187] . . . . . . . 327--327
Michel Minoux LTUR: a simplified linear-time unit
resolution algorithm for Horn formulae
and computer implementation . . . . . . 1--12
Shing Tsaan Huang A fully distributed termination
detection scheme . . . . . . . . . . . . 13--18
Jean-Claude Raoult Proving open properties by induction . . 19--23
Matthias Reichling On the detection of a common
intersection of $k$ convex objects in
the plane . . . . . . . . . . . . . . . 25--29
F. Warren Burton and
G. P. McKeown and
V. J. Rayward-Smith On process assignment in parallel
computing . . . . . . . . . . . . . . . 31--34
Erkki Makinen On linear search heuristics . . . . . . 35--36
Michael D. Atkinson and
N. Santoro A practical algorithm for Boolean matrix
multiplication . . . . . . . . . . . . . 37--38
J. L. W. Kessels An exercise in proving
self-stabilization with a variant
function . . . . . . . . . . . . . . . . 39--42
Masataka Sassa and
Ikuo Nakata Time-optimal short-circuit evaluation of
Boolean expressions . . . . . . . . . . 43--51
R. K. Arora and
M. N. Gupta More comments on: ``Distributed
termination detection algorithm for
distributed computations'' [Arora, Gupta
and S. P. Rana, Inform. Process. Lett.
\bf 22 (1986), no. 6, 311--314; R. B.
Tan, G. Tel and J. van Leeuwen, ibid.
\bf 23 (1986), no. 3, 163; MR 87j:68034a
b] . . . . . . . . . . . . . . . . . . . 53--55
André Arnold and
Paul Crubille A linear algorithm to solve fixed-point
equations on transition systems . . . . 57--66
Andrzej Sza\las An incompleteness result in Process
Algebra . . . . . . . . . . . . . . . . 67--70
Wojciech Rytter On efficient parallel computations of
costs of paths on a grid graph . . . . . 71--74
Frank Hoffmann and
Klaus Kriegel Embedding rectilinear graphs in linear
time . . . . . . . . . . . . . . . . . . 75--79
Andrzej Blikle A guided tour of the mathematics of
MetaSoft '88 . . . . . . . . . . . . . . 81--86
Dietmar Wätjen and
Erwin Unruh On the degree of synchronization of
$k\,$lT0L and $k\,$lET0L systems . . . . 87--89
Aldo de Luca and
Mariacristina Pelagalli and
Stefano Varricchio Test sets for languages of infinite
words . . . . . . . . . . . . . . . . . 91--95
Basile Louka and
Maurice Tchuente Dynamic programming on two-dimensional
systolic arrays . . . . . . . . . . . . 97--104
Hari Ballabh Mittal A fast backtrack algorithm for graph
isomorphism . . . . . . . . . . . . . . 105--110
Oscar H. Ibarra and
Tao Jiang and
Bala Ravikumar Some subclasses of context-free
languages in ${\rm NC}^1$ . . . . . . . 111--117
Gregory E. Shannon A linear-processor algorithm for
depth-first search in planar graphs . . 119--123
Paliath Narendran and
Friedrich Otto Preperfectness is undecidable for Thue
systems containing only length-reducing
rules and a single commutation rule . . 125--130
Gottfried Vossen A new characterization of FD implication
with an application to update anomalies 131--135
Hans L. Bodlaender The complexity of finding uniform
emulations on fixed graphs . . . . . . . 137--141
P. M. Van Den Broek Confluence of indirection reductions in
graph rewrite systems . . . . . . . . . 143--148
S. Haldar and
D. K. Subramanian Ring based termination detection
algorithm for distributed computations 149--153
Bogdan Korel and
Janusz Laski Dynamic program slicing . . . . . . . . 155--163
Jerzy R. Nawrocki and
Andrzej Urbanski Fixed-sized blocks optimization . . . . 165--169
Symeon Bozapalidis and
Stavros Ioulidis Varieties of formal series on trees and
Eilenberg's theorem . . . . . . . . . . 171--175
Sang Cho and
D\~ung T. H\`uynh On a complexity hierarchy between ${\rm
L}$ and ${\rm NL}$ . . . . . . . . . . . 177--182
Mohamed Ouksel and
Peter Scheuermann Implicit data structures for linear
hashing schemes . . . . . . . . . . . . 183--189
Chan-Ik Park and
Kyu Ho Park and
Myunghwan Kim Efficient backward execution in AND/OR
process model . . . . . . . . . . . . . 191--198
Ernst L. Leiss On the degree of dominator trees . . . . 199--200
F. E. J. Kruseman Aretz On a recursive ascent parser . . . . . . 201--206
Fabio A. Schreiber and
G. Rosolini An algebraic description of some
state-dependent failure mechanisms . . . 207--211
Sakti Pramanik and
Myoung Ho Kim HCB tree a height compressed $B$ tree
for parallel processing . . . . . . . . 213--220
Giorgio Gallo and
Maria Grazia Scutell\`a Polynomially solvable satisfiability
problems . . . . . . . . . . . . . . . . 221--227
H. J. Boom Lazy variable-renumbering makes
substitution cheap . . . . . . . . . . . 229--232
Boris S. Veroy Optimal search algorithm for a minimum
of a discrete periodic bimodal function 233--239
Peter Schorn A canonical simplifier for trigonometric
expressions in the kinematic equation 241--246
Füsun Özgüner and
C. Aykanat A reconfiguration algorithm for fault
tolerance in a hypercube multiprocessor 247--254
Marek Chrobak and
Richard Harter A note on random sampling . . . . . . . 255--256
William W. McCune Un-Skolemizing clause sets . . . . . . . 257--263
Micha Sharir The shortest watchtower and related
problems for polyhedral terrains . . . . 265--270
Alessandro d'Atri and
Marina Moscarini On hypergraph acyclicity and graph
chordality . . . . . . . . . . . . . . . 271--274
Pratul Dublish An $O(n^3)$ algorithm for finding the
minimal opaque forest of a convex
polygon . . . . . . . . . . . . . . . . 275--276
Mila E. Majster-Cederbaum On the uniqueness of fixed points of
endofunctors in a category of complete
metric spaces . . . . . . . . . . . . . 277--281
Bernard M. Waxman and
Makoto Imase Worst-case performance of
Rayward-Smith's Steiner tree heuristic 283--287
Stephan Olariu On the unimodality of convex polygons 289--292
Carroll Morgan Auxiliary variables in data refinement 293--296
Ir\`ene Guessarian and
Lutz Priese On the minimal number of $\times$
operators to model regularity in fair
SCCS . . . . . . . . . . . . . . . . . . 297--300
David Alex Lamb Benign side effects . . . . . . . . . . 301--305
Narayan Shankar and
Vijaya Ramachandran Efficient parallel circuits and
algorithms for division . . . . . . . . 307--313
Tetsuo Moriya Closure property of principal cones
under substitution . . . . . . . . . . . 315--317
Boris S. Veroy Average complexity of divide-and-conquer
algorithms . . . . . . . . . . . . . . . 319--326
Torben Hagerup On saving space in parallel computation 327--329
M. J. Foster and
Ronald I. Greenberg Lower bounds on the area of finite-state
machines . . . . . . . . . . . . . . . . 1--7
Jeffrey S. Salowe $L$-infinity interdistance selection by
parametric search . . . . . . . . . . . 9--14
Peter Roth A note on word chains and regular
languages . . . . . . . . . . . . . . . 15--18
Ph. Darondeau Bisimulation and effectiveness . . . . . 19--20
Ravinderpal Singh Sandhu The reflected tree hierarchy for
protection and sharing . . . . . . . . . 21--26
Andrzej Lingas and
Marek Karpi\'nski Subtree isomorphism is NC reducible to
bipartite perfect matching . . . . . . . 27--32
P. P. Chakrabarti and
S. Ghose and
A. Pandey and
S. C. De Sarkar Increasing search efficiency using
multiple heuristics . . . . . . . . . . 33--36
György Turán Lower bounds for synchronous circuits
and planar circuits . . . . . . . . . . 37--40
Zvi Galil and
Victor Pan Parallel evaluation of the determinant
and of the inverse of a matrix . . . . . 41--45
Mihály Geréb-Graus and
Ramamohan Paturi and
Endre Szemerédi There are no $p$-complete families of
symmetric Boolean functions . . . . . . 47--49
Eric C. R. Hehner Real-time programming . . . . . . . . . 51--56
Rudolf Fleischer Communication complexity of
multi-processor systems . . . . . . . . 57--65
Wing Shing Wong and
Robert J. T. Morris A new approach to choosing initial
points in local search . . . . . . . . . 67--72
June Hyoung Kim and
Kyu Ho Park and
Myunghwan Kim A model of distributed control:
dependency and uncertainty . . . . . . . 73--77
Charles Consel and
Olivier Danvy Partial evaluation of pattern matching
in strings . . . . . . . . . . . . . . . 79--86
R. Shonkwiler An image algorithm for computing the
Hausdorff distance efficiently in linear
time . . . . . . . . . . . . . . . . . . 87--89
Milena Mihail On coupling and the approximation of the
permanent . . . . . . . . . . . . . . . 91--95
Charles U. Martel and
Dan Gusfield A fast parallel quicksort algorithm . . 97--102
Peter Van Emde Boas Space measures for storage modification
machines . . . . . . . . . . . . . . . . 103--110
Toshiya Itoh and
Shigeo Tsujii An efficient algorithm for deciding
quadratic residuosity in finite fields
${\rm GF}(p^m)$ . . . . . . . . . . . . 111--114
Matti O. Jokinen Customizable garbage collectors . . . . 115--118
J. Scott Provan Shortest enclosing walks and cycles in
embedded graphs . . . . . . . . . . . . 119--125
O. Gerstel and
Y. Mansour and
S. Zaks Bit complexity of order statistics on a
distributed star network . . . . . . . . 127--132
José D. P. Rolim and
Sheila A. Greibach A note on the best-case complexity . . . 133--138
Udo Kelter The pitfall paradox and its solution
with virtual objects . . . . . . . . . . 139--143
Jorgen Staunstrup and
Jurg Nievergelt The behavior of shared objects:
concepts, pitfalls, and a new model . . 145--151
Karel Culik, II Variations of the firing squad problem
and applications . . . . . . . . . . . . 153--157
E. M. Ehlers and
S. H. von Solms Using random context structure grammars
to represent chemical structures . . . . 159--166
Christian Lavault Average number of messages for
distributed leader-finding in rings of
processors . . . . . . . . . . . . . . . 167--176
Houssine Chetto and
Maryline Chetto Scheduling periodic and sporadic tasks
in a real-time system . . . . . . . . . 177--184
James Wogulis Self-adjusting and split sequence hash
tables . . . . . . . . . . . . . . . . . 185--188
Kerry Raymond A distributed algorithm for multiple
entries to a critical section . . . . . 189--193
Friedemann Mattern Global quiescence detection based on
credit distribution and recovery . . . . 195--200
Ronald E. Barkley and
T. Paul Lee Point representation and hashing of an
interval . . . . . . . . . . . . . . . . 201--203
Alok Aggarwal and
Don Coppersmith and
Dan Kleitman A generalized model for understanding
evasiveness . . . . . . . . . . . . . . 205--208
J. M. Robson Separating strings with small automata 209--214
Joseph C. Culberson and
Piotr Rudnicki A fast algorithm for constructing trees
from distance matrices . . . . . . . . . 215--220
K. Vidyasankar An elegant $1$-writer multireader
multivalued atomic register . . . . . . 221--223
Wojciech Rytter and
Tomasz Szymacha Parallel algorithms for a class of
graphs generated recursively . . . . . . 225--231
Lud\vek Ku\vcera Graphs with small chromatic numbers are
easy to color . . . . . . . . . . . . . 233--236
Hock Thiam Ch'ng and
B. Srinivasan and
Beng Chin Ooi Study of self-organizing heuristics for
skewed access patterns . . . . . . . . . 237--244
Gyuyoun Song and
Donghyeon Park and
Dongmyun Lee and
Kyu Ho Park and
Myunghwan Kim A distributed deadlock detection
algorithm: distributed graph
reconstruction algorithm . . . . . . . . 245--252
Yechezkel Zalcstein and
Max Garzon An ${\rm NC}^2$ algorithm for testing
similarity of matrices . . . . . . . . . 253--254
Dan Gusfield and
Robert W. Irving Parametric stable marriage and minimum
cuts . . . . . . . . . . . . . . . . . . 255--259
Moshe Y. Vardi A note on the reduction of two-way
automata to one-way automata . . . . . . 261--264
Vijayan Rajan and
R. K. Ghosh and
P. Gupta An efficient parallel algorithm for
random sampling . . . . . . . . . . . . 265--268
Edward Omiecinski and
Eileen Tien A hash-based join algorithm for a
cube-connected parallel computer . . . . 269--275
J. L. Nazareth and
K. A. Ariyawansa On accelerating Newton's method based on
a conic model . . . . . . . . . . . . . 277--281
Aldo de Luca and
Stefano Varricchio Factorial languages whose growth
function is quadratically upper bounded 283--288
Greg Lindhorst and
Farhad Shahrokhi On renaming a set of clauses as a Horn
set . . . . . . . . . . . . . . . . . . 289--293
Oscar H. Ibarra and
Tao Jiang Optimal simulation of tree arrays by
linear arrays . . . . . . . . . . . . . 295--302
Carsten Vogt A new approach to optimal cache
scheduling . . . . . . . . . . . . . . . 303--310
V. Kotov Andrei P. Ershov (1931--1988) . . . . . 1--2
David Ginat and
Daniel D. Sleator and
Robert E. Tarjan A tight amortized bound for path
reversal . . . . . . . . . . . . . . . . 3--5
Tomihisa Kamada and
Satoru Kawai An algorithm for drawing general
undirected graphs . . . . . . . . . . . 7--15
Alok Aggarwal and
Dina Kravets A linear time algorithm for finding all
farthest neighbors in a convex polygon 17--20
Yves Robert and
Bernard Tourancheau and
Gilles Villard Data allocation strategies for the Gauss
and Jordan algorithms on a ring of
processors . . . . . . . . . . . . . . . 21--29
Richard I. Hartley Drawing polygons given angle sequences 31--33
Vijay Kumar Concurrency control on extendible
hashing . . . . . . . . . . . . . . . . 35--41
S. Olariu and
J. Randall Welsh-Powell opposition graphs . . . . . 43--46
Sheng Yu A pumping lemma for deterministic
context-free languages . . . . . . . . . 47--51
Hubert de Fraysseix and
Hiroshi Imai Notes on oriented depth-first search and
longest paths . . . . . . . . . . . . . 53--56
F. Luccio and
L. Pagli On the upper bound on the rotation
distance of binary trees . . . . . . . . 57--60
Chin-Wen W. Ho and
R. C. T. Lee Counting clique trees and computing
perfect elimination schemes in parallel 61--68
Rajamani Sundar Worst-case data structures for the
priority queue with attrition . . . . . 69--75
J. M. Basart and
L. Huguet An approximation algorithm for the TSP
(travelling salesman problem) . . . . . 77--81
M. V. Ramakrishna Analysis of random probing hashing . . . 83--90
F. Warren Burton A note on higher-order functions versus
logical variables . . . . . . . . . . . 91--95
Iain A. Stewart An algorithm for colouring perfect
planar graphs . . . . . . . . . . . . . 97--101
Wojciech Rytter A note on optimal parallel
transformations of regular expressions
to nondeterministic finite automata . . 103--109
D. B. Skillicorn and
D. T. Barnard Parallel parsing on the Connection
Machine . . . . . . . . . . . . . . . . 111--117
Satoshi Matsuoka and
Tomihisa Kamada and
Satoru Kawai Asymptotic evaluation of window
visibility . . . . . . . . . . . . . . . 119--126
G. Tel and
F. Mattern Comments on ``Ring based termination
detection algorithm for distributed
computations'' [Inform. Process. Lett.
\bf 29(3), 26 October 1988, pp.
149--153] . . . . . . . . . . . . . . . 127--128
Wei Kuan Shih and
Wen-Lian Hsu An $O(n \log n + m \log \log n)$ maximum
weight clique algorithm for circular-arc
graphs . . . . . . . . . . . . . . . . . 129--134
Hans L. Bodlaender Achromatic number is NP-complete for
cographs and interval graphs . . . . . . 135--138
John N. Tsitsiklis On the use of random numbers in
asynchronous simulation via rollback . . 139--144
Joseph Y.-T. Leung Bin packing with restricted piece sizes 145--149
Patrick Lentfert and
Mark H. Overmars Data structures in a real-time
environment . . . . . . . . . . . . . . 151--155
J. Cheriyan and
S. N. Maheshwari The parallel complexity of finding a
blocking flow in a $3$-layer network . . 157--161
Martin Beaudry Characterization of idempotent
transformation monoids . . . . . . . . . 163--166
Angelo Gregori Unit-length embedding of binary trees on
a square grid . . . . . . . . . . . . . 167--173
Xiaolin Wu Fast approximations to discrete optimal
quantization . . . . . . . . . . . . . . 175--179
Bogdan S. Chlebus Parallel iterated bucket sort . . . . . 181--183
Vishv Mohan Malhotra and
Tang Van To and
Kanchana Kanchanasut An improved data-dependency-based
backtracking scheme for Prolog . . . . . 185--189
Sally A. Goldman A space efficient greedy triangulation
algorithm . . . . . . . . . . . . . . . 191--196
Anujan Varma Fault-tolerant routing in unique-path
multistage interconnection networks . . 197--201
Friedemann Mattern An efficient distributed termination
test . . . . . . . . . . . . . . . . . . 203--208
Scott D. Carson and
Paul Vongsathorn Error bounds on disk arrangement using
frequency information . . . . . . . . . 209--213
Dorit S. Hochbaum and
Ron Shamir An $O(n\,\log ^2n)$ algorithm for the
maximum weighted tardiness problem . . . 215--219
Prakash Ramanan Average-case analysis of the smart next
fit algorithm . . . . . . . . . . . . . 221--225
R. Casas and
J. Diaz and
J. M. Steyaert Average-case analysis of Robinson's
unification algorithm with two different
variables . . . . . . . . . . . . . . . 227--232
Manuel E. Bermudez and
George Logothetis Simple computation of LALR(1) lookahead
sets . . . . . . . . . . . . . . . . . . 233--238
Tom Head Deciding the immutability of regular
codes and languages under finite
transductions . . . . . . . . . . . . . 239--241
Stephan Olariu A simple linear-time algorithm for
computing the RNG and MST of unimodal
polygons . . . . . . . . . . . . . . . . 243--247
Samir Khuller On computing graph closures . . . . . . 249--255
Ellen B. Feinberg Characterizing the shortest path of an
object among obstacles . . . . . . . . . 257--264
Andrew V. Goldberg and
Robert E. Tarjan A parallel algorithm for finding a
blocking flow in an acyclic network . . 265--271
Bernd-Jürgen J. Falkowski A self-optimizing Prolog program and the
underlying statistical model . . . . . . 273--276
Gunnar Stålmarck A note on the computational complexity
of the pure classical implication
calculus . . . . . . . . . . . . . . . . 277--278
Hiroshi Nagamochi and
Toshihide Ibaraki On max-flow min-cut and integral flow
properties for multicommodity flows in
directed networks . . . . . . . . . . . 279--285
Dean P. Foster and
Rakesh V. Vohra Probabilistic analysis of a heuristics
for the dual bin packing problem . . . . 287--290
Serge Yoccoz Recursive $\omega$-rule for proof
systems . . . . . . . . . . . . . . . . 291--294
Ravi Mukkamala Some properties of view-based
replication control algorithms for
distributed systems . . . . . . . . . . 295--298
Paola Bertolazzi and
Antonio Sassano A decomposition strategy for the vertex
cover problem . . . . . . . . . . . . . 299--304
Ludwik Czaja Finite processes in cause-effect
structures and their composition . . . . 305--310
Alok Aggarwal and
Michael Hawrylycz On computing the closest boundary point
on the convex hull . . . . . . . . . . . 311--314
Svante Carlsson and
Jingsen Chen and
Thomas Strothotte A note on the construction of the data
structure ``deap'' . . . . . . . . . . . 315--317
Peter A. Bloniarz and
S. S. Ravi An $\Omega (n \log n)$ lower bound for
decomposing a set of points into chains 319--322
Norbert Eisinger A note on the completeness of resolution
without self-resolution . . . . . . . . 323--326
Lloyd Allison Direct semantics and exceptions define
jumps and coroutines . . . . . . . . . . 327--330
Peter Damaschke The Hamiltonian circuit problem for
circle graphs is NP-complete . . . . . . 1--2
Dilip Sarkar and
Ivan Stojmenovi\'c An optimal parallel circle-cover
algorithm . . . . . . . . . . . . . . . 3--6
Neil Gunther Path integral methods for computer
performance analysis . . . . . . . . . . 7--13
Ji\vrí Matou\vsek On-line computation of convolutions . . 15--16
A. P. Sistla On verifying that a concurrent program
satisfies a nondeterministic
specification . . . . . . . . . . . . . 17--23
Kazuo Iwano An improvement of Goldberg, Plotkin and
Vaidya's maximal node-disjoint paths
algorithm . . . . . . . . . . . . . . . 25--27
Joachim Biskup Boyce-Codd normal form and object normal
forms . . . . . . . . . . . . . . . . . 29--33
Torben Hagerup Hybridsort revisited and parallelized 35--39
Andreas Blass and
Yuri Gurevich On Matijasevitch's nontraditional
approach to search problems . . . . . . 41--45
Errol L. Lloyd A fast algorithm for finding
interlocking sets . . . . . . . . . . . 47--50
Hwang Kyu Choi and
Myunghwan Kim Hybrid join: an improved sort-based join
algorithm . . . . . . . . . . . . . . . 51--56
Laurence Boxer and
Russ Miller A parallel circle-cover minimization
algorithm . . . . . . . . . . . . . . . 57--60
Maw-Sheng S. Chern and
G. H. Chen and
Pangfeng Liu An LC branch-and-bound algorithm for the
module assignment problem . . . . . . . 61--71
Young Joo Kim and
Gil Chang Kim Coordinator: a modification to the
monitor concept . . . . . . . . . . . . 73--80
Dror G. Feitelson and
Larry Rudolph Implementation of a wait-free
synchronization primitive that solves
$n$-process consensus . . . . . . . . . 81--83
D. A. Wolfram Forward checking and intelligent
backtracking . . . . . . . . . . . . . . 85--87
Y. C. Chen and
Z. C. Yeh and
G. H. Chen Using fewer processors to reduce time
complexities of semigroup computations 89--93
Chi Sung Laih and
Jau Yien Lee and
Lein Harn A new threshold scheme and its
application in designing the conference
key distribution cryptosystem . . . . . 95--99
Adam Janiak Minimization of resource consumption
under a given deadline in the
two-processor flow-shop scheduling
problem . . . . . . . . . . . . . . . . 101--112
Shing-Tsaan Huang Termination detection by using
distributed snapshots . . . . . . . . . 113--119
Martin Kochol Efficient monotone circuits for
threshold functions . . . . . . . . . . 121--122
Steven S. Skiena Reconstructing graphs from cut-set sizes 123--127
A. Goscinski A synchronization algorithm for
processes with dynamic priorities in
computer networks with node failures . . 129--136
Stephen Richardson and
Mahadevan Ganapathi Interprocedural analysis vs. procedure
integration . . . . . . . . . . . . . . 137--142
Paul Cull and
James L. Holloway Computing Fibonacci numbers quickly . . 143--149
G. Sagar and
Anil K. Sarje and
Kamal U. Ahmed On module assignment in two-processor
distributed systems: A modified
algorithm . . . . . . . . . . . . . . . 151--153
Joseph M. Morris Well-founded induction and the
invariance theorem for loops . . . . . . 155--158
Mikhail J. Atallah and
Danny Z. Chen An optimal parallel algorithm for the
minimum circle-cover problem . . . . . . 159--165
Giri N. Narasimhan A note on the Hamiltonian circuit
problem on directed path graphs . . . . 167--170
Marshall Bern and
Paul Plassmann The Steiner problem with edge lengths
$1$ and $2$ . . . . . . . . . . . . . . 171--176
Gérard Ligozat and
Hél\`ene Bestougeff On relations between intervals . . . . . 177--182
Mohan B. Sharma and
Sitharama S. Iyengar and
Narasimha K. Mandyam An efficient distributed
depth-first-search algorithm . . . . . . 183--186
Micha Sharir A note on the Papadimitriou-Silverberg
algorithm for planning optimal
piecewise-linear motion of a ladder . . 187--190
Andrzej Lingas Vorono\uì diagrams with barriers and the
shortest diagonal problem . . . . . . . 191--198
John A. Ellis and
Manrique Mata and
Gary MacGillivray A linear time algorithm for longest $(s,
t)$-paths in weighted outerplanar graphs 199--204
Ömer E\ugecio\uglu and
Bahman Kalantari Approximating the diameter of a set of
points in the Euclidean space . . . . . 205--211
Ravinderpal Singh Sandhu The demand operation in the schematic
protection model . . . . . . . . . . . . 213--219
Jan van den Bos PROCOL: A protocol-constrained
concurrent object-oriented language . . 221--227
R. Kemp A one-to-one correspondence between two
classes of ordered trees . . . . . . . . 229--234
Nissim Francez Cooperating proofs for distributed
programs with multiparty interactions 235--242
H. Everett and
A. Gupta Acyclic directed hypercubes may have
exponential diameter . . . . . . . . . . 243--245
Grant A. Cheston and
Art Farley and
S. T. Hedetniemi and
Andrzej Proskurowski Centering a spanning tree of a
biconnected graph . . . . . . . . . . . 247--250
David A. Mix Barrington and
James Corbett On the relative complexity of some
languages in ${\rm NC}^1$ . . . . . . . 251--256
A. Clouatre and
N. Laliberte and
T. H. Merrett A general implementation of relational
recursion with speedup techniques for
programmers . . . . . . . . . . . . . . 257--262
George H. Roberts Another note on recursive ascent . . . . 263--266
Gerd Baron and
Friedrich Urbanek Factorial languages with quadratically
upper bounded growth functions and
nonlinearly upper bounded subword
complexities . . . . . . . . . . . . . . 267--269
Erkki Mäkinen On the subtree isomorphism problem for
ordered trees . . . . . . . . . . . . . 271--273
P. P. Chakrabarti and
S. Ghose and
A. Pandey and
S. C. de Sarkar Increasing search efficiency using
multiple heuristics . . . . . . . . . . 275--275
Shuji Shiraishi A parallel algorithm for the maximum
$2$-chain edge packing problem . . . . . 277--279
Serge Abiteboul Boundedness is undecidable for Datalog
programs with a single recursive rule 281--287
Henk Alblas Optimal incremental simple multi-pass
attribute evaluation . . . . . . . . . . 289--295
Manfred Padberg and
Antonio Sassano The complexity of matching with bonds 297--300
Robert L. Drysdale, III and
Jerzy W. Jaromczyk A note on lower bounds for the maximum
area and maximum perimeter $k$-gon
problems . . . . . . . . . . . . . . . . 301--303
A. M. Gibbons and
Y. N. Srikant A class of problems efficiently solvable
on mesh-connected computers including
dynamic expression evaluation . . . . . 305--311
Robert Demolombe and
Arantza Illarramendi Heuristics for syntactical optimization
of relational queries . . . . . . . . . 313--316
Serge Abiteboul and
Marc Gyssens and
Dirk van Gucht An alternative way to represent the
cogroup of a relation in the context of
nested databases . . . . . . . . . . . . 317--324
Yoshihito Toyama Fast Knuth--Bendix completion with a
term rewriting system compiler . . . . . 325--328
Boris S. Veroy Corrigenda: ``Average complexity of
divide-and-conquer algorithms'' [Inform.
Process. Lett. \bf 29 (1988), no. 6,
319--326; MR 89m:68068] . . . . . . . . 329--329
Boris S. Veroy Corrigenda: ``Optimal search algorithm
for a minimum of a discrete periodic
bimodal function'' [Inform. Process.
Lett. \bf 29 (1988), no. 5, 233--239; MR
90b:90099] . . . . . . . . . . . . . . . 329--329
Z. Fülöp and
S. Vágvölgyi Top-down tree transducers with
deterministic top-down look-ahead . . . 3--5
S. J. Wan and
S. K. M. Wong An adaptive algorithm for finding a
covering hypersphere . . . . . . . . . . 7--10
De-Lei Lee On access and alignment of data in a
parallel processor . . . . . . . . . . . 11--14
Mila E. Majster-Cederbaum The contraction property is sufficient
to guarantee the uniqueness of fixed
points of endofunctors in a category of
complete metric spaces . . . . . . . . . 15--19
Jayadev Misra A simple proof of a simple consensus
algorithm . . . . . . . . . . . . . . . 21--24
Gadi Taubenfeld Leader election in the presence of $n-1$
initial failures . . . . . . . . . . . . 25--28
A. Srinivasa Rao and
C. Pandu Rangan Linear algorithm for domatic number
problem on interval graphs . . . . . . . 29--33
Bhaskar Dasgupta and
C. E. Veni Madhavan An approximate algorithm for the minimal
vertex nested polygon problem . . . . . 35--44
Kam-Fai Wong Comments on ``A comparison of
concatenated and superimposed code word
surrogate files for very large
data/knowledge bases'' . . . . . . . . . 45--52
Michel Raynal Prime numbers as a tool to design
distributed algorithms . . . . . . . . . 53--58
D. Avis and
J. M. Robert and
R. Wenger Lower bounds for line stabbing . . . . . 59--62
Christian Buchta On the average number of maxima in a set
of vectors . . . . . . . . . . . . . . . 63--65
Kuo Liang Chung and
Wen Chin Chen and
Ferng-Ching Lin Fast computation of periodic continued
fractions . . . . . . . . . . . . . . . 67--72
Andrzej Szepietowski Some remarks on the alternating
hierarchy and closure under complement
for sublogarithmic space . . . . . . . . 73--78
Winfried Thome and
Reinhard Wilhelm Simulating circular attribute grammars
through attribute reevaluation . . . . . 79--81
Martin Dietzfelbinger The speed of copying on one-tape
off-line Turing machines . . . . . . . . 83--89
Alejandro A. Schäffer Optimal node ranking of trees in linear
time . . . . . . . . . . . . . . . . . . 91--96
Stefano Ceri and
Georg Gottlob and
Letizia Tanca and
Gio Wiederhold Magic semi-joins . . . . . . . . . . . . 97--107
Andrzej Szepietowski Some notes on strong and weak $\log \log
n$ space complexity . . . . . . . . . . 109--112
R. Grossi and
F. Luccio Simple and efficient string matching
with $k$ mismatches . . . . . . . . . . 113--120
Takayoshi Shoudai The lexicographically first topological
order problem is NLOG-complete . . . . . 121--124
Lanfranco Lopriore Software-controlled cache coherence
protocol for multicache systems . . . . 125--130
E. Robert McCurley Auxiliary variables in partial
correctness programming logics . . . . . 131--133
Selim G. Akl and
David Gries and
Ivan Stojmenovíc An optimal parallel algorithm for
generating combinations . . . . . . . . 135--139
Ronald V. Book and
Shou Wen Tang A note on sparse sets and the
polynomial-time hierarchy . . . . . . . 141--143
Ravi B. Boppana The average-case parallel complexity of
sorting . . . . . . . . . . . . . . . . 145--146
A. Srinivasa Rao and
C. Pandu Rangan Optimal parallel algorithms on
circular-arc graphs . . . . . . . . . . 147--156
Bruce Parker and
Ian Parberry Constructing sorting networks from
$k$-sorters . . . . . . . . . . . . . . 157--162
Rudolf Berghammer and
Günther Schmidt and
Hans Zierer Symmetric quotients and domain
constructions . . . . . . . . . . . . . 163--168
John Hershberger Finding the upper envelope of $n$ line
segments in ${O}(n \log n)$ time . . . . 169--174
D. T. Lee and
F. P. Preparata Parallel batched planar point location
on the CCC . . . . . . . . . . . . . . . 175--179
Torben Hagerup and
Christine Rüb Optimal Merging and Sorting on the EREW
PRAM . . . . . . . . . . . . . . . . . . 181--185
Christos Levcopoulos and
Ola Petersson A note on adaptive parallel sorting . . 187--191
Egon Wanke and
Manfred Wiegers Undecidability of the bandwidth problem
on linear graph languages . . . . . . . 193--197
José D. P. Rolim On the polynomial IO-complexity . . . . 199--204
Jayaramaiah Boreddy and
R. N. Mukherjee An algorithm to find polygon similarity 205--206
Richard Zippel An explicit separation of relativised
random polynomial time and relativised
deterministic polynomial time . . . . . 207--212
J. Zerovnik A randomised heuristical algorithm for
estimating the chromatic number of a
graph . . . . . . . . . . . . . . . . . 213--219
P. E. Dunne Comment on Kochol's paper ``Efficient
monotone circuits for threshold
functions'' [Inform. Process. Lett. \bf
32(3), 24 August 1989, pp. 121--122] . . 221--222
A. J. M. Van Gasteren and
G. Tel Comments on ``On the proof of a
distributed algorithm'': always-true is
not invariant [Inform. Process. Lett.
\bf 25(3), 29 May 1987, pp. 145--147] 277--279
Rolf Floren A note on: ``A faster approximation
algorithm for the Steiner problem in
graphs'' [Inform. Process. Lett. \bf 27
(1988), no. 3, 125--128; MR 89d:68031]
by K. Mehlhorn . . . . . . . . . . . . . 177--178
Jimmi S. Pettersson Letter to the Editor: Comments on
``Always-true is not invariant'':
Assertional reasoning about invariance
[Inform. Process. Lett. \bf 35(6), 15
September 1990, pp. 277--279] . . . . . 231--233
Roberto Grossi Further comments on the subtree
isomorphism for ordered trees: ``On the
subtree isomorphism problem for ordered
trees'' [Inform. Process. Lett. \bf 32
(1989), no. 5, 271--273; MR 90k:68139]
by E. Mäkinen . . . . . . . . . . . . . . 255--256
R. Satyanarayanan and
D. R. Muthukrishnan A note on Raymond's tree based algorithm
for distributed mutual exclusion . . . . 249--255
George Steiner and
Scott Yeomans A note on: ``Scheduling unit-time tasks
with integer release times and
deadlines'' [Inform. Process. Lett. \bf
16 (1983), no. 4, 171--173; MR
84m:68030] by G. Frederickson . . . . . 165--166