Information Processing Letters, Volume 28

Volume 28, Number 1, May 1988

Michel Latteux, Erick Timmerman: Bifaithful Starry Transductions. 1-4
Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. 5-11
Wojciech Szpankowski: The Evaluation of an Alternative Sum With Applications to the Analysis of Some Data Structures. 13-19
David Alex Lamb, Robin W. Dawes: Testing for Class Membership in Multi-Parent Hierarchies. 21-25
José D. P. Rolim, Sheila A. Greibach: On the IO-Complexity and Approximation Languages. 27-31
Joanna Jedrzejowicz: Infinite Hierarchy of Expressions Containing Shuffle Closure Operator. 33-37
Wei-pang Chin: Optimum Watchman Routes. 39-44
Andrew Dwelly: Synchronizing the I/O Behavior of Functional Programs with Feedback. 45-51
Stephan Olariu: Paw-Fee Graphs. 53-54

Walter W. Kirchherr: Transposition of an 1*1 Matrix Requires O(log 1) Reversals on Conservative Turing Machines. 55-59
Hillel Gazit, Gary L. Miller: An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph. 61-65
Frank K. H. A. Dehne, Ivan Stojmenovic: An O(sqrt(n)) Time Algorithm for the ECDF Searching Problem for Arbitrary Dimensions on a Mesh-of-Processors. 67-70
Victor Y. Pan: Computing the Determinant and the Characteristic Polynomial of a Matrix via Solving Linear Systems of Equations. 71-75
Joost Engelfriet, Hendrik Jan Hoogeboom: Prefix and Equality Languages of Rational Functions are Co-Context-Free. 77-79
Daniel P. Bovet, Sergio De Agostino, Rossella Petreschi: Parallelism and the Feedback Vertex Set Problem. 81-85
Yves Auffray: Linear Strategy for Propositional Modal Resolution. 87-92
Jürgen Ebert: Computing Eulerian Trails. 93-97
James H. Anderson, Mohamed G. Gouda: Atomic Semantics of Nonatomic Programs. 99-103
Catherine A. Schevon, Jeffrey Scott Vitter: A Parallel Algorithm for Recognizing Unordered Depth-First Search. 105-110

Alexandre Brandwajn: Load Imbalance in DASD Dynamic Reconnection. 111-119
Prateek Mishra: Strictness Analysis of the Untyped lambda-Calculus. 121-125
Joseph Aguilar-Martin, Claudi Alsina: Characterizations of Some Rescaling Functions. 127-132
Mark Allen Weiss, Robert Sedgewick: Bad Cases for Shaker-Sort. 133-136
John F. Morrison: Parallel p-adic Computation. 137-140
Fabrizio Luccio, Geppino Pucci, Andrea Pietracaprina: A Probabilistic Simulation of PRAMs on a Bounded Degree Network. 141-147
M. Y. Chan, W. L. Chung: Optimal Multidisk Partial Match File Designs. 149-155
Hasan Ural, Bo Yang: A Structural Test Selection Criterion. 157-163

Colm Ó'Dúnlaing: A Tight Lower Bound for the Complexity of Path-Planning for a Disc. 165-170
Makoto Imase, Yoshifumi Manabe: Fault-Tolerant Routings in a kappa-Connected Network. 171-175
Moon-Jung Chung, Mukkai S. Krishnamoorthy: Algorithms of Placing Recovery Points. 177-181
Jianzhong Du, Joseph Y.-T. Leung: Scheduling Tree-Structured Tasks with Restricted Execution Times. 183-188
Daniel J. Rosenkrantz, Harry B. Hunt III: Matrix Multiplication for Finite Algebraic Systems. 189-192
Yuji Takada: Grammatical Interface for Even Linear Languages Based on Control Sets. 193-199
Guan-Ing Chen, Ten-Hwang Lai: Preemptive Scheduling of Independent Jobs on a Hypercube. 201-206
Gilles Brassard, Sampath Kannan: The Generation of Random Permutations on the Fly. 207-212
Ichiro Suzuki: Proving Properties of a Ring of Finite-State Machines. 213-214
Katsushi Inoue, Itsuo Takanami: Some Considerations About NPRIORITY(1) Without ROM. 215-219

Antoni W. Mazurkiewicz: Solvability of the Asynchronous Ranking Problem. 221-224
Ananth V. Iyer, H. Donald Ratliff, Gopalakrishnan Vijayan: Optimal Node Ranking of Trees. 225-229
Don Platt, A. Magdy: Adaptive Control Using Switched Capacitor Filters. 231-234
Shuo-Yen Robert Li: Reconstruction of Polygons from Projections. 235-240
Howard J. Karloff, Ramamohan Paturi, Janos Simon: Universal Traversal Sequences of Length n^O(log n) for Cliques. 241-243
Jean-François Romeuf: Shortest Path Under Rational Constraint. 245-248
Lance Fortnow, Michael Sipser: Are There Interactive Protocols for CO-NP Languages? 249-251
Paolo Ciaccia, Dario Maio, Paolo Tiberio: A Unifying Approach to Evaluating Block Accesses in Database Organizations. 253-257
P. K. Das, D. Q. M. Fay: Fault-Tolerant and Flexible Interconnection of Multiple Processors. 259-268
Leslie L. Miller, Shashi K. Gadia, Suresh C. Kothari, K. C. Liu: Completeness Issues for Join Dependencies Derived from the Universal Relation Join Dependency. 269-274

Alan A. Bertossi: On the Domatic Number of Interval Graphs. 275-280
D. W. Wang, Yue-Sun Kuo: A Study on Two Geometric Location Problems. 281-286
K. Vidyasankar: Converting Lamport's Regular Register to Atomic Register. 287-290
Juris Hartmanis, Lane A. Hemachandra: On Sparse Oracles Separating Feasible Complexity Classes. 291-295
Gen-Huey Chen, M. S. Yu, Lung-Tien Liu: Two Algorithms for Constructing a Binary Tree from its Traversals. 297-299
Chin-Wen Ho, Richard C. T. Lee: Efficient Parallel Algorithms for Finding Maximal Cliques, Clique Trees, and Minimum Coloring on Chordal Graphs. 301-309
Maciej Liskiewicz, Krzysztof Lorys: Alternating Real-Time Computations. 311-316
Edward P. F. Chan, Héctor J. Hernández: Testing Unboundedness of Database Schemes and Functional Dependencies. 317-326
Michael C. Loui, Teresa A. Matsushita, Douglas B. West: Election in a Complete Network with a Sense of Direction. 327