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 BibTeX
Ronald V. Book, Friedrich Otto: Cancellation Rules and Extended Word Problems. 5-11 BibTeX
Andranik Mirzaian, Eshrat Arjomandi: Selection in X+Y and Matrices With Sorted Rows and Columns. 13-17 BibTeX
Erkki Mäkinen: A Note on Undercover Relation. 19-21 BibTeX
Geoff P. McKeown: A Special Purpose MIMD Parallel Processor. 23-27 BibTeX
S. Upendra Rao, Arun K. Majumdar: An Algorithm for Local Compaction of Horizontal Microprograms. 29-33 BibTeX
Solomon Passy, Tinko Tinchev: PDL with Data Constants. 35-41 BibTeX
Silvio Romero de Lemos Meira: A Linear Applicative Solution for the Set Union Problem. 43-45 BibTeX
Adam C. Bounas: Direct Determination of a `Seed' Binary Matrix. 47-50 BibTeX
Sushil Jajodia: On Equivalence of Relational and Network Database Models. 51-54 BibTeX

Gianfranco Bilardi, Franco P. Preparata: The VLSI Optimality of the AKS Sorting Network. 55-59 BibTeX
David A. Plaisted: The Undecidability of Self-Embedding for Term Rewriting Systems. 61-64 BibTeX
Jan L. A. van de Snepscheut: Evaluating Expressions with a Queue. 65-66 BibTeX
John McLean: A Comment on the `Basic Security Theorem' of Bell and LaPadula. 67-70 BibTeX
Kohei Noshita: Translation of Turner Combinators in O(n log n) Space. 71-74 BibTeX
Peter Widmayer, C. K. Wong: An Optimal Algorithm for the Maximum Alignment of Terminals. 75-82 BibTeX
Satish R. Thatte: On the Correspondence Metween Two Classes of Reduction Systems. 83-85 BibTeX
David Harel, David Peleg: More on Looping vs. Repeating in Dynamic Logic. 87-90 BibTeX
Andrejs J. Auzins, Efim B. Kinber: On Separation of the Emptiness and Equivalence Problems for Program Schemes. 91-93 BibTeX
Danièle Beauquier, Dominique Perrin: Codeterministic Automata on Infinite Words. 95-98 BibTeX
Esko Ukkonen: Upper Bounds on the Size of LR(k) Parsers. 99-103 BibTeX
Michael G. Main: An Infinite Square-Free co-CFL. 105-107 BibTeX
Subhash C. Kak: How to Detect Tampering of Data. 109-110 BibTeX

Ernest C. Njau: Details of Distortions in the Computed Fourier Transforms of Signals - Part I: Short Periodic Signals. 111-113 BibTeX
Eduardo D. Sontag: Real Addition and the Polynomial Hierarchy. 115-120 BibTeX
Mee Yee Chan: A Note on Redundant Disk Modulo Allocation. 121-123 BibTeX
Alain J. Martin: The Probe: An Addition to Communication Primitives. 125-130 BibTeX , Erratum: Information Processing Letters 21(2): 107 (1985)
Elena Lodi, Fabrizio Luccio: Split Sequence Hash Search. 131-136 BibTeX
Richard Cole, Chee-Keng Yap: A Parallel Median Algorithm. 137-139 BibTeX
Erkki Mäkinen: An Undecidable Problem for Context-Free Grammars. 141-142 BibTeX
Yung H. Tsin: An Optimal Parallel Processor Bound in Strong Orientation of an Undirected Graph. 143-146 BibTeX
Baruch Awerbuch: A New Distributed Depth-First-Search Algorithm. 147-150 BibTeX
Jeffrey Shallit, Adi Shamir: Number-Theoretic Functions Which Are Equivalent to Number of Divisors. 151-153 BibTeX
Hugo Volger: Some Results on Addition/Subtraction Chains. 155-160 BibTeX
W. M. Beynon, Costas S. Iliopoulos: Computing a Basis for a Finite Abelian p-Group. 161-163 BibTeX

Emo Welzl: Constructing the Visibility Graph for n-Line Segments in O(n²) Time. 167-171 BibTeX
Mathai Joseph: On a Problem in Real-Time Computing. 173-177 BibTeX
Nicola Santoro, Jeffrey B. Sidney: Interpolation-Binary Search. 179-181 BibTeX
K. Rangarajan, S. Arun-Kumar: Fair Derivations in E0L Systems. 183-188 BibTeX
Carroll Morgan: Global and Logical Time in Distributed Algorithms. 189-194 BibTeX
David S. Wise: Representing Matrices as Quadtrees for Parallel Processors. 195-199 BibTeX
J. Mark Keil: Finding Hamiltonian Circuits in Interval Graphs. 201-206 BibTeX
W. J. Van Gils: How to Cope with Faulty Processors in a Completely Connected Network of Communicating Processors. 207-213 BibTeX
Costas S. Iliopoulos: Analysis of Algorithms on Problems in General Abelian Groups. 215-220 BibTeX

Maciej Slusarek: A Note on the Dynamic Storage Allocation Problem. 223-227 BibTeX
John H. Reif: Depth-First Search is Inherently Sequential. 229-234 BibTeX
Uzi Vishkin: On Efficient Parallel Strong Orientation. 235-240 BibTeX
Juris Hartmanis: Independence Results About Context-Free Languages and Lower Bounds. 241-248 BibTeX
James R. Bitner: Storing Matrices on Disk for Efficient Row and Column Retrieval. 249-254 BibTeX
Luc Devroye: A Note on the Expected Time Required to Construct the Outer Layer. 255-257 BibTeX
Christos H. Papadimitriou: An Algorithm for Shortest-Path Motion in Three Dimensions. 259-263 BibTeX