Information Processing Letters, Volume 20

Volume 20, Number 1, 2 January 1985

Christine Duboc: Some Properties of Commutation in Free Partially Commutative Monoids. 1-4
Ronald V. Book, Friedrich Otto: Cancellation Rules and Extended Word Problems. 5-11
Andranik Mirzaian, Eshrat Arjomandi: Selection in X+Y and Matrices With Sorted Rows and Columns. 13-17
Erkki Mäkinen: A Note on Undercover Relation. 19-21
Geoff P. McKeown: A Special Purpose MIMD Parallel Processor. 23-27
S. Upendra Rao, Arun K. Majumdar: An Algorithm for Local Compaction of Horizontal Microprograms. 29-33
Solomon Passy, Tinko Tinchev: PDL with Data Constants. 35-41
Silvio Romero de 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

Gianfranco Bilardi, Franco 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
Peter Widmayer, C. K. Wong: An Optimal Algorithm for the Maximum Alignment of Terminals. 75-82
Satish R. Thatte: On the Correspondence Metween Two Classes of Reduction Systems. 83-85
David Harel, David Peleg: More on Looping vs. Repeating in Dynamic Logic. 87-90
Andrejs J. Auzins, Efim B. Kinber: On Separation of the Emptiness and Equivalence Problems for Program Schemes. 91-93
Danièle Beauquier, Dominique Perrin: Codeterministic Automata on Infinite Words. 95-98
Esko Ukkonen: Upper Bounds on the Size of 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 , Erratum: Information Processing Letters 21(2): 107 (1985)
Elena Lodi, Fabrizio Luccio: Split Sequence Hash Search. 131-136
Richard Cole, Chee-Keng Yap: A Parallel Median Algorithm. 137-139
Erkki Mäkinen: An Undecidable Problem for Context-Free Grammars. 141-142
Yung H. 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, 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, Costas 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²) Time. 167-171
Mathai Joseph: On a Problem in Real-Time Computing. 173-177
Nicola Santoro, Jeffrey B. Sidney: Interpolation-Binary Search. 179-181
K. Rangarajan, 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

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