Information Processing Letters, Volume 28

Volume 28, Number 1, May 1988

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

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

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

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

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

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