Information Processing Letters, Volume 18

Volume 18, Number 1, 20 January 1984

Victor N. Kasyanov: Loop Cleaning. 1-6
Jan Magott: Performance Evaluation of Concurrent Systems Using Petri Nets. 7-13
Ahmed Saoudi: Infinitary Tree Languages Recognized by omega-Automata. 15-19
Hans-Jörg Kreowski, 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 Y. L. Chin, Cao An Wang: Minimum Vertex Distance Between Separable Convex Polygons. 41-45
Xiaolong Jin: Large Processors are Good in VLSI Chips. 47-49
Eiji Yodogawa: A Note on Array Grammars. 51-54
Robert Geist: Perception-Based Configuration Design of Computer Systems. 55-57

Martin E. Dyer, Alan 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, 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 Dets Appear? 87-92
Heung-Soon Ihm, Simeon C. Ntafos: On Legal Path Problems in Digraphs. 93-98
F. Scarioni, 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, 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 Møller-Nielsen, Jørgen Staunstrup: Experiments With a Fast String Searching Algorithm. 129-135
John H. Remmers: A Technique for Developing Loop Invariants. 137-139
Giuseppe Alia, Ferruccio Barsi, Enrico 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
Alberto Apostolico, Raffaele Giancarlo: Pattern Matching Machine Implementation of a Fast Test for Unique Decipherability. 155-158
Gordon V. Cormack, 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, Antoni Kreczmar: Programmed Deallocation Without Dangling Reference. 179-187
Alistair Moffat, Tadao Takaoka: A Priority Queue for the All Pairs Shortest Path Problem. 189-193
Donald C. S. Allison, M. T. Noga: The L₁ Travelling 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, Esko Ukkonen: A Simple Linear-Time Algorithm for in Situ Merging. 203-208
Susumu Yamasaki, Mikio Yoshida, Shuji Doshita, Mikito Hirata: A New Combination of Input and Unit Deductions for Horn Sentences. 209-213
Eike Best: Fairness and Conspiracies. 215-220 , Erratum: Information Processing Letters 19(3): 162 (1984)
Vladimir Lifschitz: On Verification of Programs With Goto Statements. 221-225
Takao Ohya, Masao Iri, Kazuo Murota: A Fast Voronoi-Diagram Algorithm With Quaternary Tree Bucketing. 227-231
Paolo Atzeni, Nicola M. Morfuni: Functional Dependencies in Relations with Null Values. 233-238

Burkhard Monien: Deterministic Two-Way One-Head Pushdown Automata are Very Powerful. 239-242
Marie-Paule Flé, Gérard Roucairol: Multiserialization of Iterated Transactions. 243-247
Gerhard Barth: An Analytical Comparison of Two String Search Algorithms. 249-256
Moshe Y. Vardi: A Note on Lossless Database Decompositions. 257-260
Nathan Goodman, Y. C. Tay: A Characterization of Multivalued Dependencies Equivalent to a Join Dependency. 261-266
Jacek Blazewicz, Jan Weglarz, Mieczyslaw Drabowski: Scheduling Independent 2-Processor Tasks to Minimize Schedule Length. 267-273
Mark B. Trakhtenbrot: Some Equivalent Transformations of Recursive Programs Based on Their Schematic Properties. 275-283
Bruno Courcelle: Some Negative Results Concerning DPDA's. 285-289
Shinsei Tazawa: On the Consecutive Retrieval Property for Generalized Binary Queries. 291-293
Donald K. Friesen, Michael A. Langston: A Storage-Size Selection Problem. 295-296