Information Processing Letters, Volume 9

Volume 9, Number 1, 20 July 1979

Hamish I. E. Gunn, Ronald Morrison: On the Implementation of Constants. 1-4 BibTeX
Paulo A. S. Veloso: Characterizing the Regular Prefix Codes and Right Power-Bounded Languages. 5-7 BibTeX
John C. Cherniavsky, John Keohane, Peter B. Henderson: A Note Concerning Top Down Program Development and Restricted Exit Control Structures. 8-12 BibTeX
Daniel M. Berry, Richard L. Schwartz: United and Discriminated Record Types in Strongly Typed Languages. 13-18 BibTeX
Patricia J. Eberlein: A Note on Medium Selection and Spider Production. 19-22 BibTeX
Alex Bykat: On Polygon Similarity. 23-25 BibTeX
H. B. M. Jonkers: A Fast Garbage Compaction Algorithm. 26-30 BibTeX
Glenn K. Manacher, Albert L. Zobrist: Neither the Greedy Nor the Delaunay Triangulation of a Planar Point Set Approximates the Optimal Triangulation. 31-34 BibTeX
Richard A. DeMillo, Raymond E. Miller: Implicit Computation of Synchronization Primitives. 35-38 BibTeX
Marek J. Lao: A New Data Structure for the UNION-FIND Problem. 39-45 BibTeX
Dario Bini, Milvio Capovani: Lower Bounds of the Complexity of Linear Algebras. 46-47 BibTeX
Andrew Chi-Chih Yao: A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases. 48-50 BibTeX
Anton Nijholt: From Left-Regular to Greibach Normal Form Grammars. 51-55 BibTeX

Mark R. Brown: Some Observations on Random 2-3 Trees. 57-59 BibTeX
Jan Grabowski: The Unsolvability of Some Petri Net Language Problems. 60-63 BibTeX
F. N. Teskey: Document Retrieval Using Associative Processors. 64-67 BibTeX
F. Frances Yao: Graph 2-Isomorphism is NP-Complete. 68-72 BibTeX
Akihiro Nozaki: A Note on the Complexity of Approximative Evaluation of Polynomials. 73-75 BibTeX
Richard L. Schwartz: Aliasing Among Pointers in EUCLID. 76-79 BibTeX
W. S. Luk: `Possible' Membership of a Multivalued Dependency in a Relational Database. 80-83 BibTeX
Andrzej Ehrenfeucht, Grzegorz Rozenberg: An Observation on Scattered Grammars. 84-85 BibTeX
Andrzej Ehrenfeucht, Grzegorz Rozenberg: Finding a Homomorphism Between Two Words is NP-Complete. 86-88 BibTeX
B. Srinivasan, V. Rajaraman: On the Normalization of Relational Databases. 89-92 BibTeX
Abhijit Sengupta, Subir Bandyopadhyay, Pradip K. Srimani: On Identification of CR Property in File Organisation. 93-96 BibTeX
John Grant: Partial Values in a Tabular Database Model. 97-99 BibTeX
Boguslaw L. Jackowski, Ryszard Kubiak, Stefan Sokolowski: Complexity of Sorting by Distributive Partitioning. 100 BibTeX

Eike Best: A Note on the Proof of a Concurrent Program. 103-104 BibTeX
Alain Fournier, Zvi M. Kedem: Comments on the All Nearest-Neighbor Problem for Convex Polygons. 105-107 BibTeX
Charles J. Colbourn: The Complexity of Symmetrizing Matrices. 108-109 BibTeX
Sandra L. Mitchell, Stephen T. Hedetniemi: Linear Algorithms for Edge-Coloring Trees and Unicyclic Graphs. 110-112 BibTeX
R. K. Arora, S. P. Rana: On Module Assignment in Two-Processor Distributed Systems. 113-117 BibTeX
Alon Itai: A Randomized Algorithm for Checking Equivalence of Circular Lists. 118-121 BibTeX
M. Howard Williams, A. R. Bulmer: A Transportable Code Generator System. 122-125 BibTeX
Marco Ferrari, Giovanni Guida: DB: A LISP-Type Data Base System. 126-134 BibTeX
Amiram Yehudai: A Note on the Pumping Lemma for Regular Languages. 135-136 BibTeX
Kozo Itano: Reduction of Page Swaps on the Two Dimensional Transforms in a Paging Environment. 137-140 BibTeX
Ferenc Dévai, Tibor Szendrényi: Comments on Convex Hull of a Finite Set of Points in Two Dimensions. 141-142 BibTeX
Gianfranco Prini: Stack Implementation of Shallow Binding in Languages with Mixed Scoping. 143-154 BibTeX
Hans Langmaack, Wolfram-Manfred Lippe, Franz Wagner: The Formal Termination Problem for Programs with Finite ALGOL 68-Modes. 155-159 BibTeX

Wm. Randolph Franklin: Padded Lists: Set Operations in Expected Theta(log log N) Time. 161-166 BibTeX
Joseph Y.-T. Leung: Bounds on List Scheduling of UET Tasks with Restricted Resource Constraints. 167-170 BibTeX
Ernest J. Cockayne, Frank Ruskey, A. G. Thomason: An Algorithm for the Most Economic Link Addition in a Tree Communication Network. 171-175 BibTeX
J. Strother Moore: A Mechanical Proof of the Termination of Takeuchi's Function. 176-181 BibTeX
Alkiviadis G. Akritas: On the Solution of Polynomial Equations Using Continued Fractions. 182-184 BibTeX
K. Mani Chandy, Jayadev Misra: Deadlock Absence Proofs for Networks of Communicating Processes. 185-189 BibTeX
D. T. Lee, C. C. Yang: Location of Multiple Points in a Planar Subdivision. 190-193 BibTeX

Jayme Luiz Szwarcfiter: Systems of Distinct Representatives for k Families of Sets. 195-196 BibTeX
Joseph M. Morris: Traversing Binary Trees Simply and Cheaply. 197-200 BibTeX
Duncan McCallum, David Avis: A Linear Algorithm for Finding the Convex Hull of a Simple Polygon. 201-206 BibTeX
G. Oulsnam: Cyclomatic Numbers Do Not Measure Complexity of Unstructured Programs. 207-211 BibTeX
Nachum Dershowitz: A Note on Simplification Orderings. 212-215 BibTeX
A. M. Andrew: Another Efficient Algorithm for Convex Hulls in Two Dimensions. 216-219 BibTeX
J. M. Robson: The Emptiness of Complement Problem for Semi Extended Regular Expressions Requires cⁿ Space. 220-222 BibTeX
Kevin Q. Brown: Voronoi Diagrams from Convex Hulls. 223-228 BibTeX
Sandra L. Mitchell: Linear Algorithms to Recognize Outerplanar and Maximal Outerplanar Graphs. 229-232 BibTeX
Roman Slowinski: Cost-Minimal Preemptive Scheduling of Independent Jobs With Release and Due Dates on Open Shop Under Resource Constraints. 233-237 BibTeX