Information Processing Letters, Vol. 4

Volume 4, Number 1, September 1975

Giorgio Germano, Andrea Maggiolo-Schettini: Sequence-to-Sequence Recursiveness. 1-6
Keijo Ruohonen: Three Results of Comparison Between L Languages with and without Interaction. 7-10
Martti Penttonen: ET0L-Grammars and N-Grammars. 11-13
Juhani Nieminen: On Homomorphic Images of Transition Graphs. 14-15
Juhani Nieminen: Some Observations on the Determination of an Upper Bound for the Clique Number of a Graph. 16-17
Andy N. C. Kang, David A. Ault: Some Properties of a Centroid of a Free Tree. 18-20
Andrew Chi-Chih Yao: An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees. 21-23
Jayadev Misra, Robert Endre Tarjan: Optimal Chain Partitions of Trees. 24-26

Andrzej Rowicki: A Note on Optimal Scheduling for Two-Processor Systems. 27-30
Stanislaw Jarzabek, Tomasz Krawczyk: LL-Regular Grammars. 31-37
Michael R. Levy: Complete Operator Precedence. 38-40
Ernest J. Cockayne, S. E. Goodman, Stephen T. Hedetniemi: A Linear Algorithm for the Domination Number of a Tree. 41-44
Laurent Hyafil, Jean-Paul Van de Wiele: On the Additive Complexity of Specific Polynomials. 45-47
R. S. Anderssen, A. J. Guttmann: A Rationale for the Numerical Differentiation of Experimental Data. 48-50
Andrew A. Sekey: A Generating Function for Entropy. 51

Donald B. Johnson: Priority Queues with Update and Finding Minimum Spanning Trees. 53-57
Doron Rotem: On a Correspondence Between Binary Trees and a Certain Type of Permutation. 58-61
Douglas W. Clark: A Fast Algorithm for Copying Binary Trees. 62-63
J. Banerjee, V. Rajaraman: A Dual Link Data Structure for Random File Organization. 64-69
Arthur G. Duncan, Lawrence Yelowitz: Loop Unravelling: A Practical Tool in Proving Program Correctness. 70-72
R. Christensen: Crossvalidation: Minimizing the Entropy of the Future. 73-76
Judea Pearl: On the Complexity of Inexact Computations. 77-81

Harry G. Barrow, Rod M. Burstall: Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques. 83-84
Zvi Galil: Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms. 85-87
Leslie Lamport: Comments on "A Synchronization Anomaly". 88-89
Russell L. Wessner: Optimal Alphabetic Search Trees With Restricted Maximal Height. 90-94
Tomás Lang, Eduardo B. Fernández: Scheduling of Unit-Length Independent Tasks with Execution Constraints. 95-98
M. S. Krishnamurthy, H. R. Ramesha Chandra: A Note on Precedence Functions. 99-100
Hans-Dieter Ehrich, Witold Lipski Jr.: On the Storage Space Requirement of Consecutive Retrieval with Redundancy. 101-104
Stefan Feyock: Noiselike Transforms of omega-Events. 105-108
David R. Hanson: A Simple Variant of the Boundary-Tag Algorithm for the Allocation of Coroutine Environments. 109-112

Stanislaw Chrobot: Layer - A Language Construction for Concurrent Structure Program Design. 113-117
Jim Cunningham, M. E. J. Gilford: A Note on the Semantic Definition of Side Effects. 118-120
Wolfgang Coy: The Logical Meaning of Programs of a Subrecursive Language. 121-126
Grzegorz Rozenberg: On Slicing of K-Iteration Grammars. 127-131
Jon Louis Bentley, Walter A. Burkhard: Heuristics for Partial-Match Retrieval Data Base Design. 132-135
S. De Wolf, G. De Mey: Numerical Solution of Integral Equations for Potential Problems by a Variational Principle. 136-139

Paul Pritchard: A Proof Rule for Multiple Coroutine Systems. 141-143
Peter J. A. Reusch: Generalized Lattices Applicable in Retrieval Models. 144-148
David P. Dobkin, Jan van Leeuwen: The Complexity of Vector-Products. 149-154
Gideon Yuval: An Algorithm for Finding All Shortest Paths Using N^(2.81) Infinite-Precision Multiplications. 155-156
Joost Engelfriet, Sven Skyum: Copying Theorems. 157-161
Grzegorz Rozenberg, Derick Wood: A Note on K-Iteration Grammars. 162-164
Roman Krzemien, Andrzej Lukasiewicz: Automatic Generation of Lexical Analyzers in a Compiler-Compiler. 165-168