Last update: Fri Oct 20 15:24:14 MDT 2023
Volume 16, Number 4, May 13, 1983Greg N. Frederickson Scheduling Unit-Time Tasks with Integer Release Times and Deadlines . . . . . . 171--173
J. Pierre Verjus On the proof of a distributed algorithm 145--147
Kurt Mehlhorn A faster approximation algorithm for the Steiner problem in graphs . . . . . . . 125--128
Kerry Raymond A distributed algorithm for multiple entries to a critical section . . . . . 189--193
Martin Kochol Efficient monotone circuits for threshold functions . . . . . . . . . . 121--122
Erkki Mäkinen On the subtree isomorphism problem for ordered trees . . . . . . . . . . . . . 271--273
P. Crescenzi and R. Silvestri Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems . . . 221--226 Hitoshi Suzuki and Naomi Takahashi and Takao Nishizeki A linear algorithm for bipartition of biconnected graphs . . . . . . . . . . . 227--231 Yijie Han and Yoshihide Igarashi Time lower bounds for sorting on multi-dimensional mesh-connected processor arrays . . . . . . . . . . . . 233--238 Jürgen Kämper A result relating disjunctive self-reducibility to $P$-immunity . . . 239--242 C. S. Kannan and Henry Y. H. Chuang Fast Hough transform on a mesh connected processor array . . . . . . . . . . . . 243--248 Laurence Boxer and Russ Miller Common intersections of polygons . . . . 249--254 Divyakant Agrawal and Amr El Abbadi Exploiting logical structures in replicated databases . . . . . . . . . . 255--260 Victor Shoup On the deterministic complexity of factoring polynomials over finite fields 261--267 Richard J. Anderson and Gary L. Miller A simple randomized parallel algorithm for list-ranking . . . . . . . . . . . . 269--273
Alan A. Bertossi and Sabrina Moretti Parallel algorithms on circular-arc graphs . . . . . . . . . . . . . . . . . 275--281 Michael B. Dillencourt Realizability of Delaunay triangulations 283--287 Neil J. Gunther and John G. Shaw Path integral evaluation of ALOHA network transients . . . . . . . . . . . 289--295 Tom Altman and Bogdan S. Chlebus Sorting roughly sorted sequences in parallel . . . . . . . . . . . . . . . . 297--300 Stephan Olariu A generalization of Chvatal's star-cutset lemma . . . . . . . . . . . 301--303 Torben Hagerup and Christine Rüb A guided tour of Chernoff bounds . . . . 305--308 Zvi Galil and Kunsoo Park A linear-time algorithm for concave one-dimensional dynamic programming . . 309--311 Philips Hingston and Ross Wilkinson A distributed join algorithm . . . . . . 313--317 Samir Khuller and Joseph S. B. Mitchell On a triangle counting problem . . . . . 319--321 Edgar Knapp A predicate transformer for progress . . 323--330
Masahito Kurihara and Ikuo Kaji Modular term rewriting systems and the termination . . . . . . . . . . . . . . 1--4 Mohan Ahuja Flush primitives for asynchronous distributed systems . . . . . . . . . . 5--12 Shai Simonson Routing with critical paths . . . . . . 13--19 Arne Andersson and Svante Carlsson Construction of a tree from its traversals in optimal time and space . . 21--25 Jeremy Jacob Separability and the detection of hidden channels . . . . . . . . . . . . . . . . 27--29 Alejandro D. Martinez and Rosita Wachenchauzer and Rafael D. Lins Cyclic reference counting with local mark-scan . . . . . . . . . . . . . . . 31--35 O. J. Murphy and S. M. Selkow Finding nearest neighbors with Voronoi tessellations . . . . . . . . . . . . . 37--41 Carla Neaderhouser Purdy and George B. Purdy The area-time complexity of the greatest common divisor problem: a lower bound 43--46 Joseph Y.-T. Leung and Gilbert H. Young Preemptive scheduling to minimize mean weighted flow time . . . . . . . . . . . 47--50 R. Morrison and M. P. Atkinson and A. L. Brown and A. Dearle On the classification of binding mechanisms . . . . . . . . . . . . . . . 51--55
Simeon Ntafos The robber route problem . . . . . . . . 59--63 Pradip Dey and Barrett R. Bryant and Tadao Takaoka Lexical ambiguity in tree adjoining grammars . . . . . . . . . . . . . . . . 65--69 Young C. Wee and Seth Chaiken and Dan E. Willard On the angle restricted nearest neighbor problem . . . . . . . . . . . . . . . . 71--76 Sandeep Sen Finding an approximate median with high probability in constant parallel time 77--80 Stephen Cook and Toniann Pitassi A feasibly constructive lower bound for resolution proofs . . . . . . . . . . . 81--85 Jean-Paul Laumond Connectivity of plane triangulations . . 87--96 Stephan Olariu On the closure of triangle-free graphs under substitution . . . . . . . . . . . 97--101 Michel Cosnard and Jean Duprat and Afonso G. Ferreira The complexity of searching in X+Y and other multisets . . . . . . . . . . . . 103--109
C. A. R. Hoare Fixed points of increasing functions . . 111--112 J. M. Pallo A distance metric on binary trees using lattice-theoretic measures . . . . . . . 113--116 A. Bertoni and M. Goldwurm and P. Massazza Counting problems and algebraic formal power series in noncommuting variables 117--121 Lein Harn and Thomas Kiesler An efficient probabilistic encryption scheme . . . . . . . . . . . . . . . . . 123--129 Moon Hwa Park and Myunghwan Kim A distributed synchronization scheme for fair multi-process handshakes . . . . . 131--138 Henk Goeman Towards a theory of (self) applicative communicating processes. A short note 139--142 Christoph Meinel Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree . . . . . . . . . . . . . . . . . 143--146 Shang-Hua Teng Space efficient Processor Identity protocol . . . . . . . . . . . . . . . . 147--154 John C. Tipper A straightforward iterative algorithm for the planar Voronoi diagram . . . . . 155--160 Jürgen Plehn Preemptive scheduling of independent jobs with release times and deadlines on a hypercube . . . . . . . . . . . . . . 161--166
Udi Manber Recognizing breadth-first search trees in linear time . . . . . . . . . . . . . 167--171 L. V. Kale An almost perfect heuristic for the $N$-nonattacking queens problem . . . . 173--178 Earlin Lutz Some proofs of data refinement . . . . . 179--185 Biing-Feng Wang and Gen-Huey Chen and Ferng-Ching Lin Constant time sorting on a processor array with a reconfigurable bus system 187--192 James H. Bradford Sequence matching with binary codes . . 193--196 A. Bagchi and S. L. Hakimi and J. Mitchem and E. Schmeichel Parallel algorithms for gossiping by mail . . . . . . . . . . . . . . . . . . 197--202 Samir Khuller Coloring algorithms for K$_5$-minor free graphs . . . . . . . . . . . . . . . . . 203--208 James Cooper and Leslie Kitchen CASOP: A fast algorithm for computing the $n$-ary composition of a binary associative operator . . . . . . . . . . 209--213 G. Ramalingam and C. Pandu Rangan New sequential and parallel algorithms for interval graph recognition . . . . . 215--219
P. E. Dunne Comment on Kochol's paper ``Efficient monotone circuits for threshold functions'' [Inform. Process. Lett. \bf 32(3), 24 August 1989, pp. 121--122] . . 221--222 Stefan Ronn and Heikki Saikkonen Distributed termination detection with counters . . . . . . . . . . . . . . . . 223--227 Zsolt Tuza Periodic string division generated by deterministic $L$ systems . . . . . . . 229--234 Sung Kwon Kim A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle . . . . . . . . . . . . . . 235--241 Owen Murphy A unifying framework for trie design heuristics . . . . . . . . . . . . . . . 243--249 William Pugh Slow optimally balanced search strategies vs. cached fast uniformly balanced search strategies . . . . . . . 251--254 A. Pombortsis Sharing special purpose resources in a multiprocessor environment . . . . . . . 255--260 R. T. Kuo and S. S. Tseng The necessary and sufficient condition for the worst-case male optimal stable matching . . . . . . . . . . . . . . . . 261--263 J. M. Robson Random access machines with multi-dimensional memories . . . . . . . 265--266 Mark Allen Weiss and Robert Sedgewick More on Shellsort increment sequences 267--270 Gaston H. Gonnet and Ricardo A. Baeza-Yates An analysis of the Karp-Rabin string matching algorithm . . . . . . . . . . . 271--274 Ingo Althöfer Tight lower bounds on the length of word chains . . . . . . . . . . . . . . . . . 275--276
Oded Goldreich A note on computational indistinguishability . . . . . . . . . . 277--281 N. Chandrasekharan Isomorphism testing of $k$-trees is in NC, for fixed $k$ . . . . . . . . . . . 283--287 Jan Chomicki and V. S. Subrahmanian Generalized closed world assumption is $\Pi_2^0$-complete . . . . . . . . . . . 289--291 Lenwood S. Heath Covering a set with arithmetic progressions is NP-complete . . . . . . 293--298 M. R. Zargham and K. J. Danhof Toward a definition of fault analysis for Petri nets models . . . . . . . . . 299--305 Philip Klein and Clifford Stein A parallel algorithm for eliminating cycles in undirected graphs . . . . . . 307--312 Gabriel Matsliach and Oded Shmueli Distributing a $B^+$-tree in a loosely coupled environment . . . . . . . . . . 313--321 A. Sengupta and S. Bandyopadhyay Deadlock-free routing in $k$-ary hypercube network in presence of processor failures . . . . . . . . . . . 323--328
Mitchell Wand A short proof of the lexical addressing algorithm . . . . . . . . . . . . . . . 1--5 Mohan Ahuja and Yahui Zhu An $O(n\log n)$ feasibility algorithm for preemptive scheduling of $n$ independent jobs on a hypercube . . . . 7--11 Alok Aggarwal and Subhash Suri Computing the longest diagonal of a simple polygon . . . . . . . . . . . . . 13--18 Jeremy Jacob A model of reconfiguration in communicating sequential processes . . . 19--22 Chanderjit L. Bajaj and Tamal Dey Polygon nesting and robustness . . . . . 23--32 Rani Siromoney and Lisa Mathew A public key cryptosystem based on Lyndon words . . . . . . . . . . . . . . 33--36 Yu-Tai Ching and Kurt Mehlhorn and Michiel H. M. Smid Dynamic deferred data structuring . . . 37--40 E. Lodi and F. Luccio and L. Pagli Routing in times square mode . . . . . . 41--48 Ronitt Rubinfeld The cover time of a regular expander is $O(n\log n)$ . . . . . . . . . . . . . . 49--51 L. Boxer and R. Miller Corrigenda: ``Common intersections of polygons'' [Inform. Process. Lett. \bf 33(5), 10 January 1990, pp. 249--254] 53--53 D. Kumar and S. S. Iyengar and M. B. Sharma Corrections to a distributed depth-first search algorithm . . . . . . . . . . . . 55--56
Anna Lubiw Counterexample to a conjecture of Szymanski on hypercube routing . . . . . 57--61 Ted Herman Probabilistic self-stabilization . . . . 63--67 G. R. Guenther Efficient expansion of factored expressions . . . . . . . . . . . . . . 69--72 Maurice Maes On a cyclic string-to-string correction problem . . . . . . . . . . . . . . . . 73--78 D. T. Barnard and D. B. Skillicorn Pipelining tree-structured algorithms on SIMD architectures . . . . . . . . . . . 79--84 Khun Yee Fung and Tina M. Nicholl and Robert E. Tarjan and Christopher J. Van Wyk Simplified linear-time Jordan sorting and polygon clipping . . . . . . . . . . 85--92 Ching-Lin Wang Obtaining lazy evaluation with continuations in Scheme . . . . . . . . 93--97 Ingo Wegener Efficient simulation of circuits by EREW PRAMs . . . . . . . . . . . . . . . . . 99--102 Martha Sideris On attribute grammars without attribute synthesis . . . . . . . . . . . . . . . 103--109
Tom Altman and George Logothetis A note on ambiguity in context-free grammars . . . . . . . . . . . . . . . . 111--114 Erik Lambrichts and Peter Nees and Jan Paredaens and Peter Peelman and Letizia Tanca Checking functional consistency in deductive databases . . . . . . . . . . 115--120 Maxime Crochemore and Wojciech Rytter Parallel construction of minimal suffix and factor automata . . . . . . . . . . 121--128 Marta Z. Kwiatkowska A metric for traces . . . . . . . . . . 129--135 K. Mehlhorn and S. Näher and C. Uhrig Hidden line elimination for isooriented rectangles . . . . . . . . . . . . . . . 137--143 Moshe Y. Vardi Endmarkers can make a difference . . . . 145--148 Srinivasa Rao Arikati and C. Pandu Rangan Linear algorithm for optimal path cover problem on interval graphs . . . . . . . 149--153 John Launchbury Strictness analysis aids inductive proofs . . . . . . . . . . . . . . . . . 155--159 Jerzy A. Piotrowski A functional model of a simplified sequential machine . . . . . . . . . . . 161--166
Chau-Jy Lin Parallel algorithm for generating permutations on linear array . . . . . . 167--170 Mohamed G. Gouda and Ted Herman Stabilizing unison . . . . . . . . . . . 171--175 Shyan-Ming Yuan The communication complexity for decentralized evaluation of functions 177--182 Kurt Mehlhorn and Stefan Näher Bounded ordered dictionaries in $O(\log \log n)$ time and $O(n)$ space . . . . . 183--189 P. Inverardi and M. Nesi A rewriting strategy to verify observational congruence . . . . . . . . 191--199 Noga Alon Generating pseudo-random permutations and maximum flow algorithms . . . . . . 201--204 Glenn K. Manacher and Terrance A. Mankus and Carol Joan Smith An optimum $\Theta (n \log n)$ algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals . . . . . . . . . . . . 205--211 Xiaotie Deng An optimal parallel algorithm for linear programming in the plane . . . . . . . . 213--217
Kenneth Block and Tai-Kuo Woo A more efficient generalization of Peterson's mutual exclusion algorithm 219--222 Michael C. Loui and Milind A. Sohoni An algorithm for load balancing in multiprocessor systems . . . . . . . . . 223--228 Seinosuke Toda On the complexity of topological sorting 229--233 Erich Grädel Simple interpretations among complicated theories . . . . . . . . . . . . . . . . 235--238 Ken Grigg and Serge Miguet and Yves Robert Symmetric matrix-vector product on a ring of processors . . . . . . . . . . . 239--248 Robert J. Cimikowski Finding Hamiltonian cycles in certain planar graphs . . . . . . . . . . . . . 249--254 Maw Shang Chang and Nen-Fu Huang and Chuan-Yi Tang An optimal algorithm for constructing oriented Voronoi diagrams and geographic neighborhood graphs . . . . . . . . . . 255--260 Lisa Hellerstein and Philip Klein and Robert Wilber On the time-space complexity of reachability queries for preprocessed graphs . . . . . . . . . . . . . . . . . 261--267 Matthew T. Dickerson and R. Scot Drysdale Fixed-radius near neighbors search algorithms for points and segments . . . 269--273
A. J. M. Van Gasteren and G. Tel Comments on ``On the proof of a distributed algorithm'': always-true is not invariant . . . . . . . . . . . . . 277--279 David B. Shmoys and David P. Williamson Analyzing the Held-Karp TSP bound. A monotonicity property with application 281--285 A. W. Mostowski Alternating automata with start formulas 287--290 George Karner A note on terminal balancing of algebraic systems . . . . . . . . . . . 291--293 Chain-Chin Yen and R. C. T. Lee The weighted perfect domination problem 295--299 Alok Aggarwal and Tom Leighton A tight lower bound for the train reversal problem . . . . . . . . . . . . 301--304 Chwan-Hwa Wu and Chia-Jiu Wang and Heng-Ming Tai Application of exponential hetero-associative memory on frequency classifier . . . . . . . . . . . . . . . 305--311 Jang-Ping Sheu and Jyh-Shyan Tang Efficient parallel $k$ selection algorithm . . . . . . . . . . . . . . . 313--316 Sun Wu and Udi Manber and Gene Myers and Webb Miller $O(NP)$ sequence comparison algorithm 317--323 Andrew Chin On the depth complexity of the counting functions . . . . . . . . . . . . . . . 325--328
Zhen Liu A Note on Graham's Bound . . . . . . . . 1--5 Wen-Huei Chen and Ching-Sung Lu and Elben R. Brozovsky and Jin-Tuu Wang An optimization technique for protocol conformance testing using multiple UIO sequences . . . . . . . . . . . . . . . 7--11 Joanna J\polhkedrzejowicz Infinite hierarchy of shuffle expressions over a finite alphabet . . . 13--17 Haklin Kim Finding a maximum independent set in a permutation graph . . . . . . . . . . . 19--23 Frank Dederichs and Rainer Weber Safety and liveness from a methodological point of view . . . . . . 25--30 Biing-Feng Wang and Gen-Huey Chen Two-Dimensional processor array with a reconfigurable bus system is at least as powerful as CRCW model . . . . . . . . . 31--36 Stanley Burris and John Lawrence Unification in commutative rings is not finitary . . . . . . . . . . . . . . . . 37--38 Malcolm C. Fields and Greg N. Frederickson A faster algorithm for the maximum weighted tardiness problem . . . . . . . 39--44 Oded Goldreich and Erez Petrank The best of both worlds: guaranteeing termination in fast randomized Byzantine Agreement protocols . . . . . . . . . . 45--49 Ke Qiu and Henk Meijer A note on diameter of acyclic directed hypercubes . . . . . . . . . . . . . . . 51--52 Hans L. Bodlaender and Gerard Tel Bit-optimal election in synchronous rings . . . . . . . . . . . . . . . . . 53--56
Torben Hagerup and Hong Shen Improved nonconservative sequential and parallel integer sorting . . . . . . . . 57--63 Miklos Biro Object-oriented interaction in resource constrained scheduling . . . . . . . . . 65--67 Anna Slobodova One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages . . . . . . 69--72 Stephen A. Vavasis Quadratic programming is in NP . . . . . 73--77 Jin-yi Cai Lower bounds for constant-depth circuits in the presence of help bits . . . . . . 79--83 Jae Moon Lee and Jong Soo Park and Myunghwan Kim An upper bound on buffer size for join operation using nonclustered indexes . . 85--90 Richard J. Lipton and Arvin Park The processor identity problem . . . . . 91--94 Chandan Haldar and L. M. Patnaik Oracle complexities for computational geometry of semi-algebraic sets and Voronoi diagrams . . . . . . . . . . . . 95--102 G. M. Megson and F. M. F. Gaston Improved matrix triangularisation using a double pipeline systolic array . . . . 103--109
De-Lei Lee Efficient address generation in a parallel processor . . . . . . . . . . . 111--116 Jingde Cheng An algebraic semantics of notional entailment logic Cn . . . . . . . . . . 117--121 Aphrodite Tsalgatidou Modelling and animating information systems dynamics . . . . . . . . . . . . 123--127 Shuo-Yen Robert Li On full utilization of multi-channel capacity with priority protocol . . . . 129--133 Laura A. Sanchis On the complexity of test case generation for NP-hard problems . . . . 135--140 John G. Kollias and Yannis Manolopoulos and Christos H. Papadimitriou The optimum execution order of queries in linear storage . . . . . . . . . . . 141--145 Lawrence L. Larmore An optimal algorithm with unknown time complexity for convex matrix searching 147--151 R. Lin and S. Olariu A fast parallel algorithm to recognize partitionable graphs . . . . . . . . . . 153--157 A. Paulik Worst-case analysis of a generalized heapsort algorithm . . . . . . . . . . . 159--165
Kim-Heng Teo and Tai-Ching Tuan Performance analysis of greedy heuristic to find a minimum total-jogs layout for river routing . . . . . . . . . . . . . 167--170 Valmir C. Barbosa Blocking versus nonblocking interprocess communication. A note on the effect on concurrency . . . . . . . . . . . . . . 171--175 Hans Kleine Büning Existence of simple propositional formulas . . . . . . . . . . . . . . . . 177--182 Xiaolei Qian An Axiom System for Database Transactions . . . . . . . . . . . . . . 183--189 Gerhard Woeginger A simple solution to the two paths problem in planar graphs . . . . . . . . 191--192 Edsger W. Dijkstra Making a fair roulette from a possibly biased coin . . . . . . . . . . . . . . 193--193 S. Ramesh On the completeness of modular proof systems . . . . . . . . . . . . . . . . 195--201 Erkki Makinen The grammatical inference problem for the Szilard languages of linear grammars 203--206 Bernd-Jürgen Falkowski Perceptrons revisited . . . . . . . . . 207--213 Miros\law Kuty\lowski Remarks on sorting and one-way multihead finite automata . . . . . . . . . . . . 215--218 Jozef Vyskoc Making bubblesort recursive . . . . . . 219--220
Hyoung Joong Kim and Jang Gyu Lee Partial sum problem mapping into a hypercube . . . . . . . . . . . . . . . 221--224 Jin Ho Hur and Kilnam Chon Self and selftype . . . . . . . . . . . 225--230 Peter Damaschke and Haiko Müller and Dieter Kratsch Domination in convex and chordal bipartite graphs . . . . . . . . . . . . 231--236 Ursula Martin A note on division orderings on strings 237--240 Jang-Ping Sheu and Zen-Fu Chiang Efficient allocation of chain-like task on chain-like network computers . . . . 241--245 Carsten Damm Problems complete for $\oplus L$ . . . . 247--250 Siu Wing Cheng and Ravi Janardan Efficient dynamic algorithms for some geometric intersection problems . . . . 251--258 Marc Gyssens and Jan Paredaens and Dirk Van Gucht On a hierarchy of classes for nested databases . . . . . . . . . . . . . . . 259--266 O. M. Makarov On the synthesis of fast algorithms for signal processing . . . . . . . . . . . 267--272 P. Dublish Some comments on the subtree isomorphism problem for ordered trees . . . . . . . 273--275
Subir Kumar Ghosh and Anil Maheshwari An optimal algorithm for computing a minimum nested nonconvex polygon . . . . 277--280 F. Kocsis and J. F. Böhme Rotation-based computations for ray-tracing second-order surfaces and curves . . . . . . . . . . . . . . . . . 281--283 Antonio Brogi and Evelina Lamma and Paola Mello Hypothetical reasoning in logic programming. A semantic approach . . . . 285--291 Z. Fülöp and S. Vágvölgyi The emptiness problem is undecidable for domains of partial monadic $2$-modular tree transformations . . . . . . . . . . 293--296 Rob R. Hoogerwoord A calculational derivation of the CASOP algorithm . . . . . . . . . . . . . . . 297--299 Gabriel Matsliach Performance analysis of file organizations that use multi-bucket data leaves . . . . . . . . . . . . . . . . . 301--310 Kai Salomaa and Sheng Yu The immortality problem for Lag systems 311--315 Giuseppe Di Battista and Wei-Ping Liu and Ivan Rival Bipartite graphs, upward drawings, and planarity . . . . . . . . . . . . . . . 317--322 Sung Kwon Kim Parallel algorithms for the segment dragging problem . . . . . . . . . . . . 323--327
Chung-Kuo Chang and M. G. Gouda On the minimum requirements for independent recovery in distributed systems . . . . . . . . . . . . . . . . 1--7 Xubo Zhang Overlap closures do not suffice for termination of general term rewriting systems . . . . . . . . . . . . . . . . 9--11 Soma Chaudhuri and Richard E. Ladner Safety and liveness of $\omega$-context-free languages . . . . 13--20 Stephan Olariu An optimal greedy heuristic to color interval graphs . . . . . . . . . . . . 21--25 Viggo Kann Maximum bounded $3$-dimensional matching is MAX SNP-complete . . . . . . . . . . 27--35 Yannis Manolopoulos and Athina Vakali Seek distances in disks with two independent heads per surface . . . . . 37--42 U. K. Sarkar and P. P. Chakrabarti and S. Ghose and S. C. De Sarkar Multiple stack branch and bound . . . . 43--48 Douglas Campbell and John Higgins Minimal visibility graphs . . . . . . . 49--53 Bin Yu and Xinggang Lin and Youshou Wu The tree representation of the graph used in binary image processing . . . . 55--59
Igor Litovsky Prefix-free languages as $\omega$-generators . . . . . . . . . . 61--65 Fabrizio Luccio and Andrea Pietracaprina and Geppino Pucci Analysis of Parallel Uniform Hashing . . 67--69 Timothy Law Snyder Lower bounds for rectilinear Steiner trees in bounded space . . . . . . . . . 71--74 C. C. Handley A space efficient distributive sort . . 75--78 Roberto Tamassia An incremental reconstruction method for dynamic planar point location . . . . . 79--83 Yoshihiro Tanaka A dual algorithm for the satisfiability problem . . . . . . . . . . . . . . . . 85--89 Richard Beigel and Lane A. Hemachandra and Gerd Wechsung Probabilistic polynomial time is closed under parity reductions . . . . . . . . 91--94 J. von Wright Program inversion in the refinement calculus . . . . . . . . . . . . . . . . 95--100 Alan Gibbons and Ridha Ziani The balanced binary tree technique on mesh-connected computers . . . . . . . . 101--109 Xin He An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon . . . . . . . 111--116 Svante Carlsson An optimal algorithm for deleting the root of a heap . . . . . . . . . . . . . 117--120
Sven Skyum A simple algorithm for computing the smallest enclosing circle . . . . . . . 121--125 Jurek Czyzowicz and K. B. Lakshmanan and Andrzej Pelc Searching with a forbidden lie pattern in responses . . . . . . . . . . . . . . 127--132 Udi Manber and Ricardo Baeza-Yates An algorithm for string matching with a sequence of don't cares . . . . . . . . 133--136 Pavol Duris and Imrich Vrto Semelectivity is not sufficient . . . . 137--141 Bin Jiang Traversing graphs in a paging environment, BFS or DFS? . . . . . . . . 143--147 Frederic Green Oracle separating $\oplus P$ from $PP^{PH}$ . . . . . . . . . . . . . . . 149--153 A. J. E. M. Janssen An optimization problem related to neural networks . . . . . . . . . . . . 155--157 Galen Sasaki The Effect of the Density of States on the Metropolis Algorithm . . . . . . . . 159--163 D\~ung T. H\`uynh The effective entropies of some extensions of context-free languages . . 165--169 Wladyslaw M. Turski On starvation and some related issues 171--174 Micha Hofri and Hadas Shachnai On the optimality of the counter scheme for dynamic linear lists . . . . . . . . 175--179\$
Zhaofang Wen Parallel multiple search . . . . . . . . 181--186 D. P. Jacobs Probabilistic checking of associativity in algebras . . . . . . . . . . . . . . 187--191 Xiaotie Deng and Sanjeev Mahajan Server problems and resistive spaces . . 193--196 Robert W. Irving On approximating the minimum independent dominating set . . . . . . . . . . . . . 197--200 Xue-Hou Tan and Tomio Hirata and Yasuyoshi Inagaki The intersection searching problem for $c$-oriented polygons . . . . . . . . . 201--204 C. Huizing and W. P. de Roever Introduction to design choices in the semantics of Statecharts . . . . . . . . 205--213 U. Zwick An extension of Khrapchenko's theorem 215--217 Y. Liang and C. Rhee and S. K. Dhall and S. Lakshmivarahan A new approach for the domination problem on permutation graphs . . . . . 219--224 Peter F. Corbett and Isaac D. Scherson A unified algorithm for sorting on multidimensional mesh-connected processors . . . . . . . . . . . . . . . 225--231 Maria Serna Approximating linear programming is log-space complete for P . . . . . . . . 233--236 H. Alt and N. Blum and K. Mehlhorn and M. Paul Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}\sqrt m/log n)$ . . . . . . . 237--240
Shyan Ming Yuan Topological properties of supercube . . 241--245 James K. Mullin A Caution on Universal Classes of Hash Functions . . . . . . . . . . . . . . . 247--256 Dani\`ele Beauquier An undecidable problem about rational sets and contour words of polyominoes 257--263 Anne Kaldewaij and Berry Schoenmakers The derivation of a tighter bound for top-down skew heaps . . . . . . . . . . 265--271 Toshiya Itoh Characterization for a family of infinitely many irreducible equally spaced polynomials . . . . . . . . . . . 273--277 Yasubumi Sakakibara On learning from queries and counterexamples in the presence of noise 279--284 Gadi Taubenfeld On the nonexistence of resilient consensus protocols . . . . . . . . . . 285--289 Qingzhou Wang and Kam Hoi Cheng List scheduling of parallel tasks . . . 291--297
Dirk Taubner A note on the notation of recursion in process algebras . . . . . . . . . . . . 299--303 Kim-Heng Teo and Tai-Ching Tuan An improved upper bound on the number of intersections between two rectangular paths . . . . . . . . . . . . . . . . . 305--309 Sabri A. Mahmoud Motion estimation based on modified Fourier spectrum . . . . . . . . . . . . 311--313 Olivier Danvy Semantics-directed compilation of nonlinear patterns . . . . . . . . . . . 315--322 K. Vidyasankar A very simple construction of $1$-writer multireader multivalued atomic variable 323--326 Biing-Feng Wang and Chuen-Liang Chen and Gen-Huey Chen A simple approach to implementing multiplication with small tables . . . . 327--329 Zvi Galil and Giuseppe F. Italiano A note on set union with arbitrary deunions . . . . . . . . . . . . . . . . 331--335 Myung-Joon Lee and Kwang-Moo Choe ${\rm SLR}(k)$ covering for ${\rm LR}(k)$ grammars . . . . . . . . . . . . 337--347 R. Srikant and Kamala Krithivasan Fastest path across constrained moving rectilinear obstacles . . . . . . . . . 349--353 Nageswara S. V. Rao and Weixiong Zhang Building heaps in parallel . . . . . . . 355--358
Victor J. Dielissen and Anne Kaldewaij Rectangular partition is polynomial in two dimensions but NP-complete in three 1--6 P. Goral\vcík and A. Goral\vcíková and V. Koubek Alternation with a pebble . . . . . . . 7--13 Ivan Stojmenovi\'c Bisections and ham-sandwich cuts of convex polygons and polyhedra . . . . . 15--21 Ahmed K. Elmagarmid and Wei Min Du Integrity aspects of quasi serializability . . . . . . . . . . . . 23--28 Shi-Jinn Horng and Wen-Tsuen Chen and Ming-Yi Fang Optimal speed-up algorithms for template matching on SIMD hypercube multiprocessors with restricted local memory . . . . . . . . . . . . . . . . . 29--37 Victor Shoup Smoothness and factoring polynomials over finite fields . . . . . . . . . . . 39--42 Xu Cheng A graph transformation algorithm for concurrency control in a partitioned database . . . . . . . . . . . . . . . . 43--48 Calvin C.-Y. Chen and Sajal K. Das and Selim G. Akl A unified approach to parallel depth-first traversals of general trees 49--55
Maxime Crochemore and Wojciech Rytter Efficient parallel algorithms to test square-freeness and factorize strings 57--60 C. \`Alvarez and J. Gabarró The parallel complexity of two problems on concurrency . . . . . . . . . . . . . 61--70 Hsu Chun Yen A polynomial time algorithm to decide pairwise concurrency of transitions for $1$-bounded conflict-free Petri nets . . 71--76 Giovanni Manzini Radix sort on the hypercube . . . . . . 77--81 João Meidânis Lower bounds for arithmetic problems . . 83--87 Xavier Messeguer Dynamic behaviour in updating process over BST of size two with probabilistic deletion algorithms . . . . . . . . . . 89--100 Jayadev Misra Phase synchronization . . . . . . . . . 101--105 Steven Minsker The Towers of Antwerpen problem . . . . 107--111
Ming-Yang Kao and Stephen R. Tate Online matching with blocked input . . . 113--116 David Fernández-Baca and Mark A. Williams On matroids and hierarchical graphs . . 117--121 Günter Rote Computing the minimum Hausdorff distance between two-point sets on a line under translation . . . . . . . . . . . . . . 123--127 Lars Langemyr Circuits for computing the GCD of two polynomials over an algebraic number field . . . . . . . . . . . . . . . . . 129--134 Charles Martel Self-adjusting multi-way search trees 135--141 Subbiah Rajanarayanan and Sitharama S. Iyengar A new optimal distributed algorithm for the set intersection problem . . . . . . 143--148 Günter Rote and Gerhard Woeginger and Binhai Zhu and Zhengyan Wang Counting $k$-subsets and convex $k$-gons in the plane . . . . . . . . . . . . . . 149--151 Michal Mnuk A div($n$) depth Boolean circuit for smooth modular inverse . . . . . . . . . 153--156 P. Pramanik and P. K. Das and A. K. Bandyopadhyay and D. Q. M. Fay A deadlock-free communication kernel for loop architecture . . . . . . . . . . . 157--161 Dragan M. Acketa and Jovi\vsa D. \vZuni\'c On the number of linear partitions of the $(m,n)$-grid . . . . . . . . . . . . 163--168
James H. Bradford and T. A. Jenkyns On the inadequacy of tournament algorithms for the $N$-SCS problem . . . 169--171 Marek Chrobak and Lawrence L. Larmore A note on the server problem and a benevolent adversary . . . . . . . . . . 173--175 Rolf Floren A note on: ``A faster approximation algorithm for the Steiner problem in graphs'' [Inform. Process. Lett. \bf 27 (1988), no. 3, 125--128; MR 89d:68031] by K. Mehlhorn . . . . . . . . . . . . . 177--178 Andrew V. Goldberg Processor-efficient implementation of a maximum flow algorithm . . . . . . . . . 179--185 Laurent Siklossy and Eduard Tulp The space reduction method: a method to reduce the size of search spaces . . . . 187--192 William I. Gasarch On selecting the $k$ largest with restricted quadratic queries . . . . . . 193--195 Ernst L. Leiss and Hari N. Reddy Embedding complete binary trees into hypercubes . . . . . . . . . . . . . . . 197--199 R. Shonkwiler Computing the Hausdorff set distance in linear time for any $L_p$ point distance 201--207 J. M. Basart Some upper bounds for minimal trees . . 209--213 Jin-yi Cai and Lane A. Hemachandra A note on enumerative counting . . . . . 215--219 Markku Sakkinen Selftype is a special case . . . . . . . 221--224
W. Rytter and A. Saoudi On the complexity of the recognition of parallel $2$D-image languages . . . . . 225--229 John Hershberger A new data structure for shortest path queries in a simple polygon . . . . . . 231--235 Andrzej Lingas Bit complexity of matrix products . . . 237--242 Myoung Ho Kim and Sakti Pramanik The FX distribution method for parallel processing of partial match queries . . 243--252 Gerhard Woeginger On minimizing the sum of $k$ tardinesses 253--256 Susanne Hambrusch and Michael Luby Parallel asynchronous connected components in a mesh . . . . . . . . . . 257--263 T. Z. Kalamboukis and S. L. Mantzaris Towards optimal distributed election on chordal rings . . . . . . . . . . . . . 265--270 Farshad Fotouhi and Sakti Pramanik Problem of optimizing the number of block accesses in performing relational join is NP-hard . . . . . . . . . . . . 271--275 Jiri Matousek Computing dominances in $E^n$ . . . . . 277--278 Timothy Law Snyder Corrigendum: ``Lower bounds for rectilinear Steiner trees in bounded space'' [Inform. Process. Lett. \bf 37(2), 31 January 1991, pp. 71--74] . . 279--279 Myung-Joon Lee and Kwang-Moo Choe Corrigenda: ``${\rm SLR}(k)$ covering for ${\rm LR}(k)$ grammars'' . . . . . . 281--281
Peter B. Danzig A cooperative game with applications to computer networks . . . . . . . . . . . 283--289 Franco P. Preparata Inverting a Vandermonde matrix in minimum parallel time . . . . . . . . . 291--294 Robert Kennedy Parallel cardinality stacks and an application . . . . . . . . . . . . . . 295--299 Sandy Irani Two results on the list update problem 301--306 Kenneth Luo and William Klostermeyer and Yuan-Chieh Chow and Richard Newman-Wolfe Optimal deadlock resolutions in edge-disjoint reducible wait-for graphs 307--313 Shahram Latifi Distributed subcube identification algorithms for reliable hypercubes . . . 315--321 Jerzy R. Nawrocki Conflict detection and resolution in a lexical analyzer generator . . . . . . . 323--328 Kieran T. Herley A note on the token distribution problem 329--334 David Zuckerman On the time to traverse all edges of a graph . . . . . . . . . . . . . . . . . 335--337 Dejan Zivkovic A fast algorithm for finding the compact sets . . . . . . . . . . . . . . . . . . 339--342
Robert Nieuwenhuis and Pilar Nivela Efficient deduction in equality Horn logic by Horn-completion . . . . . . . . 1--6 Ronald V. Book On random oracle separations . . . . . . 7--10 Bernadette Charron-Bost Concerning the size of logical clocks in distributed systems . . . . . . . . . . 11--16 Alberto Apostolico and Martin Farach and Costas S. Iliopoulos Optimal superprimitivity testing for strings . . . . . . . . . . . . . . . . 17--20 Jian-er Chen and Jim Cox and Bud Mishra An NL hierarchy . . . . . . . . . . . . 21--26 Ronald A. Olsson and Daniel T. Huang Axiomatic semantics for `escape' statements . . . . . . . . . . . . . . . 27--33 Roberto Tamassia and Ioannis G. Tollis and Jeffrey Scott Vitter Lower bounds for planar orthogonal drawings of graphs . . . . . . . . . . . 35--40 Elena Stöhr Broadcasting in the Butterfly network 41--43 A. P. Sistla Proving correctness with respect to nondeterministic safety specifications 45--49 Fabrizio Luccio and Linda Pagli An efficient algorithm for some tree matching problems . . . . . . . . . . . 51--57
Alex A. Shvartsman Achieving optimal CRCW PRAM fault-tolerance . . . . . . . . . . . . 59--66 Ilan Newman Private vs. common random bits in communication complexity . . . . . . . . 67--71 Amos Omondi Fast one's-complement multiplication . . 73--79 Roberto Grossi A note on the subtree isomorphism for ordered trees and related problems . . . 81--84 Sandy Irani and Ronitt Rubinfeld A competitive $2$-server algorithm . . . 85--91 Jang-Ping Sheu Fault-tolerant parallel $k$ selection algorithm in $n$-cube networks . . . . . 93--97 Abdulla Bataineh and Füsun Özgüner and Alok Sarwal Parallel Boolean operations for information retrieval . . . . . . . . . 99--108 Alessandro Fantechi and Stefania Gnesi and Gioia Ristori Compositionality and bisimulation. A negative result . . . . . . . . . . . . 109--114
Pierre Fraigniaud and Claudine Peyrat Broadcasting in a hypercube when some calls fail . . . . . . . . . . . . . . . 115--119 M. Keil A simple algorithm for determining the envelope of a set of lines . . . . . . . 121--124 K. Qiu and H. Meijer and S. Akl Decomposing a star graph into disjoint cycles . . . . . . . . . . . . . . . . . 125--129 Bing-Chao Huang and Michael A. Langston Stable set and multiset operations in optimal time and space . . . . . . . . . 131--136 Hans Ulrich Simon The Vapnik--Chervonenkis dimension of decision trees with bounded rank . . . . 137--141 Prabhakar Ragde and Avi Wigderson Linear-size constant-depth polylog-threshold circuits . . . . . . . 143--146 Nian Shing Chen and Hwey Pyng Yu and Shing Tsaan Huang A self-stabilizing algorithm for constructing spanning trees . . . . . . 147--151 Paul J. Heffernan The translation square map and approximate congruence . . . . . . . . . 153--159 Janice Jeffs Order independent NCE grammars recognized in polynomial time . . . . . 161--164 M. L. Garg and S. I. Ahson and P. V. Gupta A fuzzy Petri net for knowledge representation and reasoning . . . . . . 165--171
Sandeep Sen Some observations on skip-lists . . . . 173--176 Tatsuya Motoki Inductive inference from all positive and some negative data . . . . . . . . . 177--182 Ji\vrí Matou\vsek Randomized optimal algorithm for slope selection . . . . . . . . . . . . . . . 183--187 D. Roelants van Baronaigien A loopless algorithm for generating binary tree sequences . . . . . . . . . 189--194 Svante Carlsson and Jingsen Chen An optimal parallel adaptive sorting algorithm . . . . . . . . . . . . . . . 195--200 Volker Turau Fixed-radius near neighbors search . . . 201--203 Christos Levcopoulos and Ola Petersson Splitsort---an adaptive sorting algorithm . . . . . . . . . . . . . . . 205--211 Robert J. T. Morris and Wing Shing Wong Systematic choice of initial points in local search. Extensions and application to neural networks . . . . . . . . . . . 213--217 Thomas Hofmeister and Walter Hohberg and Susanne Köhling Some notes on threshold circuits, and multiplication in depth $4$ . . . . . . 219--225 Jeremy P. Spinrad Finding large holes . . . . . . . . . . 227--229
Achim Schweikard Trigonometric polynomials with simple roots . . . . . . . . . . . . . . . . . 231--236 Abhay K. Parekh Analysis of a greedy heuristic for finding small dominating sets in graphs 237--240 Maurizio Tucci and Gennaro Costagliola and Shi-Kuo Chang A remark on NP-completeness of picture matching . . . . . . . . . . . . . . . . 241--243 Dimitris Kavadias and Lefteris M. Kirousis and Paul Spirakis The complexity of the reliable connectivity problem . . . . . . . . . . 245--252 Prabhakar Ragde Analysis of an asynchronous PRAM algorithm . . . . . . . . . . . . . . . 253--256 D. Sreenivasa Rao and John D. Provence An integrated approach to routing and via minimization . . . . . . . . . . . . 257--263 Jan L. A. van de Snepscheut Inversion of a recursive tree traversal 265--267 Coenraad Bron and Wim H. Hesselink Smoothsort revisited . . . . . . . . . . 269--276 Lih-Hsing Hsu and Rong-Hong Jan and Yu-Che Lee and Chun-Nan Hung and Maw-Sheng Chern Finding the most vital edge with respect to minimum spanning tree in weighted graphs . . . . . . . . . . . . . . . . . 277--281 Jae Dong Yang and Yoon Joon Lee A sound and complete query evaluation for Implicit Predicate which is a semantic descriptor of unknown values 283--289
Bernhard von Stengel An algebraic characterization of semantic independence . . . . . . . . . 291--296 Davide Crippa A special case of the dynamization problem for least cost paths . . . . . . 297--302 Jian-er Chen Characterizing parallel hierarchies by reducibilities . . . . . . . . . . . . . 303--307 Rodney R. Howell The complexity of problems involving structurally bounded and conservative Petri nets . . . . . . . . . . . . . . . 309--315 Ricardo A. Baeza-Yates Height balance distribution of search trees . . . . . . . . . . . . . . . . . 317--324 A. Bijlsma Derivation of logic programs by functional methods . . . . . . . . . . . 325--332 Jean Frédéric Myoupo Dynamic programming on linear pipelines 333--341 Michel Raynal and André Schiper and Sam Toueg The causal ordering abstraction and a simple way to implement it . . . . . . . 343--350
P. Crescenzi and C. Fiorini and R. Silvestri A note on the approximation of the MAX CLIQUE problem . . . . . . . . . . . . . 1--5 Reinhold Heckmann Lower and upper power domain constructions commute on all cpos . . . 7--11 Nen Fu Huang and Ching Ho Huang Complexity of the repeaters allocating problem . . . . . . . . . . . . . . . . 13--20 Volker Diekert and Ronald V. Book On ``inherently context-sensitive'' languages---an application of complexity cores . . . . . . . . . . . . . . . . . 21--23 Tao Jiang and B. Ravikumar A note on the space complexity of some decision problems for finite automata 25--31 Maria Cristina Pinotti and Geppino Pucci Parallel priority queues . . . . . . . . 33--40 Thomas Shermer A counterexample to the algorithms for determining opaque minimal forests . . . 41--42 Jean R. S. Blair and Errol L. Lloyd The benefits of external wires in single row routing . . . . . . . . . . . . . . 43--49 Wim H. Hesselink Repetitions, known or unknown? . . . . . 51--57
Ravi Janardan On the dynamic maintenance of maximal points in the plane . . . . . . . . . . 59--64 Victor Yodaiken Modal functions for concise definition of state machines and products . . . . . 65--72 S. Bonnier and U. Nilsson and T. Näslund A simple fixed point characterization of three-valued stable model semantics . . 73--78 V. Pan and J. Reif The parallel computation of minimum cost paths in graphs by stream contraction 79--83 Yi Xian Yang New enumeration results about the optical orthogonal codes . . . . . . . . 85--87 Eric Allender and Vivek Gore Rudimentary reductions revisited . . . . 89--95 R. V. Subramaniyam and A. A. Diwan A counterexample for the sufficiency of edge guards in star polygons . . . . . . 97--99 Xiaodong Wang On the complexity of the extreme points decision problem . . . . . . . . . . . . 101--106 Ruay Shiung Chang Single step graph search problem . . . . 107--111 Jonathan Brandt and Carlos Cabrelli and Ursula Molter An algorithm for the computation of the Hutchinson distance . . . . . . . . . . 113--117
Alok Aggarwal and Prabhakar Raghavan Deferred data structure for the nearest neighbor problem . . . . . . . . . . . . 119--122 Wen-Lian Hsu and Kuo-Hui Tsai Linear time algorithms on circular-arc graphs . . . . . . . . . . . . . . . . . 123--129 Sylvia Boyd and Hasan Ural The synchronization problem in protocol testing and its complexity . . . . . . . 131--136 Shashank Mehta and Maharaj Mukherjee and George Nagy Constrained integer approximation to planar line intersection . . . . . . . . 137--139 M. Abadi and B. Alpern and K. R. Apt and N. Francez and S. Katz and L. Lamport and F. B. Schneider Preserving liveness: comments on ``Safety and liveness from a methodological point of view'' [Inform. Process. Lett. \bf 36(1), 1 October 1990, pp. 25--30] . . . . . . . . . . . 141--142 Frank Dederichs and Rainer Weber Reply to the comments by M. Abadi et al. 143--143 Wen-Huei Chen and Chuan Yi Tang Computing the optimal IO sequences of a protocol in polynomial time . . . . . . 145--148 Richard Brewster and Gary MacGillivray A note on restricted $H$-colouring . . . 149--151 Sukumar Ghosh Binary self-stabilization in distributed systems . . . . . . . . . . . . . . . . 153--159 Joel Wein Las Vegas RNC algorithms for unary weighted perfect matching and $T$-join problems . . . . . . . . . . . . . . . . 161--167 Andrzej Pelc Broadcasting in complete networks with faulty nodes using unreliable calls . . 169--174
Jeffrey K. Uhlmann Satisfying general proximity/similarity queries with metric trees . . . . . . . 175--179 Teofilo F. Gonzalez Covering a set of points in multidimensional space . . . . . . . . . 181--188 Dan Halperin and Micha Sharir On disjoint concave chains in arrangements of (pseudo) lines . . . . . 189--192 Bin Jiang DFS-traversing graphs in a paging environment, LRU or MRU? . . . . . . . . 193--196 Stefan Ronn On the logarithmic evaluation of recurrence relations . . . . . . . . . . 197--199 Do-Hyung Kim and Kwang-Moo Choe Yet another efficient backward execution algorithm in the AND/OR process model 201--211 T. Massart An agent calculus with simple actions where the enabling and disabling are derived operators . . . . . . . . . . . 213--218 F. Cherief and Ph. Schnoebelen $\tau$-Bisimulations and full abstraction for refinement of actions 219--222 Rong Lin Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses . . . . . . . . . . 223--230
Jimmi S. Pettersson Letter to the Editor: Comments on ``Always-true is not invariant'': Assertional reasoning about invariance [Inform. Process. Lett. \bf 35(6), 15 September 1990, pp. 277--279] . . . . . 231--233 Josep Domingo-Ferrer Distributed user identification by zero-knowledge access rights proving . . 235--239 Zhi-Zhong Chen A randomized NC algorithm for the maximal tree cover problem . . . . . . . 241--246 James K. Park A special case of the $n$-vertex traveling-salesman problem that can be solved in ${O(n)}$ time . . . . . . . . 247--254 Roberto Grossi Further comments on the subtree isomorphism for ordered trees: ``On the subtree isomorphism problem for ordered trees'' [Inform. Process. Lett. \bf 32 (1989), no. 5, 271--273; MR 90k:68139] by E. Mäkinen . . . . . . . . . . . . . . 255--256 Rabi N. Mahapatra and Harish Pareek Modelling a fast parallel thinning algorithm for shared memory SIMD computers . . . . . . . . . . . . . . . 257--261 Iain A. Stewart Complete problems for symmetric logspace involving free groups . . . . . . . . . 263--267 Zhou Chaochen and C. A. R. Hoare and Anders P. Ravn A calculus of durations . . . . . . . . 269--276 Sumanta Guha and Arunabha Sen Expected time analysis of interpolation merge --- A simple new merging algorithm 277--281 Ju Yuan Hsiao and Chuan Yi Tang and Ruay Shiung Chang Solving the single step graph searching problem by solving the maximum two-independent set problem . . . . . . 283--287
Miklós Bartha and Éva Gombás A structure theorem for maximum internal matchings in graphs . . . . . . . . . . 289--294 Chang-Biau B. Yang Reducing conflict resolution time for solving graph problems in broadcast communications . . . . . . . . . . . . . 295--302 Ferruccio Barsi Mod $m$ arithmetic in binary systems . . 303--309 Akhil Kumar and Shun Yan Cheung A high availability $\sqrt {N}$ hierarchical grid algorithm for replicated data . . . . . . . . . . . . 311--316 L. Allison and T. I. Dix and C. N. Yee Shortest path and closure algorithms for banded matrices . . . . . . . . . . . . 317--322 Xiaojun Shen and Edward M. Reingold Scheduling on a hypercube . . . . . . . 323--328 Pai-Cheng C. Chu Evaluating clustering factor approach to estimating block selectivities . . . . . 329--334 Subrata Ghosh and Ambuj Mahanti Bidirectional heuristic search with limited resources . . . . . . . . . . . 335--340 Fikret Ercal Distributed evaluation of an iterative function for all object pairs on an SIMD hypercube . . . . . . . . . . . . . . . 341--345
Giuseppe Di Battista and Roberto Tamassia and Ioannis G. Tollis Constrained visibility representations of graphs . . . . . . . . . . . . . . . 1--7 Jeremy Jacob A model of reconfiguration in communicating sequential processes with a notion of transactions . . . . . . . . 9--12 Massimo Ancona and Claudia Fassino and Vittoria Gianuzzi Optimization of LR(k) ``Reduced parsers'' . . . . . . . . . . . . . . . 13--20 M. D. Atkinson and J. R. Sack Generating binary trees at random . . . 21--23 P. David Stotts and Parke Godfrey Place/transition nets with debit arcs 25--33 Jan Pachl A simple proof of a completeness result for leads-to in the UNITY logic . . . . 35--38 Calvin C.-Y. Chen and Sajal K. Das Breadth-first traversal of trees and integer sorting in parallel . . . . . . 39--49 Pradip K. Srimani and Rachamallu L. N. Reddy Another distributed algorithm for multiple entries to a critical section 51--57 Jayadev Misra Corrigenda: ``Phase synchronization'' [Inform. Process. Lett. \bf 38(2), 26 April 1991, pp. 101--105] . . . . . . . 59--59
Youichi Kobuchi Order of state functions and logic functions . . . . . . . . . . . . . . . 61--66 Petr Pavlu On efficient implementation of LR-attributed grammars . . . . . . . . . 67--75 Carlisle M. Adams On immunity against Biham and Shamir's ``differential cryptanalysis'' . . . . . 77--80 Joachim Von Zur Gathen Processor-efficient exponentiation in finite fields . . . . . . . . . . . . . 81--86 Rene Leermakers A recursive ascent Earley parser . . . . 87--91 Xin Yao Finding approximate solutions to NP-hard problems by neural networks is hard . . 93--98 R. C. Chang and H. S. Lee Finding a maximum set of independent chords in a circle . . . . . . . . . . . 99--102 Franz Aurenhammer and Gerd Stöckl Searching for segments with largest relative overlap . . . . . . . . . . . . 103--108 Shing Tsaan Huang and Nian Shing Chen A self-stabilizing algorithm for constructing breadth-first trees . . . . 109--117
Luca Gemignani Fast inversion of Hankel and Toeplitz matrices . . . . . . . . . . . . . . . . 119--123 W. W. Kirchherr Kolmogorov complexity and random graphs 125--130 J. Misra and David Gries A constructive proof of Vizing's theorem 131--133 Thomas C. Shermer A linear algorithm for bisecting a polygon . . . . . . . . . . . . . . . . 135--140 Klaas Esselink Order of Appel's algorithm . . . . . . . 141--147 Alok Aggarwal Parallel complexity of computing a maximal set of disjoint paths . . . . . 149--151 Peter Rajcani Optimal parallel $3$-coloring algorithm for rooted trees and its applications 153--156 Rakesh M. Verma Strings, trees, and patterns . . . . . . 157--161 Kim S. Larsen and Michael I. Schwartzbach and Erik M. Schmidt A new formalism for relational algebra 163--168 Koichi Wada and Yupin Luo and Kimio Kawaguchi Optimal fault-tolerant routings for connected graphs . . . . . . . . . . . . 169--174
Andrzej Sza\las Axiomatizing fixpoint logics . . . . . . 175--180 Dan Gusfield and Gad M. Landau and Baruch Schieber An efficient algorithm for the All Pairs Suffix --- Prefix Problem . . . . . . . 181--185 L. C. Wu and C. Y. Tang Solving the satisfiability problem by using randomized approach . . . . . . . 187--190 Günter Rote and Gerhard Woeginger Counting convex $k$-gons in planar point sets . . . . . . . . . . . . . . . . . . 191--194 Samuel Kamin Head-strictness is not a monotonic abstract property . . . . . . . . . . . 195--198 Samuel R. Buss The graph of multiplication is equivalent to counting . . . . . . . . . 199--201 Jaikumar Radhakrishnan Improved bounds for covering complete uniform hypergraphs . . . . . . . . . . 203--207 Debra Hoover and Joseph Poole A distributed self-stabilizing solution to the dining philosophers problem . . . 209--213 K. Arvind and C. Pandu Ragan Connected domination and Steiner set on weighted permutation graphs . . . . . . 215--220 Mikael Goldmann and Johan Håstad A simple lower bound for monotone clique using a communication game . . . . . . . 221--226 Eva Ma and Bhagirath Narahari and Lixin Tao Optimal embedding of $2$-D torus into ring . . . . . . . . . . . . . . . . . . 227--231
Takayoshi Shoudai A ${P}$-complete language describable with iterated shuffle . . . . . . . . . 233--238 Tom Whaley Alternative developments of cyclic-permutation algorithms . . . . . 239--241 Guorong Wang An improved parallel algorithm for computing the generalized inverse $A^+$ 243--251 Igor Rivin and Ramin Zabih A dynamic programming solution to the $n$-queens problem . . . . . . . . . . . 253--256 Chandrasekhar Narayanaswami and William Randolph Franklin Edge intersection on the hypercube computer . . . . . . . . . . . . . . . . 257--262 Chun Wa Ko and Frank Ruskey Generating permutations of a bag by interchanges . . . . . . . . . . . . . . 263--269 J. Urrutia and F. Gavril An algorithm for fraternal orientation of graphs . . . . . . . . . . . . . . . 271--274 J. Blazewicz and P. Dell'Olmo and M. Drozdowski and M. G. Speranza Scheduling multiprocessor tasks on three dedicated processors . . . . . . . . . . 275--280 Mads Dam $R$-generability, and definability in branching time logics . . . . . . . . . 281--287 Jean Frédéric Myoupo Corrigenda: ``Dynamic programming on linear pipelines'' . . . . . . . . . . . 289--289
Michael Clausen Almost all Boolean functions have no linear symmetries . . . . . . . . . . . 291--292 Fritz Müller Confluence of the lambda calculus with left-linear algebraic rewriting . . . . 293--299 Cengiz Erbas and Murat M. Tanik and Zekeriya Aliyazicioglu Linear congruence equations for the solutions of the $N$-queens problem . . 301--306 L. L. Miller Generating hinges from arbitrary subhypergraphs . . . . . . . . . . . . . 307--312 Javier Esparza A solution to the covering problem for $1$-bounded conflict-free Petri nets using linear programming . . . . . . . . 313--319 Nader H. Bshouty A lower bound for the multiplication of polynomials modulo a polynomial . . . . 321--326 Eliezer L. Lozinskii Counting propositional models . . . . . 327--332 Klaus Jansen An approximation algorithm for the general routing problem . . . . . . . . 333--339 S. D. Carson and V. Nirkhe and P. Vongsathorn A discrete-state model of the two-headed disk . . . . . . . . . . . . . . . . . . 341--345 Jonathan Brandt and Carlos Cabrelli and Ursula Molter Corrigendum: ``An algorithm for the computation of the Hutchinson distance'' [Inform. Process. Lett. \bf 40(2), 25 October 1991, pp. 113--117] . . . . . . 347--347
Erkki Mäkinen On the structural grammatical inference problem for some classes of context-free grammars . . . . . . . . . . . . . . . . 1--5 Ambuj K. Singh Towards an understanding of unbounded variables in asynchronous systems . . . 7--17 L. H. Clark and F. Shahrokhi and L. A. Székely A linear time algorithm for graph partition problems . . . . . . . . . . . 19--24 Helmut Alt and Viliam Geffert and Kurt Mehlhorn A lower bound for the nondeterministic space complexity of context-free recognition . . . . . . . . . . . . . . 25--27 Herbert Fleischner and Gerhard J. Woeginger Detecting cycles through three fixed vertices in a graph . . . . . . . . . . 29--33 Henk Meijer and David Rappaport Computing the minimum weight triangulation of a set of linearly ordered points . . . . . . . . . . . . . 35--38 Arunabha Sen and Abhijit Sen Gupta and Subir Bandyopadhyay On the routing problem in faulty supercubes . . . . . . . . . . . . . . . 39--46 U. K. Sarkar and P. P. Chakrabarti and S. Ghose and S. C. De Sarkar Effective use of memory in iterative deepening search . . . . . . . . . . . . 47--52 Nimrod Megiddo A note on approximate linear programming 53--53 Alok Aggarwal and Herbert Edelsbrunner and Prahakar Raghavan and Prasoon Tiwari Optimal time bounds for some proximity problems in the plane . . . . . . . . . 55--60
Ching-Chih Han and Kwei-Jay Lin Scheduling real-time computations with separation constraints . . . . . . . . . 61--66 Uwe Trier Additive weights of a special class of nonuniformly distributed backtrack trees 67--76 Ronitt Rubinfeld Batch checking with applications to linear functions . . . . . . . . . . . . 77--80 Mike Burmester An almost-constant round interactive zero-knowledge proof . . . . . . . . . . 81--87 Sang Cho and D\~ung T. H\`uynh The parallel complexity of coarsest set partition problems . . . . . . . . . . . 89--94 Brigitte Plateau and Denis Trystam Optimal total exchange for a 3-D torus of processors . . . . . . . . . . . . . 95--102 Jan L. A. Van De Snepscheut A LISP programming exercise . . . . . . 103--108 V. Chandru and J. N. Hooker Detecting embedded Horn structure in propositional logic . . . . . . . . . . 109--111 V. Kamakoti and C. Pandu Rangan An optimal algorithm for reconstructing a binary tree . . . . . . . . . . . . . 113--115 Naveen Gabrani and Priti Shankar A note on the reconstruction of a binary tree from its traversals . . . . . . . . 117--119
Boleslaw K. Szymanski and Balaram Sinharoy Complexity of the closest vector problem in a lattice generated by $(0,1)$-matrix 121--126 Phan Trung Huy and Igor Livotsky and \Dbar\cftilo Long Vân Which finite monoids are syntactic monoids of rational $\omega$-languages 127--132 Kaizhong Zhang and Rick Statman and Dennis Shasha On the editing distance between unordered labeled trees . . . . . . . . 133--139 A. Parker and J. O. Hamblen Optimal value for the Newton--Raphson division algorithm . . . . . . . . . . . 141--144 Ming Li and P. M. B. Vitanyi Average case complexity under the universal distribution equals worst-case complexity . . . . . . . . . . . . . . . 145--149 J. S. Salowe A note on lower bounds for rectilinear Steiner trees . . . . . . . . . . . . . 151--152 Thang Nguyen Bui and Curt Jones Finding good approximate vertex and edge partitions is NP-hard . . . . . . . . . 153--159 Miranda Mowbray Finitary logics for some CCS observational bisimulations . . . . . . 161--165 Jan Friso Groote A short proof of the decidability of bisimulation for normed BPA-processes 167--171 U. K. Sarkar and P. P. Chakrabarti and S. Ghose and S. C. De Sarkar A simple $0.5$-bounded greedy algorithm for the $0/1$ knapsack problem . . . . . 173--177
Tzonelih Hwang Protocols for group oriented secret sharing . . . . . . . . . . . . . . . . 179--182 Avrim Blum Rank-$r$ decision trees are a subclass of $r$-decision lists . . . . . . . . . 183--185 C. Aykanat and F. Ozguner A fault-tolerant hexagonal systolic array . . . . . . . . . . . . . . . . . 187--196 Lin Chen Optimal parallel time bounds for the maximum clique problem on intervals . . 197--201 Ramachandran Vaidyanathan Sorting on PRAMs with reconfigurable buses . . . . . . . . . . . . . . . . . 203--208 Zhiyong Liu and Jia-Huai You An implementation of a nonlinear skewing scheme . . . . . . . . . . . . . . . . . 209--215 Ramachandran Vaidyanathan and Carlos R. P. Hartmann and Pramod K. Varshney PRAMs with variable word-size . . . . . 217--222 C. J. Colbourn and D. R. Stinson and L. Teirlinck A parallelization of Miller's $n^{\log n}$ isomorphism technique . . . . . . . 223--228 Alan P. Sprague and K. H. Kulkarni Optimal parallel algorithms for finding cut vertices and bridges of interval graphs . . . . . . . . . . . . . . . . . 229--234
Khaled Day and Anand Tripathi Arrangement graphs: A class of generalized star graphs . . . . . . . . 235--241 Zhi-Zhong Chen A simple parallel algorithm for computing the diameters of all vertices in a tree and its application . . . . . 243--248 Andrew V. Goldberg A natural randomization strategy for multicommodity flow and related algorithms . . . . . . . . . . . . . . . 249--256 S. K. Wismath Computing the full visibility graph of a set of line segments . . . . . . . . . . 257--261 Jiawei Han Binding propagation beyond the reach of rule/goal graphs . . . . . . . . . . . . 263--268 Bruce Litow On iterated integer product . . . . . . 269--272 G. Wrightson and J. Coldwell A truncation technique for clausal analytic tableaux . . . . . . . . . . . 273--281 S. Singh Expected connectivity and leader election in unreliable networks . . . . 283--285 Helen Cameron and Derick Wood A note on the path length of red-black trees . . . . . . . . . . . . . . . . . 287--292
Glenn K. Manacher and Terrance A. Mankus Incorporating negative-weight vertices in certain vertex-search graph algorithms . . . . . . . . . . . . . . . 293--294 Peter Bro Miltersen Circuit depth relative to a random oracle . . . . . . . . . . . . . . . . . 295--298 Gerhard J. Woeginger and Zhong Liang Yu On the equal-subset-sum problem . . . . 299--302 B. Zhu Computing the shortest diagonal of a monotone polygon in linear time . . . . 303--307 Elias Dahlhaus and Marek Karpi\'nski and Pierre Kelsen An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension $3$ . . . . . . 309--313 Clifford Stein and Joel Wein Approximating the minimum-cost maximum flow is ${P}$-complete . . . . . . . . . 315--319 Samir Khuller and Baruch Schieber On independent spanning trees . . . . . 321--323 Kenichi Morita Computation-universality of one-dimensional one-way reversible cellular automata . . . . . . . . . . . 325--329 Antonio Brogi and Anna Ciampolini and Evelina Lamma and Paolo Mello The implementation of a distributed model for logic programming based on multiple-headed clauses . . . . . . . . 331--338 Eric Goles and Servet Martínez Automata networks and optimization . . . 339--343 Nancy G. Kinnersley The vertex separation number of a graph equals its path-width (NP-complete problem) . . . . . . . . . . . . . . . . 345--350
Sanjeev Saluja A note on the permanent value problem 1--5 Marshall Bern and John R. Gilbert Drawing the planar dual . . . . . . . . 7--13 Barun Chandra Does randomization help in on-line bin packing? . . . . . . . . . . . . . . . . 15--19 Leo Bachmair Associative-commutative reduction orderings . . . . . . . . . . . . . . . 21--27 Stefan Schirra Approximate decision algorithms for approximate congruence . . . . . . . . . 29--34 W. Kern Learning convex bodies under uniform distribution . . . . . . . . . . . . . . 35--39 Li-Hui Tsai An algorithm for flow time minimization and its asymptotic makespan properties 41--46 Mukesh Singhal and Ajay Kshemkalyani An efficient implementation of vector clocks . . . . . . . . . . . . . . . . . 47--52 Elias Koutsoupias and Christos H. Papadimitriou On the greedy algorithm for satisfiability . . . . . . . . . . . . . 53--55
Maurizio Martelli and Chiara Tricomi A new SLDNF-tree . . . . . . . . . . . . 57--62 Yeow Meng Chee and Andrew Lim The algorithmic complexity of colour switching . . . . . . . . . . . . . . . 63--68 F. R. Hsu and R. C. T. Lee and R. C. Chang Special subgraphs of weighted visibility graphs . . . . . . . . . . . . . . . . . 69--75 Su Chu Hsu and Shing Tsaan Huang A self-stabilizing algorithm for maximal matching . . . . . . . . . . . . . . . . 77--81 Tzonelih Hwang Attacks on Okamoto and Tanaka's one-way ID-based key distribution system . . . . 83--86 Arunabha Sen and Haiyong Deng and Sumanta Guha On a graph partition problem with application to VLSI layout . . . . . . . 87--94 Mila E. Majster-Cederbaum Ensuring the existence of a BCNF-decomposition that preserves functional dependencies in $O(N^2)$ time 95--100 Steven Cheung and Francis C. M. Lau Mesh permutation routing with locality 101--105 Ming Li and Paul M. B. Vitányi Optimality of wait-free atomic multiwriter variables . . . . . . . . . 107--112
Oege de Moor Inductive data types for predicate transformers . . . . . . . . . . . . . . 113--117 Sanjeev Saluja and K. V. Subrahmanyam On the power of enumerative counting . . 119--125 Gerhard J. Woeginger Finding the closest extreme vertex to a fixed point . . . . . . . . . . . . . . 127--128 Xiao Qing Liu and Junguk L. Kim An efficient parallel sorting algorithm 129--133 Thomas A. Henzinger Sooner is safer than later (reactive systems) . . . . . . . . . . . . . . . . 135--141 V. I. Galiev and A. F. Polupanov and I. E. Shparlinski Distances from differences of roots of polynomials to the nearest integers . . 143--146 Wojciech Penczek On undecidability of propositional temporal logics on trace systems . . . . 147--153 M. Boreale and P. Inverardi and M. Nesi Complete sets of axioms for finite basic LOTOS behavioural equivalences . . . . . 155--160 V. S. Dimitrov and T. V. Cooklev and B. D. Donevsky On the multiplication of reduced biquaternions and applications . . . . . 161--164 Do-Hyung Kim and Kwang-Moo Choe Corrigenda: ``Yet another efficient backward execution algorithm in the AND/OR Process Model'' [Inform. Process. Lett. \bf 40(4), 25 November 1991, pp. 201--211] . . . . . . . . . . . . . . . 165--165 Boleslaw K. Szymanski and Balaram Sinharoy Corrigenda: ``Complexity of the closest vector problem in a lattice generated by $(0,1)$-matrix'' [Inform. Process. Lett. 42 (1992), no. 3, 121--126; MR 94c:68096] . . . . . . . . . . . . . . . 167--167
Peter Gemmell and Madhu Sudan Highly resilient correctors for polynomials . . . . . . . . . . . . . . 169--174 Jens Palsberg and Michael I. Schwartzbach Safety analysis versus type inference for partial types . . . . . . . . . . . 175--180 Mihail N. Kolountzakis and Kiriakos N. Kutulakos Fast computation of the Euclidian distance maps for binary images . . . . 181--184 Jean-Camille Birget Intersection and union of regular languages and state complexity . . . . . 185--190 Zhi-Zhong Chen A fast and efficient parallel algorithm for finding a satisfying truth assignment to a $2$-${\rm CNF}$ formula 191--193 Tadao Takaoka A new upper bound on the complexity of the all pairs shortest path problem . . 195--199 Ronald I. Greenberg and F. Miller Maley Minimum separation for single-layer channel routing . . . . . . . . . . . . 201--205 L. Allison Lazy dynamic-programming can be eager 207--212 A. Bagchi On sorting in the presence of erroneous information . . . . . . . . . . . . . . 213--215 Daniel P. Huttenlocher and Klara Kedem and Jon M. Kleinberg Vorono\uì diagrams of rigidly moving sets of points . . . . . . . . . . . . . . . 217--223 Katsushi Inoue and Akira It\=o and Itsuo Takanami A relationship between nondeterministic Turing machines and $1$-inkdot Turing machines with small space . . . . . . . 225--227
Ju Yuan Hsiao and Chuan Yi Tang and Ruay Shiung Chang An efficient algorithm for finding a maximum weight $2$-independent set on interval graphs . . . . . . . . . . . . 229--235 Eric J. Schwabe Embedding meshes of trees into de Bruijn graphs . . . . . . . . . . . . . . . . . 237--240 Robin W. Dawes Some pursuit-evasion problems on grids 241--247 R. Satyanarayanan and D. R. Muthukrishnan A note on Raymond's tree based algorithm for distributed mutual exclusion . . . . 249--255 Zbigniew J. Czech and George Havas and Bohdan S. Majewski An Optimal Algorithm for Generating Minimal Perfect Hash Functions . . . . . 257--264 A. S. Pombortsis Analysis of hierarchical bus-based multicomputer architectures . . . . . . 265--270 Eugene K. Ressler Random list permutations in place . . . 271--275 André van Vliet An improved lower bound for on-line bin packing algorithms . . . . . . . . . . . 277--284
Izidor Jerebic and Roman Trobec Optimal routing in toroidal networks . . 285--291 Maw-Shang Chang and Fu-Hsing Wang Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs . . . . . . . . . . . . . . . . . 293--295 Shen Lung Peng and Maw Shang Chang A simple linear time algorithm for the domatic partition problem on strongly chordal graphs . . . . . . . . . . . . . 297--300 D. Scholefield and H. S. M. Zedan Weakest precondition semantics for time and concurrency . . . . . . . . . . . . 301--308 Eliezer A. Albacea A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles . . 309--314 Cheeha Kim and Jong-Sung Kim A mean value analysis of the Ethernet throughput . . . . . . . . . . . . . . . 315--320 Jie Wang A note on two-way probabilistic automata 321--326 Hanxiong Chen and Xu Yu and Kazunori Yamaguchi and Hiroyuki Kitagawa and Nobuo Ohbo and Yuzuru Fujiwara Decomposition --- An approach for optimizing queries including ADT functions . . . . . . . . . . . . . . . 327--333 Torben Hagerup On a compaction theorem of Ragde . . . . 335--340
Soon M. Chung Indexed Extendible Hashing . . . . . . . 1--6 Shigeru Masuyama and Shozo Naito Deciding whether graph ${G}$ has page number one is in NC . . . . . . . . . . 7--10 V. Th. Paschos A $({\Delta}/2)$-approximation algorithm for the maximum independent set problem 11--13 Ming Shing Yu and Cheng-Hsing Yang An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model . . . . . . 15--22 Peter L. Hammer and Alexander Kogan Horn functions and their DNFs . . . . . 23--29 Tzonelih Hwang Efficient ID-based key distribution with tamperfree devices . . . . . . . . . . . 31--34 Shyam Kapur and Gianfranco Bilardi On uniform learnability of language families . . . . . . . . . . . . . . . . 35--38 Vijay K. Garg Some optimal algorithms for decomposed partially ordered sets . . . . . . . . . 39--43 N. Ch. Veeraraghavulu and P. Sreenivasa Kumar and C. E. Veni Madhavan A linear-time algorithm for isomorphism of a subclass of chordal graphs . . . . 45--49 Ahmad Sharary and Nejib Zaguia On a setup optimization problem for interval orders . . . . . . . . . . . . 51--55
Mireille Bousquet-Mélou The number of minimal word chains computing the Thue--Morse word . . . . . 57--64 Paul Gastin and Edward Ochma\'nski and Antoine Petit and Brigitte Rozoy Decidability of the Star Problem in $A* \times \{b\}*$ . . . . . . . . . . . . . 65--71 Bettina De Iaco and Fabrizio Luccio Finding all the palindromes in a binary tree in linear time and space . . . . . 73--77 Ming-Yang Kao and Fang Wan Not all planar digraphs have small cycle separators . . . . . . . . . . . . . . . 79--83 Masakatu Morii and Masao Kasahara Perfect staircase profile of linear complexity for finite sequences . . . . 85--89 Rong Jaye Chen and Yu Song Hou Non-associative parallel prefix computation . . . . . . . . . . . . . . 91--94 Krishnendu Mukhopadhyaya and Bhabani P. Sinha Hamiltonian graphs with minimum number of edges for fault-tolerant topologies 95--99 Kim-Heng Teo and Tai-Ching Tuan An efficient one-side height minimization algorithm for routing around a rectangle . . . . . . . . . . . 101--105 Been-Chian Chien and Wei-Pang Yang The worst case analysis of algorithm on multiple stacks manipulation . . . . . . 107--111
Marco Cadoli The complexity of model checking for circumscriptive formulae . . . . . . . . 113--118 Daniel P. Bovet and Stefano Varricchio On the regularity of languages on a binary alphabet generated by copying systems . . . . . . . . . . . . . . . . 119--123 Erkki Mäkinen Remarks on the structural grammatical inference problem for context-free grammars . . . . . . . . . . . . . . . . 125--127 Jorge Lobo and V. S. Subrahmanian Relating minimal models and pre-requisite-free normal defaults . . . 129--133 James J. Lu and Lawrence J. Henschen The completeness of gp-resolution for annotated logics . . . . . . . . . . . . 135--140 Y. Han and B. Narahari and H.-A. Choi Mapping a chain task to chained processors . . . . . . . . . . . . . . . 141--148 Victor Pan and Akimou Sadikou and Elliott Landowne Polynomial division with a remainder by means of evaluation and interpolation 149--153 Subir Kumar Ghosh and Anil Maheshwari An optimal parallel algorithm for computing furthest neighbors in a tree 155--160 Gerhard J. Woeginger The complexity of finding arborescences in hypergraphs . . . . . . . . . . . . . 161--164 John Bainbridge A heuristic method for generating large random expressions . . . . . . . . . . . 165--170 J. Pachl Corrigendum: ``A simple proof of a completeness result for \em leads-to in the UNITY logic'' [Inform. Process. Lett. \bf 41(1), 21 January 1992, pp. 35--38] . . . . . . . . . . . . . . . . 171--171
Mukesh Dalal and David W. Etherington A hierarchy of tractable satisfiability problems . . . . . . . . . . . . . . . . 173--180 Louxin Zhang The pre-NTS property is undecidable for context-free grammars . . . . . . . . . 181--184 Ke Wang and Li Yan Yuan Preservation of integrity constraints in definite DATALOG programs . . . . . . . 185--193 Tao Jiang and Ming Li and Ding Zhu Du A note on shortest superstrings with flipping . . . . . . . . . . . . . . . . 195--199 Hsun-Wen Chang and Kuo-Liang Chung Fault-tolerant routing in unique-path multistage Omega network . . . . . . . . 201--204 Sanjay Gupta On the closure of certain function classes under integer division by polynomially-bounded functions . . . . . 205--210 Akihisa Tamura and Yoshiko Tamura Degree constrained tree embedding into points in the plane . . . . . . . . . . 211--214 Rafael D. Lins Cyclic reference counting with lazy mark-scan . . . . . . . . . . . . . . . 215--220 Silvano Martello and Paolo Toth A note on $0.5$-bounded greedy algorithms for the $0/1$ knapsack problem . . . . . . . . . . . . . . . . 221--222 Alex A. Shvartsman An efficient Write-All algorithm for fail-stop PRAM without initialized memory . . . . . . . . . . . . . . . . . 223--231
Amihood Amir and Martin Farach Two-dimensional dictionary matching . . 233--239 Jer Shyan Wu and Rong Jaye Chen The Towers of Hanoi problem with parallel moves . . . . . . . . . . . . . 241--243 Jyh-Han Lin and Jeffrey Scott Vitter Approximation algorithms for geometric median problems . . . . . . . . . . . . 245--249 Amotz Bar-Noy and Rajeev Motwani and Joseph Naor The greedy algorithm is optimal for on-line edge coloring . . . . . . . . . 251--253 Fabrizio d'Amore and Paolo Giulio Franciosa On the optimal binary plane partition for sets of isothetic rectangles . . . . 255--259 Mark H. Overmars Point location in fat subdivisions . . . 261--265 Peter Rossmanith and Wojciech Rytter Observations on $\log(n)$ time parallel recognition of unambiguous CFL's . . . . 267--272 Gopal Gupta Dynamic parallel evaluation of the cross-product set using time-stamps . . 273--280 Ronald Greenberg and Joseph JáJá and Sridhar Krishnamurthy On the difficulty of Manhattan channel routing . . . . . . . . . . . . . . . . 281--284 Eliezer Dekel and Jie Hu and Wen Ouyang An optimal algorithm for finding compact sets . . . . . . . . . . . . . . . . . . 285--289
Joost Engelfriet An elementary proof of Double Greibach Normal Form . . . . . . . . . . . . . . 291--293 Uriel Feige On the complexity of finite random functions . . . . . . . . . . . . . . . 295--296 Sundar Vishwanathan An approximation algorithm for the asymmetric travelling salesman problem with distances one and two . . . . . . . 297--302 Lance Fortnow and Márió Szegedy On the power of two-local random reductions . . . . . . . . . . . . . . . 303--306 D. A. Cohen and E. A. Scott Rationality of division orderings . . . 307--311 Adriano Pascoletti An optimal algorithm for the period of a strongly connected digraph . . . . . . . 313--316 Arup Acharya and B. R. Badrinath Recording distributed snapshots based on causal order of message delivery . . . . 317--321 Shai Simonson and I. Hal Sudborough On the complexity of tree embedding problems . . . . . . . . . . . . . . . . 323--328 Hing Leung A note on finitely ambiguous distance automata . . . . . . . . . . . . . . . . 329--331 Gang Luo and Gregor v. Bochmann and Anindya Das and Cheng Wu Failure-equivalent transformation of transition systems to avoid internal actions . . . . . . . . . . . . . . . . 333--343 Dany Breslauer An on-line string superprimitivity test 345--347
Jens Palsberg Normal forms have partial types . . . . 1--3 John F. Dillenburg and Peter C. Nelson Improving the efficiency of depth-first search by cycle elimination . . . . . . 5--10 Vincent A. Fischetti and Gad M. Landau and Peter H. Sellers and Jeanette P. Schmidt Identifying periodic occurrences of a template with applications to protein structure . . . . . . . . . . . . . . . 11--18 Magnús M. Halldórsson A still better performance guarantee for approximate graph coloring . . . . . . . 19--23 Kao Chêng Lin and Maw Sheng Chern The most vital edges in the minimum spanning tree problem . . . . . . . . . 25--31 Jeong Uk Kim and Ho Chang and Tag Gon Kim Multidisk partial match file design with known access pattern . . . . . . . . . . 33--39 Berry Schoenmakers A systematic analysis of splaying . . . 41--50 Ricardo Baeza-Yates and Mireille Regnier Fast two-dimensional pattern matching 51--57
James A. Foster The generic oracle hypothesis is false 59--62 David Cross and Reinhard Drefenstedt and Jorg Keller Reduction of network cost and wiring in Ranade's butterfly routing . . . . . . . 63--67 Andrew Chin Permutations on the Block PRAM . . . . . 69--73 He Jifeng and C. A. R. Hoare From algebra to operational semantics 75--80 S\lawomir Pilarski and Tiko Kameda Simple bounds on the convergence rate of an ergodic Markov chain . . . . . . . . 81--87 Frank Drewes NP-completeness of $k$-connected hyperedge-replacement languages of order $k$ . . . . . . . . . . . . . . . . . . 89--94 Marshall Bern Approximate closest-point queries in high dimensions . . . . . . . . . . . . 95--99 Michael J. Fischer and Shlomo Moran and Gadi Taubenfeld Space-efficient asynchronous consensus without shared memory initialization . . 101--105 Tracy Kimbrel and Rakesh Kumar Sinha A probabilistic algorithm for verifying matrix products using $O(n^2)$ time and $\log_2 n + O(1)$ random bits . . . . . 107--110
Bin Jiang I/O- and CPU-optimal recognition of strongly connected components . . . . . 111--115 Desh Ranjan and Daniela Rus A tool for the analysis of manipulation 117--121 Khaled Day and Anand Tripathi Unidirectional star graphs . . . . . . . 123--129 Cheng Chia Chen and I P'êng Lin The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic . . . . . . . . . . . . . . . . . 131--136 Michael Merritt and Gadi Taubenfeld Speeding Lamport's fast mutual exclusion algorithm . . . . . . . . . . . . . . . 137--142 Maciej Li\'skiewicz On the relationship between deterministic time and deterministic reversal . . . . . . . . . . . . . . . . 143--146 Nancy Amato Improved processor bounds for parallel algorithms for weighted directed graphs 147--152 Suchen H. Hsu and Richard Snodgrass Optimal block size for set-valued attributes . . . . . . . . . . . . . . . 153--158 Francis Suraweera and Prabir Bhattacharya An $O(\log m)$ parallel algorithm for the minimum spanning tree problem . . . 159--163
Marek Raczunas Remarks on the equivalence of $c$-$e$ structures and Petri nets . . . . . . . 165--169 Edmund Ihler and Dorothea Wagner and Frank Wagner Modeling hypergraphs by graphs with the same mincut properties . . . . . . . . . 171--175 Feng Hsu Wang and Ferng-Ching Lin On constructing multiple spanning trees in a hypercube . . . . . . . . . . . . . 177--183 Y. Daniel Liang and Chongkye Rhee Finding a maximum matching in a circular-arc graph . . . . . . . . . . . 185--190 Anastasia Analyti and Sakti Pramanik Performance Analysis of a Main Memory Multi-directory Hashing Technique . . . 191--197 Xiaojun Shen and Qing Hu and Bin Cong and Hal Sudborough and Mike Girou and Said Bettayeb The $4$-star graph is not a subgraph of any hypercube . . . . . . . . . . . . . 199--203 Benny Chor and Eyal Kushilevitz A communication-privacy tradeoff for modular addition . . . . . . . . . . . . 205--210 David A. Rosenblueth An execution mechanism for nondeterministic, state-oriented programs based on a chart parser . . . . 211--217
Michael Buro On the maximum length of Huffman codes 219--223 S. Cheung and F. C. M. Lau A lower bound for permutation routing on two-dimensional bused meshes . . . . . . 225--228 Jeremy P. Spinrad Doubly lexical ordering of dense $0$-$1$ matrices . . . . . . . . . . . . . . . . 229--235 Philipp Hanschke and Jörg Würtz Satisfiability of the smallest binary program . . . . . . . . . . . . . . . . 237--241 A. Bijlsma Quasi-Boolean equivalence . . . . . . . 243--247 Roberto De Prisco and Alfredo De Santis On binary search trees . . . . . . . . . 249--253 Jian Lu Parallelizing Mallat algorithm for $2$-D wavelet transforms . . . . . . . . . . . 255--259 D. T. Lee and E. Papadopoulou The all-pairs quickest path problem . . 261--267 Matthew T. Dickerson and Jason Shugart A simple algorithm for enumerating longest distances in the plane . . . . . 269--274
Jie Wang and Jay Belanger Honest iteration schemes of randomizing algorithms . . . . . . . . . . . . . . . 275--278 Leizhen Cai The recognition of union trees . . . . . 279--283 F\uanic\ua Gavril An efficiently solvable graph partition problem to which many problems are reducible . . . . . . . . . . . . . . . 285--290 James F. Korsh Counting and randomly generating binary trees . . . . . . . . . . . . . . . . . 291--294 Eric J. Schwabe Constant-slowdown simulations of normal hypercube algorithms on the butterfly network . . . . . . . . . . . . . . . . 295--301 Alexander Razborov and Avi Wigderson $n^{\Omega(\log n)}$ lower bounds on the size of depth-$3$ threshold circuits with AND gates at the bottom . . . . . . 303--307 Wen Tsuen Chen and Kuen Rong Hsieh A neural sorting network with $O(1)$ time complexity . . . . . . . . . . . . 309--313 L. Gargano and U. Vaccaro and A. Vozella Fault tolerant routing in the star and pancake interconnection networks . . . . 315--320 Somasundaram Ravindran and Alan Gibbons Dense edge-disjoint embedding of complete binary trees in the hypercube 321--325
Jer Shyan Wu and Rong Jaye Chen The Towers of Hanoi problem with cyclic parallel moves . . . . . . . . . . . . . 1--6 Ming Shing Yu and Lin Yu Tseng and Shoe Jane Chang Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs . . . . . 7--11 G. M. Megson Systolic partitioning algorithms . . . . 13--18 Rafael D. Lins Generational cyclic reference counting 19--20 Ten Hwang Lai and Shu-Shang Wei The Edge Hamiltonian Path Problem is NP-complete for bipartite graphs . . . . 21--26 Yi Xian Yang New binary sequences with perfect staircase profile of linear complexity 27--29 Ramachandran Vaidyanathan and Carlos R. P. Hartmann and Pramod K. Varshney Running ASCEND, DESCEND and PIPELINE algorithms in parallel using small processors . . . . . . . . . . . . . . . 31--36 Kojiro Kobayashi $\Sigma^0_n$-complete properties of programs and Martin-Löf randomness . . . 37--42 Shin Cha and In Sang Chung and Yong Rae Kwon Complexity measures for concurrent programs based on information-theoretic metrics . . . . . . . . . . . . . . . . 43--50 Sang Bong Oh An analytical evidence for Kalé's heuristic for the $N$ queens problem . . 51--54
Chris Ho-Stuart and H. S. M. Zedan and Ming Fang Congruent weak bisimulation with dense real-time . . . . . . . . . . . . . . . 55--61 Hiroshi Ohtsuka A proof of the substitution lemma in de Bruijn's notation . . . . . . . . . . . 63--66 Shlomo Hoory and Avi Wigderson Universal traversal sequences for expander graphs . . . . . . . . . . . . 67--69 Alistair Moffat and Justin Zobel Supporting random access in files of variable length records . . . . . . . . 71--77 Alexander Z. Zelikovsky A faster approximation algorithm for the Steiner tree problem in graphs . . . . . 79--83 Ingo Wegener Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions . . . . . . . 85--87 P. Thangavel and V. P. Muthuswamy Parallel algorithms for addition and multiplication on processor arrays with reconfigurable bus systems . . . . . . . 89--94 Luc Longpré and Sarah Mocas Symmetry of information and one-way functions . . . . . . . . . . . . . . . 95--100 Xiaojun Shen and Qing Hu A note on: ``Minimal visibility graphs'' [Inform. Process. Lett. \bf 37 (1991), no. 1, 49--53; MR 91m:68160] by D. Campbell and J. C. Higgins . . . . . . . 101--101 Fillia Makedon and Dafna Sheinwald and Yaron Wolfsthal A simple linear-time algorithm for the recognition of bandwidth-$2$ biconnected graphs . . . . . . . . . . . . . . . . . 103--107
L. Bianco and J. Blazewicz and P. Dell'Olmo and M. Drozdowski Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness . . . . . . 109--113 Ted Fischer and Andrew V. Goldberg and David J. Haglin and Serge Plotkin Approximating matchings in parallel . . 115--118 Ricard Gavald\`a A positive relativization of polynomial time versus polylog space . . . . . . . 119--123 Gen Huey Chen and Yung Chen Hung On the quickest path problem . . . . . . 125--128 Lung-Tien Liu and Gen-Huey Chen and Kwei-Jay Lin An algorithm for coalescing operations with precedence constraints in real-time systems . . . . . . . . . . . . . . . . 129--133 Robert Davis and Armand Prieditis The expected length of a shortest path 135--141 Shahram Latifi On the fault-diameter of the star graph 143--150 Tadakazu Sato Decidability for some problems of linear cellular automata over finite commutative rings . . . . . . . . . . . 151--155 Vincent A. Fischetti and Gad M. Landau and Jeanette P. Schmidt and Peter H. Sellers Corrigendum: ``Identifying periodic occurrences of a template with applications to protein structure'' . . 157--157
Maxime Crochemore and Leszek G\polhkasieniec and Wojciech Rytter Two-dimensional pattern matching by sampling . . . . . . . . . . . . . . . . 159--162 Ludmila Kuncheva Genetic algorithm for feature selection for parallel classifiers . . . . . . . . 163--168 Magnús M. Halldórsson Approximating the minimum maximal independence number . . . . . . . . . . 169--172 Antoni Mazurkiewicz Distributed Disassembly of Mosaics . . . 173--178 János Demetrovics and Vu Duc Thi Some problems concerning keys for relation schemes and relations in the relational datamodel . . . . . . . . . . 179--184 Marc van Kreveld The power of parallel projection (computational geometry) . . . . . . . . 185--191 Jyh Jong Tsay An efficient implementation of priority queues using fixed-sized systolic coprocessors . . . . . . . . . . . . . . 193--198 Uday Kumar Chakraborty and D. Ghosh Dastidar Using reliability analysis to estimate the number of generations to convergence in genetic algorithms . . . . . . . . . 199--209
A. Bijlsma Calculating with procedure calls . . . . 211--217 George D. Stamoulis and John N. Tsitsiklis An efficient algorithm for multiple simultaneous broadcasts in the hypercube 219--224 Haiko Müller and Falk Nicolai Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs . . . . . . . 225--230 S. C. Chang and M. W. Du Diamond deque: A simple data structure for priority deques . . . . . . . . . . 231--237 Uwe Schoning On random reductions from sparse sets to tally sets . . . . . . . . . . . . . . . 239--241 David S. Wise Stop-and-copy and one-bit reference counting . . . . . . . . . . . . . . . . 243--249 Myoung Ho Kim and Joon Ho Lee and Yoon Joon Lee Analysis of fuzzy operators for high quality information retrieval . . . . . 251--256 Wayne Snyder On the complexity of recursive path orderings . . . . . . . . . . . . . . . 257--262
Krishnaprasad Thirunarayan Locality in inheritance networks . . . . 263--268 Klaus-Uwe Höffgen Computational limitations on training sigmoid neural networks . . . . . . . . 269--274 Fouad B. Chedid and Riad B. Chedid A new variation on hypercubes with smaller diameter . . . . . . . . . . . . 275--280 Martin Middendorf Minimum broadcast time is NP-complete for $3$-regular planar graphs and deadline $2$ . . . . . . . . . . . . . . 281--287 T. Bolognesi Deriving graphical representations of process networks from algebraic expressions . . . . . . . . . . . . . . 289--294 Arne Andersson and Stefan Nilsson Improved behaviour of tries by adaptive branching . . . . . . . . . . . . . . . 295--300 E. M. Clarke and I. A. Draghicescu and R. P. Kurshan A unified approach for showing language inclusion and equivalence between various types of $\omega$-automata . . . 301--308 Helmut Prodinger and Wojciech Szpankowski A note on binomial recurrences arising in the analysis of algorithms . . . . . 309--311
Sivan Toledo Approximate parametric searching . . . . 1--4 Boris Teia A lower bound for randomized list update algorithms . . . . . . . . . . . . . . . 5--9 Pierluigi Crescenzi and Riccardo Silvestri A note on the descriptive complexity of maximization problems . . . . . . . . . 11--15 Olumide Owolabi Efficient pattern searching over large dictionaries . . . . . . . . . . . . . . 17--21 John Hershberger A faster algorithm for the two-center decision problem . . . . . . . . . . . . 23--29 Michael Meskes and Jörg Noack The generalized supplementary magic-sets transformation for stratified Datalog 31--41 Wen Huei Chen and Chuan Yi Tang A $2\cdot{}\vert E\vert$-bit distributed algorithm for the directed Euler trail problem . . . . . . . . . . . . . . . . 43--49 Dany Breslauer and Livio Colussi and Laura Toniolo Tight comparison bounds for the string prefix-matching problem . . . . . . . . 51--57
Jürgen Dassow and Gheorghe P\uaun and Arto Salomaa On the union of 0L languages . . . . . . 59--63 Robert Nieuwenhuis Simple LPO constraint solving methods 65--69 Greg N. Frederickson and Susanne E. Hambrusch and Hung Yi Tu Shortest path computations in source-deplanarized graphs . . . . . . . 71--75 Éva Tardos and Vijay V. Vazirani Improved bounds for the max-flow min-multicut ratio for planar and $K_{r,r}$-free graphs . . . . . . . . . 77--80 Sanjay Jain and Arun Sharma On the non-existence of maximal inference degrees for language identification . . . . . . . . . . . . . 81--88 Ming Shing Yu and Cheng-Hsing Yang An ${O(n)}$ time algorithm for maximum matching on cographs . . . . . . . . . . 89--93 Christophe Hancart On Simon's string searching algorithm 95--99 Sang Ho Lee and Lawrence J. Henschen Semantics and properties of existential quantifiers in deductive databases . . . 101--108 Heonchul Park and Hyoung Joong Kim and Viktor K. Prasanna An $O(1)$ time optimal algorithm for multiplying matrices on reconfigurable mesh . . . . . . . . . . . . . . . . . . 109--113
Matthew J. Katz and Micha Sharir Optimal slope selection via expanders 115--122 Heung-Chul Shin and Kwang-Moo Choe An improved ${\rm LALR}(k)$ parser generation for regular right part grammars . . . . . . . . . . . . . . . . 123--129 Iréne Durand and Bruno Salinier Constructor equivalent term rewriting systems . . . . . . . . . . . . . . . . 131--137 K. Gopalakrishnan and D. G. Hoffman and D. R. Stinson A note on a conjecture concerning symmetric resilient functions . . . . . 139--143 Carlo Luchetti and M. Cristina Pinotti Some comments on building heaps in parallel . . . . . . . . . . . . . . . . 145--148 Byeong-Mo Chang and Kwang-Moo Choe and Taisook Han Efficient bottom-up execution of logic programs using abstract interpretation 149--157 Jonathan D. Bright Range-restricted mergeable priority queues . . . . . . . . . . . . . . . . . 159--164 George Steiner and Scott Yeomans A note on: ``Scheduling unit-time tasks with integer release times and deadlines'' [Inform. Process. Lett. \bf 16 (1983), no. 4, 171--173; MR 84m:68030] by G. Frederickson . . . . . 165--166
Andrew Lim and Yeow Meng Chee and Siu Wing Cheng Single jog minimum area joining of compacted cells . . . . . . . . . . . . 167--172 Michael Luby and Alistair Sinclair and David Zuckerman Optimal speedup of Las Vegas algorithms 173--180 C.- Z. Xu and F. C. M. Lau Optimal parameters for load balancing using the diffusion method in $k$-ary $n$-cube networks . . . . . . . . . . . 181--187 In Sig Yun and Kwang Moo Choe and Taisook Han Syntactic error repair using repair patterns . . . . . . . . . . . . . . . . 189--196 Yi-Bing Lin Parallel trace-driven simulation of packet-switched multiplexer under priority scheduling policy . . . . . . . 197--201 Eric T. Bax Inclusion and exclusion algorithm for the Hamiltonian Path Problem . . . . . . 203--207 Subir Bhattacharya and A. Bagchi A faster alternative to SSS* with extension to variable memory . . . . . . 209--214 D. S. Hirschberg and S. S. Seiden A bounded-space tree traversal algorithm 215--219
Myung Soo Kim and Jae-Woo Ahn and Soon-Bum Lim An algebraic algorithm to compute the exact general sweep boundary of a $2$D curved object . . . . . . . . . . . . . 221--229 Nageswara S. V. Rao and Ching Luo On similarity of polynomial configurations . . . . . . . . . . . . . 231--236 Byeong-Mo Chang and Kwang-Moo Choe and Taisook Han Static filtering on stratified programs 237--244 Woo-Jun Park and Myung-Joon Lee and Kwang-Moo Choe On the reduction of ${\rm LR}(k)$ parsers . . . . . . . . . . . . . . . . 245--251 Laurent Alonso and Edward M. Reingold and René Schott Determining the majority . . . . . . . . 253--255 Nalvo F. de Almeida, Jr. and Valmir C. Barbosa A string-matching algorithm for the CREW PRAM . . . . . . . . . . . . . . . . . . 257--259 Himabindu Gurla Leftmost one computation on meshes with row broadcasting . . . . . . . . . . . . 261--266 Ramachandran Vaidyanathan and Jerry L. Trahan Optimal simulation of multidimensional reconfigurable meshes by two-dimensional reconfigurable meshes . . . . . . . . . 267--273
Esther M. Arkin and Magnús M. Halldórsson and Refael Hassin Approximating the tree and tour covers of a graph . . . . . . . . . . . . . . . 275--282 Danny Krizanc Integer sorting on a mesh-connected array of processors . . . . . . . . . . 283--289 H. Peter Gumm Another glance at the Alpern-Schneider characterization of safety and liveness in concurrent executions . . . . . . . . 291--294 Zhizhang Shen Static behavior analysis of a mesh system . . . . . . . . . . . . . . . . . 295--299 Johan Håstad and Steven Phillips and Shmuel Safra A well-characterized approximation problem . . . . . . . . . . . . . . . . 301--305 R. T. Udink and J. N. Kok Unity properties and sequences of states, some observations . . . . . . . 307--311 Martin Hühne Linear speed-up does not hold on Turing machines with tree storages . . . . . . 313--318 Peter Eades and Xuemin Lin and W. F. Smyth A fast and effective heuristic for the feedback arc set problem . . . . . . . . 319--323 Danny Z. Chen and Sumantha Guha Testing a simple polygon for monotonicity optimally in parallel . . . 325--331
C. V. Hall Using overloading to express distinctions between evaluators . . . . 1--8 Adam L. Buchsbaum and Martin C. Carlisle Determining uni-connectivity in directed graphs . . . . . . . . . . . . . . . . . 9--12 Nabil I. Hachem An Approximate Analysis of the Performance of Extendible Hashing with Elastic Buckets . . . . . . . . . . . . 13--20 Mohan Ahuja Assertions about past and future in \em Highways: Global flush broadcast and flush-vector-time . . . . . . . . . . . 21--28 Daniel M. Yellin and Charanjit S. Jutla Finding extremal sets in less than quadratic time . . . . . . . . . . . . . 29--34 Tzonelih Hwang Scheme for secure digital mobile communications based on symmetric key cryptography . . . . . . . . . . . . . . 35--37 J. Santos and J. Orozco Rate monotonic scheduling in hard real-time systems . . . . . . . . . . . 39--45 Ming Shing Yu and Cheng Hsing Yang A simple optimal parallel algorithm for the minimum coloring problem on interval graphs . . . . . . . . . . . . . . . . . 47--51
Howard Karloff Fast algorithms for approximately counting mismatches . . . . . . . . . . 53--60 Daniele Pretolani A linear time algorithm for unique Horn satisfiability . . . . . . . . . . . . . 61--66 Wuu Yang An incremental LL(1) parsing algorithm 67--72 M. D. Atkinson and Louise Walker Enumerating $k$-way trees . . . . . . . 73--75 Mike Steel and Tandy Warnow Kaikoura tree theorems: Computing the maximum agreement subtree . . . . . . . 77--82 Stefan Gärtner A remark on the regulation of $k$lETOL systems . . . . . . . . . . . . . . . . 83--85 Donald D. Chinn and Rakesh K. Sinha Bounds on sample space size for matrix product verification . . . . . . . . . . 87--91 Sanjay Gupta On bounded-probability operators and ${\rm C}_={\rm P}$ . . . . . . . . . . . 93--98 Stefan Voss Worst-case performance of some heuristics for Steiner's problem in directed graphs . . . . . . . . . . . . 99--105
Yeonghwan Tscha and Yanghee Choi and Kyoon Ha Lee Rearrangeable nonblocking condition for multi-$\log_2N$ multiconnection networks 107--112 Nimish R. Shah A parallel algorithm for constructing projection polyhedra . . . . . . . . . . 113--119 Ee-Chien Chang and Weiguo Wang and Mohan S. Kankanhalli Multidimensional on-line bin-packing: an algorithm and its average-case analysis 121--125 Satoshi Fujita and Masafumi Yamashita Fast gossiping on square mesh computers 127--130 Debra A. Hensgen and David L. Sims and David Charley A fair Banker's Algorithm for read and write locks . . . . . . . . . . . . . . 131--137 Detlef Sieling and Ingo Wegener Reduction of OBDDs in linear time . . . 139--144 K. V. S. Ramarao and S. Venkatesan The lower bounds on distributed shortest paths . . . . . . . . . . . . . . . . . 145--149 Hachemi Bennaceur and Gérard Plateau An exact algorithm for the constraint satisfaction problem: application to logical inference . . . . . . . . . . . 151--158
C. M. Khoong Optimal parallel construction of heaps 159--161 DongGill Lee and Kwang-Moo Choe and Taisook Han A description of dynamic behavior for compilers based on object oriented modeling . . . . . . . . . . . . . . . . 163--170 Georg Reichwein and José Luiz Fiadeiro Models for the substitution axiom of UNITY logic . . . . . . . . . . . . . . 171--176 Ying Teh Tsai and Chuan Yi Tang The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems . . . . . 177--182 Z. Fülöp and P. Gyenizse On injectivity of deterministic top-down tree transducers . . . . . . . . . . . . 183--188 Kian-Lee Tan and Hongium Lu On resource scheduling of multi-join queries in parallel database systems . . 189--195 Michael S. Paterson and Heiko Schröder and Ondrej Sýkora and Imrich V\vr\softto A short proof of the dilation of a toroidal mesh in a path . . . . . . . . 197--199 Harry Buhrman and Leen Torenvliet and Peter van Emde Boas Twenty questions to a $p$-selector . . . 201--204 Maw Shang Chang and Yi Chang Liu Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs . . . . . . . . 205--210
Kazuo Iwano and Naoki Katoh Efficient algorithms for finding the most vital edge of a minimum spanning tree . . . . . . . . . . . . . . . . . . 211--213 Theodore Johnson and Krishna Harathi A simple correctness proof of the MCS contention-free lock . . . . . . . . . . 215--220 Dana L. Grinstead and Peter J. Slater and Naveed A. Sherwani and Nancy D. Holmes Efficient edge domination problems in graphs . . . . . . . . . . . . . . . . . 221--228 Lydia Kavraki and Jean-Claude Latombe and Randall H. Wilson On the complexity of assembly partitioning . . . . . . . . . . . . . . 229--235 Jang Ping Sheu and Wen Hwa Liaw and Tzung Shi Chen A broadcasting algorithm in star graph interconnection networks . . . . . . . . 237--241 Yordan Rouskov and Pradip K. Srimani Fault diameter of star graphs . . . . . 243--251 Mordecia J. Golin and Robert Sedgewick Queue-mergesort . . . . . . . . . . . . 253--259 Alain Billionnet Partitioning multiple-chain-like task across a host- satellite system . . . . 261--266
Karel Culik, II and Jarkko Kari Parametrized recurrent systems for image generation . . . . . . . . . . . . . . . 267--274 Marion Rodrigues and Hasan Ural Exact solutions for the construction of optimal length test sequences . . . . . 275--280 Millist W. Vincent and Bala Srinivasan A note on relation schemes which are in $3$NF but not in BCNF . . . . . . . . . 281--283 Katsushi Inoue and Akira It\=o and Itsuo Takanami and Tsunehiro Yoshinaga A note on multi-inkdot nondeterministic Turing machines with small space . . . . 285--288 Krishnan Pillaipakkamnatt and Vijay Raghavan A linear time equivalence test for read-twice DNF formulas . . . . . . . . 289--295 Pierre Fraigniaud and Claire Kenyon and Andrzej Pelc Finding a target subnetwork in sparse networks with random faults . . . . . . 297--303 Olivier Goldschmidt and Dorit S. Hochbaum and Gang Yu A modified greedy heuristic for the Set Covering problem with improved worst case bound . . . . . . . . . . . . . . . 305--310 Peter Dankelmann Computing the average distance of an interval graph . . . . . . . . . . . . . 311--314 Kevin I.-J. Ho and Joseph Y.-T. Leung and W.-D. Wei Complexity of scheduling tasks with time-dependent execution times . . . . . 315--320
Vittoria Gianuzzi Distributed termination detection in reducible communication graphs . . . . . 1--8 Esko Nuutila and Eljas Soisalon-Soininen On finding the strongly connected components in a directed graph . . . . . 9--14 Mikael Goldmann and Per Grape and Johan Håstad On average time hierarchies (Turing machines) . . . . . . . . . . . . . . . 15--20 Kanchana Kanchanasut A shortest-path algorithm for Manhattan graphs . . . . . . . . . . . . . . . . . 21--25 Mounir Belbaraka and Ivan Stojmenovi\'c On generating $B$-trees with constant average delay and in lexicographic order 27--32 D. Veljan Computing values of a polynomial with only few multiplications . . . . . . . . 33--37 Hing F. Ting and Andrew C. Yao A randomized algorithm for finding maximum with $O((\log n)^2)$ polynomial tests . . . . . . . . . . . . . . . . . 39--43 C. Rhee and Y. Daniel Liang and S. K. Dhall and S. Lakshmivarahan Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs . . . . . . 45--50 Haim Kaplan and Ron Shamir The domatic number problem on some perfect graph families . . . . . . . . . 51--56
Gurdip Singh Real-time leader election . . . . . . . 57--61 Min-Soo Jung and Kwang-Moo Choe and Taisook Han An efficient computation of right context for LR-based error repair . . . 63--71 Sanjeev Saxena Two-coloring linked lists is ${\rm NC}^1$-complete for logarithmic space 73--76 Peter Gemmell and Mor Harchol Tight bounds on expected time to add correctly and add mostly correctly . . . 77--83 Joachim Steinbach Generating polynomial orderings . . . . 85--93 Harry G. Mairson Generating words in a context-free language uniformly at random . . . . . . 95--99 Jan Willem Klop and Aart Middeldorp and Yoshihito Toyama and Roel de Vrijer Modularity of confluence: A simplified proof . . . . . . . . . . . . . . . . . 101--109
Amihood Amir and Martin Farach and S. Muthukrishnan Alphabet dependence in parameterized matching . . . . . . . . . . . . . . . . 111--115 Sung Kwon Kim The range co-minima problem . . . . . . 117--121 M. Ladermann and H. Petersen Notes on looping deterministic two-way pushdown automata . . . . . . . . . . . 123--127 Tze Fen Li and Sung Wu Chang An algorithm to estimate the fraction defective and the exponential mean life using unlabeled samples . . . . . . . . 129--133 Yukio Shibata and Miyuki Shirahata and Shingo Osawa Counting closed walks in generalized de Bruijn graphs . . . . . . . . . . . . . 135--138 B. S. Panda and S. P. Mohanty Recognition algorithm for intersection graphs of edge disjoint paths in a tree 139--143 Zoran Jovanovi\'c and Jelena Mi\vsi\'c Fault tolerance of the star graph interconnection network . . . . . . . . 145--150 Maria Luisa Bonet and Samuel R. Buss Size-depth tradeoffs for Boolean formulae . . . . . . . . . . . . . . . . 151--155 S. B. Yang and S. K. Dhall and S. Lakshmivarahan A processor efficient MIS algorithm on random graphs . . . . . . . . . . . . . 157--163
Chien-Min M. Wang A new routing algorithm for cyclic shifts on BRGC hypercubes . . . . . . . 165--169 Nen-Fu F. Huang and Ching-Ho H. Huang and Yue-Li L. Wang A sweepline algorithm to solve the two-center problem . . . . . . . . . . . 171--177 Aldo de Luca and Licia Mione On bispecial factors of the Thue--Morse word . . . . . . . . . . . . . . . . . . 179--183 John H. Leuchner and Les Miller and Giora Slutzki A note on the equivalence of a set of egds to a set of FDs . . . . . . . . . . 185--188 Ken Calvert Eliminating disjunctions of leads-to properties (temporal logic) . . . . . . 189--194 Gil Neiger Distributed Consensus revisited . . . . 195--201 Dongseung Kim and Joonyoung Park Two-way dominant sequence clustering for processor scheduling . . . . . . . . . . 203--208 Eddie Cheng and William H. Cunningham A faster algorithm for computing the strength of a network . . . . . . . . . 209--212 Hirotsugu Kakugawa and Satoshi Fujita and Masafumi Yamashita and Tadashi Ae A distributed $k$-mutual exclusion algorithm using $k$-coterie . . . . . . 213--218
Roni Khardon On using the Fourier transform to learn Disjoint DNF . . . . . . . . . . . . . . 219--222 Wolfgang J. Paul A note on bitonic sorting . . . . . . . 223--225 Michiel C. Van Wezel and Gerard Tel An assertional proof of Rana's algorithm 227--233 Dany Breslauer Testing string superprimitivity in parallel . . . . . . . . . . . . . . . . 235--241 Prasoon Tiwari and Martin Tompa A direct version of Shamir and Snir's lower bounds on monotone circuit depth 243--248 Kaizhong Zhang and Tao Jiang Some MAX SNP-hard results concerning unordered labeled trees . . . . . . . . 249--254 Mihail N. Kolountzakis Selection of a large sum-free subset in polynomial time . . . . . . . . . . . . 255--256 Lih-Chyau Wuu and Shing-Tsaan Huang Identity assignment in uniform synchronous rings . . . . . . . . . . . 257--262 Sriram V. Pemmaraju and Clifford A. Shaffer Analysis of the worst case space complexity of a PR quadtree . . . . . . 263--267 J. B\la\.zewicz and P. Dell'Olmo and M. Drozdowski and M. G. Speranza Corrigendum: ``Scheduling multiprocessor tasks on three dedicated processors'' [Inform. Process. Lett. \bf 41 (1992), no. 5, 275--280] . . . . . . . . . . . . 269--270
Gerard Tel Maximal matching stabilizes in quadratic time . . . . . . . . . . . . . . . . . . 271--272 Leonid Libkin and Limsoon Wong Conservativity of nested relational calculi with internal generic functions 273--280 Victor Chepoi and Feodor Dragan Computing a median point of a simple rectilinear polygon . . . . . . . . . . 281--285 Al Borchers and Prosenjit Gupta Extending the quadrangle inequality to speed-up dynamic programming . . . . . . 287--290 Sergio Rajsbaum Upper and lower bounds for stochastic marked graphs . . . . . . . . . . . . . 291--295 Zeev Collin and Shlomi Dolev Self-stabilizing depth-first search . . 297--301 G. Sajith and Sanjeev Saxena Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees 303--308 Viggo Kann Maximum bounded $H$-matching is Max SNP-complete . . . . . . . . . . . . . . 309--318 H. N. Reddy and E. L. Leiss An $O(\log N)$ algorithm to solve linear recurrences on hypercubes . . . . . . . 319--325 Helmut Prodinger An asymptotic comment on a paper by A. Analyti and S. Pramanik: ``Performance analysis of a main memory multi-directory hashing technique'' [Inform. Process. Lett. \bf 45 (1993), no. 4, 191--197; MR 93k:68026] . . . . . 327--328
Ferruccio Barsi and M. Cristina Pinotti A fully parallel algorithm for residue to binary conversion . . . . . . . . . . 1--8 Y. Azar and A. Z. Broder and A. M. Frieze On the problem of approximating the number of bases of a matroid . . . . . . 9--11 Yi-Bing Lin Determining the global progress of parallel simulation with FIFO communication property . . . . . . . . . 13--17 Marc Demange and Pascal Grisoni and Vangelis Th. Paschos Approximation results for the minimum graph coloring problem . . . . . . . . . 19--23 Aviezri S. Fraenkel and Edward M. Reingold and Prashant Saxena Efficient management of dynamic tables 25--30 Pierre Collette An explanatory presentation of composition rules for assumption-commitment specifications . . 31--35 Jennifer Seberry and Xian Mo Zhang and Yuliang Zheng Improving the strict avalanche characteristics of cryptographic functions . . . . . . . . . . . . . . . 37--41 Yong-Seok Kim An optimal scheduling algorithm for preemptable real-time tasks . . . . . . 43--48 Samir Khuller and Balaji Raghavachari and Neal Young Designing multi-commodity flow trees . . 49--55
Frédéric Maire Polyominos and perfect graphs . . . . . 57--61 P. Ferragina Static and dynamic parallel computation of connected components . . . . . . . . 63--68 Her-Kun Chang and Shyan-Ming Yuan Message complexity of hierarchical quorum consensus algorithm . . . . . . . 69--73 T. Sony Roy and G. Athithan and M. S. Ganagi and A. Sivasankara Reddy A new method to solve non-linear equations . . . . . . . . . . . . . . . 75--79 Narsingh Deo and Amit Jain and Muralidhar Medidi An optimal parallel algorithm for merging using multiselection . . . . . . 81--87 Y. L. Chen Finding the $k$ quickest simple paths in a network . . . . . . . . . . . . . . . 89--92 Giovanni Di Crescenzo and Giuseppe Persiano Round-optimal perfect zero-knowledge proofs . . . . . . . . . . . . . . . . . 93--99 Rani Siromoney and Lisa Mathew and V. R. Dare and K. G. Subramanian Infinite Lyndon words . . . . . . . . . 101--104 Rahul Simha and Amitava Majumdar On lookahead in the list update problem 105--110 Himabindu Gurla Leftmost one computation on meshes with row broadcasting . . . . . . . . . . . . 111--111
Yair Bartal and Howard Karloff and Yuval Rabani A better lower bound for on-line scheduling . . . . . . . . . . . . . . . 113--116 Etsuro Moriya On two-way tree automata . . . . . . . . 117--121 Paul F. Dietz and Ioan I. Macarie and Joel I. Seiferas Bits and relative order from residues, space efficiently . . . . . . . . . . . 123--127 Dongseung Kim and Seung-Hoon Kim ${O}(\log n)$ numerical algorithms on a mesh with wormhole routing . . . . . . . 129--136 Bob P. Weems and Lloyd C. Swayze Allocation techniques for distributed reduction data elements . . . . . . . . 137--142 Yuzheng Ding and Mark Allen Weiss On the complexity of building an interval heap . . . . . . . . . . . . . 143--144 G. Prem Kumar and G. Phanendra Babu Optimal network partitioning for fault-tolerant network management using evolutionary programming . . . . . . . . 145--149 Dhananjay M. Dhamdhere and Sandeep S. Kulkarni A token based $k$-resilient mutual exclusion algorithm for distributed systems . . . . . . . . . . . . . . . . 151--157 Li Yan Yuan Logic program semantics and circumscription of autoepistemic theories . . . . . . . . . . . . . . . . 159--164 R. Baldoni and B. Ciciani Distributed algorithms for multiple entries to a critical section with priority . . . . . . . . . . . . . . . . 165--172
K\=okichi Sugihara Simpler proof of a realizability theorem on Delaunay triangulations . . . . . . . 173--176 R. F. Resende and A. El Abbadi On the serializability theorem for nested transactions . . . . . . . . . . 177--183 R. Ravi A primal-dual approximation algorithm for the Steiner forest problem . . . . . 185--189 Udi Manber and Sun Wu An algorithm for approximate membership checking with application to password security . . . . . . . . . . . . . . . . 191--197 Jaikumar Radhakrishnan and K. V. Subrahmanyam Directed monotone contact networks for threshold functions . . . . . . . . . . 199--203 Chandrasekhar Narayanaswami and William Luken Approximating $x^n$ efficiently . . . . 205--210 Sorin Istrail and Dejan Zivkovic Bounded-width polynomial-size Boolean formulas compute exactly those functions in ${\rm AC}^0$ . . . . . . . . . . . . 211--216 Simon Y. Berkovich Multiprocessor interconnection network using pairwise balanced combinatorial designs . . . . . . . . . . . . . . . . 217--222 Yi-Min Wang and Andy Lowry and W. Kent Fuchs Consistent global checkpoints based on direct dependency tracking . . . . . . . 223--230
Giovanni Manzini Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results . . . . . 231--238 Dennis Moore and W. F. Smyth An optimal algorithm to compute all the covers of a string . . . . . . . . . . . 239--246 Mitchell L. Neilsen and Masaaki Mizuno Nondominated $k$-coteries for multiple mutual exclusion . . . . . . . . . . . . 247--252 Huade Li Trajectory planning in $H$-space . . . . 253--258 Xubo Zhang and Z. Meral Özsoyo\vglu Some results on the containment and minimization of (in)equality queries . . 259--267 Chris H. Perleberg Single character searching methods and the shift-or pattern-matching algorithm 269--275 Shuji Jimbo and Akira Maruoka On the relationship between the diameter and the size of a boundary of a directed graph . . . . . . . . . . . . . . . . . 277--282 Abraham P. Punnen and K. P. K. Nair A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem . . . . . . . . . . . . . . . . 283--286
Anonymous IPL's policy on complexity results . . . 287--287 Alberto Bertoni and Carlo Mereghetti and Giovanni Pighizzini An optimal lower bound for nonregular languages . . . . . . . . . . . . . . . 289--292 Giuseppe Pirillo Infinite words and biprefix codes . . . 293--295 Chiu-Chuan Lin and Ferng-Ching Lin Minimal fully adaptive wormhole routing on hypercubes . . . . . . . . . . . . . 297--301 José Fortes Gálvez A note on a proposed LALR parser for extended context-free grammars . . . . . 303--305 Matti Nykänen and Esko Ukkonen Finding lowest common ancestors in arbitrarily directed trees . . . . . . . 307--310 Sridhar Alagar and S. Venkatesan An optimal algorithm for distributed snapshots with causal message ordering 311--316 Jordan Gergov and Christoph Meinel On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs . . . . . . . . 317--322 M. D. Atkinson and J.-R. Sack Uniform generation of forests of restricted height . . . . . . . . . . . 323--327 David A. Naumann A recursion theorem for predicate transformers on inductive data types . . 329--336 Linda Pagli and Geppino Pucci Counting the number of fault patterns in redundant VLSI arrays . . . . . . . . . 337--342
Krzysztof Diks and Evangelos Kranakis and Danny Krizanc and Bernard Mans and Andrzej Pelc Optimal coteries and voting schemes . . 1--6 Meena Mahajan and Thomas Thierauf and N. V. Vinodchandran A note on SpanP functions . . . . . . . 7--10 Zhaofang Wen New algorithms for the LCA problem and the binary tree reconstruction problem 11--16 Shuji Jimbo and Akira Maruoka On the relationship between $\epsilon$-biased random variables and $\epsilon$-dependent random variables 17--23 Ling Chen and Henry Y. H. Chuang A fast algorithm for Euclidean distance maps of a $2$-D binary image . . . . . . 25--29 Joseph Gil and Yossi Matias Designing algorithms by expectations . . 31--34 Yoshihide Igarashi and Shingo Osawa and Walter Unger Automorphisms of broadcasting schemes with respect to start rounds . . . . . . 35--41 Antonia Sinachopoulos Logics and decidability for labelled pre- and partially-ordered Kripke structures . . . . . . . . . . . . . . . 43--52 Dan Halperin and Micha Sharir Corrigendum: ``On disjoint concave chains in arrangements of (pseudo) lines'' [Inform. Process. Lett. \bf 40 (1991), no. 4, 189--192; MR 92m:52029] 53--56
Norbert Blum and Henning Rochow A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals . . . . 57--60 David A. Basin A term equality problem equivalent to Graph Isomorphism . . . . . . . . . . . 61--66 Michael Frazier and C. David Page, Jr. Prefix grammars: An alternative characterization of the regular languages . . . . . . . . . . . . . . . 67--71 Simon R. Blackburn Increasing the rate of output of $m$-sequences . . . . . . . . . . . . . 73--77 Edith Hemaspaandra Census techniques collapse space classes 79--84 Eun-Jung Lee and Kwang-Moo Choe Grammar coverings of a deterministic parser with action conflicts . . . . . . 85--92 Abhijit Sengupta and Suresh Viswanathan On fault-tolerant fixed routing in hypercubes . . . . . . . . . . . . . . . 93--99 Gianfranco Bilardi and Shiva Chaudhuri and Devdatt Dubhashi and K. Mehlhorn A lower bound for area-universal graphs 101--105 Peter Kirrinnis An optimal bound for path weights in Huffman trees . . . . . . . . . . . . . 107--110
Mark Jerrum Counting trees in a graph is $\#{\rm P}$-complete . . . . . . . . . . . . . . 111--116 Erl Huei Lu and Yi Chang Chen and Hsiao Peng Wuu A complete decoding algorithm for double-error-correcting primitive binary BCH codes of odd $m$ . . . . . . . . . . 117--120 K. S. Easwarakumar and C. Pandu Rangan and G. A. Cheston A linear algorithm for centering a spanning tree of a biconnected graph . . 121--124 Vinnakota Bapiraju and V. V. Bapeswara Rao Enumeration of binary trees . . . . . . 125--127 Wen Chin Chen and Wen Chun Ni Internal path length of the binary representation of heap-ordered trees . . 129--132 Refael Hassin and Shlomi Rubinstein Approximations for the maximum acyclic subgraph problem . . . . . . . . . . . . 133--140 Vladimir G. De\uìneko and René van Dal and Günter Rote The convex-hull-and-line Traveling Salesman Problem: A solvable case . . . 141--148 Jayme L. Szwarcfiter and Guy Chaty Enumerating the kernels of a directed graph with no odd circuits . . . . . . . 149--153 G. Ramalingam and Thomas Reps On competitive on-line algorithms for the dynamic priority-ordering problem 155--161
Ching Yu Hung and Behrooz Parhami Fast RNS division algorithms for fixed divisors with application to RSA encryption . . . . . . . . . . . . . . . 163--169 André Raspaud and Eric Sopena Good and semi-strong colorings of oriented planar graphs . . . . . . . . . 171--174 Dominique Barth and André Raspaud Two edge-disjoint Hamiltonian cycles in the butterfly graph . . . . . . . . . . 175--179 K. Sridharan and H. E. Stephanou and K. C. Craig and S. S. Keerthi Distance measures on intersecting objects and their applications . . . . . 181--188 Paul Fischer and Klaus-Uwe Höffgen Computing a maximum axis-aligned rectangle in a convex polygon . . . . . 189--193 Pen Cheng and Shigeru Masuyama On the equivalence in complexity among three computation problems on maximum number of edge-disjoint $s$-$t$ paths in a probabilistic graph . . . . . . . . . 195--199 Robert Harper A simplified account of polymorphic references . . . . . . . . . . . . . . . 201--206 David Eppstein Arboricity and bipartite subgraph listing algorithms . . . . . . . . . . . 207--211 X. D. Hu and P. D. Chen and F. K. Hwang A new competitive algorithm for the counterfeit coin problem . . . . . . . . 213--218
Bo Chen and André van Vliet and Gerhard J. Woeginger A lower bound for randomized on-line scheduling algorithms . . . . . . . . . 219--222 Eliezer A. Albacea Parallel algorithm for finding a core of a tree network . . . . . . . . . . . . . 223--226 Tamal K. Dey and Nimish R. Shah Many-face complexity in incremental convex arrangements . . . . . . . . . . 227--231 Jung Sing Jwo and Tai Ching Tuan On transmitting delay in a distance-transitive strongly antipodal graph . . . . . . . . . . . . . . . . . 233--235 Xiao Jun Shen and Qing Hu and Weifa Liang Realization of an arbitrary permutation on a hypercube . . . . . . . . . . . . . 237--243 Philip M. Long Halfspace learning, linear programming, and nonmalicious distributions . . . . . 245--250 Lloyd Allison Using Hirschberg's algorithm to generate random alignments of strings . . . . . . 251--255 Yoav Raz Serializability by commitment ordering 257--264 Jordan Gergov Time-space tradeoffs for integer, multiplication on various types of input oblivious sequential machines . . . . . 265--269 Dan Gusfield Faster implementation of a shortest superstring approximation . . . . . . . 271--274
Ying Teh Tsai and Chuan Yi Tang and Yunn Yen Chen Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space . . 275--282 Steven S. Seiden and Daniel S. Hirschberg Finding succinct ordered minimal perfect hash functions . . . . . . . . . . . . . 283--288 Barun Chandra Constructing sparse spanners for most graphs in higher dimensions . . . . . . 289--294 Micha Hofri On timeout for global deadlock detection in decentralized database systems . . . 295--302 Olav Lysne Extending Bachmair's method for proof by consistency to the final algebra . . . . 303--310 Alejandro López-Ortiz New lower bounds for element distinctness on a one-tape Turing machine . . . . . . . . . . . . . . . . 311--314 Nikolai N. Kuzjurin Multi-processor scheduling and expanders 315--319 Vincenzo Acciaro On the complexity of computing Gröbner bases in characteristic $2$ . . . . . . 321--323
Nakagawa Akinari and Hiroshi Hagiwara On the real-number representation with variable-length exponent field . . . . . 1--6 Charles U. Martel Maximum finding on a multiple access broadcast network . . . . . . . . . . . 7--13 Torben Æ. Mogensen WORM-2DPDAs: An extension to 2DPDAs that can be simulated in linear time . . . . 15--22 Md. Mozammel Huq Azad Khan An algorithm for hazard-free minimization of incompletely specified switching function . . . . . . . . . . . 23--29 Lawrence L. Larmore and Wojciech Rytter An optimal sublinear time parallel algorithm for some dynamic programming problems . . . . . . . . . . . . . . . . 31--34 Shao Dong Chen and Hong Shen and Rodney Topor An efficient permutation-based parallel range-join algorithm on $N$-dimensional torus computers . . . . . . . . . . . . 35--38 Jon M. Kleinberg A lower bound for two-server balancing algorithms . . . . . . . . . . . . . . . 39--43 G. Galbiati and F. Maffioli and A. Morzenti A short note on the approximability of the Maximum Leaves Spanning Tree Problem 45--49 Aohan Mei and Yoshihide Igarashi An efficient strategy for robot navigation in unknown environment . . . 51--56
Helmut Seidl Haskell overloading is DEXPTIME-complete 57--60 Mikael Rittri Semi-unification of two terms in Abelian groups . . . . . . . . . . . . . . . . . 61--68 Bern Cherng Liaw and R. C. T. Lee An optimal algorithm to solve the minimum weakly cooperative guards problem for $1$-spiral polygons . . . . 69--75 C. H. Peng and J. S. Wang and R. C. T. Lee Recognizing shortest-path trees in linear time . . . . . . . . . . . . . . 77--85 Refael Hassin and Shlomo Lahav (Haddad) Maximizing the number of unused colors in the vertex coloring problem . . . . . 87--90 Takehiro Tokuda and Yoshimichi Watanabe An attribute evaluation of context-free languages . . . . . . . . . . . . . . . 91--98 Mohamed G. Gouda Stabilizing observers . . . . . . . . . 99--103 Jean Mayo and Phil Kearns Distributed termination detection with roughly synchronized clocks . . . . . . 105--108 Thomas Roos and Peter Widmayer $k$-violation linear programming . . . . 109--114
A. Pedrotti Analysis of a list-update strategy . . . 115--121 Y. Daniel Liang On the feedback vertex set problem in permutation graphs . . . . . . . . . . . 123--129 Kirk R. Pruhs Average-case scalable on-line algorithms for fault replacement . . . . . . . . . 131--136 Ir\`ene Durand and Bruno Salinier Constructor equivalent term rewriting systems are strongly sequential: A direct proof . . . . . . . . . . . . . . 137--145 Paul F. Dietz and Rajeev Raman A constant update time finger search tree . . . . . . . . . . . . . . . . . . 147--154 Luc Devroye and Paul Kruszewski A note on the Horton--Strahler number for random trees . . . . . . . . . . . . 155--159 Frank Wagner Approximate Map Labeling is in $\Omega(n \log n)$ . . . . . . . . . . . . . . . . 161--165 Michele Flammini On the learnability of monotone $k \mu$-DNF formulae under product distributions . . . . . . . . . . . . . 167--173
Rajesh P. N. Rao and Jörg Rothe and Osamu Watanabe Upward separation for ${\rm FewP}$ and related classes . . . . . . . . . . . . 175--180 Ernie Cohen The convergence span of greedy load balancing . . . . . . . . . . . . . . . 181--182 Chuzo Iwamoto and Godfried T. Toussaint Finding Hamiltonian circuits in arrangements of Jordan curves is NP-complete . . . . . . . . . . . . . . 183--189 Su-Hyun Lee and Do-Hyung Kim and Kwang-Moo Choe Path for AND-parallel execution of logic programs . . . . . . . . . . . . . . . . 191--199 Hung Min Sun and Shiuh Pyng Shieh On dynamic threshold schemes . . . . . . 201--206 Esko Nuutila An efficient transitive closure algorithm for cyclic digraphs . . . . . 207--213 Mark de Berg and Marc van Kreveld Rectilinear decompositions with low stabbing number . . . . . . . . . . . . 215--221 Pierre Kelsen An optimal parallel algorithm for maximal matching . . . . . . . . . . . . 223--228
H. Petersen Refined simulation of multihead automata 229--233 Ronald V. Book On collapsing the polynomial-time hierarchy . . . . . . . . . . . . . . . 235--237 Samir Khuller and Uzi Vishkin On the parallel complexity of digraph reachability . . . . . . . . . . . . . . 239--241 James F. Korsh Loopless generation of $k$-ary tree sequences . . . . . . . . . . . . . . . 243--247 Eric T. Bax Algorithms to count paths and cycles . . 249--252 Mark Allen Weiss Linear-time construction of treaps and Cartesian trees . . . . . . . . . . . . 253--257 Jin Tai Yan and Pei Yung Hsiao A fuzzy clustering algorithm for graph bisection . . . . . . . . . . . . . . . 259--263 Zhi-Zhong Chen A parallel algorithm for finding a triconnected component separator with an application . . . . . . . . . . . . . . 265--271 Zbigniew Duszak and Waldemar W. Koczkodaj Generalization of a new definition of consistency for pairwise comparisons . . 273--276 F. Luccio and A. Pedrotti A parallel list update problem . . . . . 277--284
J. A. Bergstra and Gh. \cStef\uanescu Bisimulation is two-way simulation . . . 285--287 Arturo Carpi On repeated factors in $C^\infty$-words 289--294 Subir Bhattacharya and A. Bagchi A general framework for minimax search in game trees . . . . . . . . . . . . . 295--301 Philip N. Klein A data structure for bicategories, with application to speeding up an approximation algorithm . . . . . . . . 303--307 Y. Daniel Liang Dominations in trapezoid graphs . . . . 309--315 Jing Ho Yan and Gerard J. Chang The path-partition problem in block graphs . . . . . . . . . . . . . . . . . 317--322 H. Petersen On the determinacy problem for two-way pushdown automata . . . . . . . . . . . 323--324 Luke O'Connor An upper bound on the number of functions satisfying the Strict Avalanche Criterion . . . . . . . . . . 325--327 Ravi B. Boppana The decision-tree complexity of element distinctness . . . . . . . . . . . . . . 329--331 Wan Fokkink A complete equational axiomatization for prefix iteration . . . . . . . . . . . . 333--337 A. Bertoni and Carlo Mereghetti and Giovanni Pighizzini Corrigendum: ``An optimal lower bound for nonregular languages'' [Inform. Process. Lett. \bf 50 (27 June 1994), no. 6, 289--292; MR 95c:68126] . . . . . 339--339 Erl Huei Lu and Yi Chang Cheng and Hsiao Peng Wuu Corrigendum: ``A complete decoding algorithm for double-error-correcting primitive binary BCH codes of odd $m$'' [Inform. Process. Lett. \bf 51 (1994), no. 3, 117--120; 1290203] . . . . . . . 341--341
Sanjay Jain On a question about learning nearly minimal programs . . . . . . . . . . . . 1--4 Martin Fränzle and Bernhard von Stengel and Arne Wittmüss A generalized notion of semantic independence . . . . . . . . . . . . . . 5--9 Angelo Monti and Alessandro Roncato Completeness results concerning systolic tree automata and E$0$L languages . . . 11--16 Ran Canetti and Guy Even and Oded Goldreich Lower bounds for sampling algorithms for estimating the average . . . . . . . . . 17--25 Andrea Clementi and Russell Impagliazzo The reachability problem for finite cellular automata . . . . . . . . . . . 27--31 Priyalal Kulasinghe and Said Bettayeb Multiply-twisted hypercube with five or more dimensions is not vertex-transitive 33--36 C. C. Aggarwal and N. Jain and P. Gupta An efficient selection algorithm on the pyramid . . . . . . . . . . . . . . . . 37--47 Yuliang Zheng On key agreement protocols based on tamper-proof hardware . . . . . . . . . 49--54 Yung Cheng Chang and Lih Hsing Hsu Element perturbation problems of optimum spanning trees with two-parameter objectives . . . . . . . . . . . . . . . 55--59
Alexander Russell and Ravi Sundaram The relativized relationship between probabilistically checkable debate systems, IP and PSPACE . . . . . . . . . 61--68 S. T. Fischer A note on the complexity of local search problems . . . . . . . . . . . . . . . . 69--75 Kaoru Kurosawa and Koji Okada and Shigeo Tsujii Low exponent attack against elliptic curve RSA . . . . . . . . . . . . . . . 77--83 Chuan-Heng Ang and Kok-Phuang Tan The interval $B$-tree . . . . . . . . . 85--89 Chae Hoon Lim and Pil Joong Lee Several practical protocols for authentication and key exchange . . . . 91--96 Tzonelih Hwang and Yung-Hsiang Chen On the security of SPLICE/AS --- The authentication system in WIDE Internet 97--101 Tzonelih Hwang and Narn-Yih Lee and Chuan-Ming Li and Ming-Yung Ko and Yung-Hsiang Chen Two attacks on Neuman-Stubblebine authentication protocols . . . . . . . . 103--107 Refael Hassin and Arie Tamir On the minimum diameter spanning tree problem . . . . . . . . . . . . . . . . 109--111 Ouri Wolfson and Sushil Jajodia An algorithm for dynamic data allocation in distributed systems . . . . . . . . . 113--119
Burghard von Karger and C. A. R. Hoare Sequential calculus . . . . . . . . . . 123--130 Mathematics of Program Construction Group Fixed-point calculus . . . . . . . . . . 131--136 The Eindhoven Tuesday Afternoon Club Constructing the Galois adjoint . . . . 137--139 Edsger W. Dijkstra Heuristics for a calculational proof . . 141--143 David Gries and Fred B. Schneider Equational propositional logic . . . . . 145--152 Jacob Kornerup Mapping a functional notation for parallel programs onto hypercubes . . . 153--158 K. Rustan M. Leino Constructing a program with exceptions 159--163 R. J. R. Back and J. von Wright Games and winning strategies . . . . . . 165--172
Ashok Subramanian A polynomial bound on the number of light cycles in an undirected graph . . 173--176 Ralph P. Boland and Jorge Urrutia Separating collections of points in Euclidean spaces . . . . . . . . . . . . 177--183 Hsieh-Chang Tu and Carl H. Smith Training digraphs . . . . . . . . . . . 185--192 Rajiv Gupta Generalized dominators . . . . . . . . . 193--200 Roberto De Prisco and Giuseppe Persiano Characteristic inequalities for binary trees . . . . . . . . . . . . . . . . . 201--207 Gregory Kucherov and Michaël Rusinowitch Undecidability of ground reducibility for word rewriting systems with variables . . . . . . . . . . . . . . . 209--215 Ji\vrí Matou\vsek On enclosing $k$ points by a circle . . 217--221 Enno Ohlebusch Termination is not modular for confluent variable-preserving term rewriting systems . . . . . . . . . . . . . . . . 223--228 Aristidis Likas and Andreas Stafylopatis A parallel algorithm for the minimum weighted vertex cover problem . . . . . 229--234 Mikael Rittri Corrigendum: ``Semi-unification of two terms in Abelian groups'' [Inform. Process. Lett. \bf 52(2), 28 October 1994, pp. 61--68] . . . . . . . . . . . 235--235
Friedrich Otto Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general . . . . . . . . . . . . . . . 237--242 Chi Sung Laih and Fu Kuan Tu and Wen Chung Tai On the security of the Lucas function 243--247 Robert Davis and Alan Burns Optimal priority assignment for aperiodic tasks with firm deadlines in fixed priority pre-emptive systems . . . 249--254 M. C. Heydemann and D. Sotteau A note on recursive properties of the de Bruijn, Kautz, and FFT digraphs . . . . 255--259 Valmir C. Barbosa and Stella C. S. Porto An algorithm for FIFO message delivery among migrating tasks . . . . . . . . . 261--267 Takehiro Tokuda and Yoshimichi Watanabe An efficient semantic evaluator for warped LC(1) attributed grammars . . . . 269--276 Mounir Hamdi Topological properties of the directional hypercube . . . . . . . . . 277--286 Paulo A. S. Veloso and Thomas S. E. Maibaum On the Modularization Theorem for logical specifications . . . . . . . . . 287--293 William Steiger and Ileana Streinu A pseudo-algorithmic separation of lines from pseudo-lines . . . . . . . . . . . 295--299
Myra Spiliopoulou and Yannis Cotronis and Michael Hatzopoulos Query processing for multimedia applications on optical media . . . . . 301--306 J. H. R. May and A. D. Lunn New statistics for demand-based software testing . . . . . . . . . . . . . . . . 307--314 Ioan I. Macarie Decreasing the bandwidth of a transition matrix . . . . . . . . . . . . . . . . . 315--320 Mikael Goldmann A note on the power of majority gates and modular gates . . . . . . . . . . . 321--327 Rutger M. Dijkstra An experiment with the use of predicate transformers in UNITY . . . . . . . . . 329--332 Madan Natu and Shu Cherng Fang On the point-to-point connection problem 333--336 Martin Otto A note on the number of monadic quantifiers in monadic $\Sigma^1_1$ . . 337--339 Antti Valmari The weakest deadlock-preserving congruence . . . . . . . . . . . . . . . 341--346 Luke O'Connor A new lower bound on the expected size of irredundant forms for Boolean functions . . . . . . . . . . . . . . . 347--353 Ran El-Yaniv and Jon Kleinberg Geometric two-server algorithms . . . . 355--358 Sung-Ho Kim and Jung-Heum Park and Seung-Hak Choi and Sung Yong Shin and Kyung-Yong Chwa An optimal algorithm for finding the edge visibility polygon under limited visibility . . . . . . . . . . . . . . . 359--365
Stavros D. Nikolopoulos Constant-time parallel recognition of split graphs . . . . . . . . . . . . . . 1--8 H. Petersen On space functions fully constructed by two-dimensional Turing machines . . . . 9--10 Hamed Nassar A Markov model for multibus multiprocessor systems under asynchronous operation . . . . . . . . . 11--16 Roope Kaivola On modal mu-calculus and Büchi tree automata . . . . . . . . . . . . . . . . 17--22 Paul E. Dunne and Chris J. Gittings and Paul H. Leng Multiprocessor simulation strategies with optimal speed-up . . . . . . . . . 23--33 Irena Rusu Quasi-parity and perfect graphs . . . . 35--39 Mitsunori Ogihara On helping by parity-like languages . . 41--43 Sundeep Oberoi $\lambda_{\beta'}$ --- A $\lambda$-calculus with a generalized $\beta$-reduction rule . . . . . . . . . 45--53 David M. Chickering and Dan Geiger and David Heckerman On finding a cycle basis with a shortest maximal cycle . . . . . . . . . . . . . 55--58 Ming-Yang Kao Linear-time optimal augmentation for componentwise bipartite-completeness of graphs . . . . . . . . . . . . . . . . . 59--63
C. B. Jones Partial functions and logics: A warning 65--67 Chui Cheng Chen and Rong Jaye Chen Compact embedding of binary trees into hypercubes . . . . . . . . . . . . . . . 69--72 Giorgio Ausiello and Marco Protasi Local search, reducibility and approximability of NP-optimization problems . . . . . . . . . . . . . . . . 73--79 Luis Barriga and Rassul Ayani Lazy update: An efficient implementation of LRU stacks . . . . . . . . . . . . . 81--84 Gene Myers Approximately matching context-free languages . . . . . . . . . . . . . . . 85--92 H. Bunke and J. Csirik An improved algorithm for computing the edit distance of run-length coded strings . . . . . . . . . . . . . . . . 93--96 Richa Agarwala and David Fernández-Baca Weighted search in the plane . . . . . . 97--100 Dennis Moore and W. F. Smyth A correction to ``An optimal algorithm to compute all the covers of a string'' 101--103 Guozhu Dong On the index of positive programmed formal languages . . . . . . . . . . . . 105--110 Israel Cidon and Yuval Shavitt Message terminating algorithms for anonymous rings of unknown size . . . . 111--119 George Varghese and Roger Chamberlain and William E. Weihl Deriving global virtual time algorithms from conservative simulation protocols 121--126 M. A. Weiss A note on construction of treaps and Cartesian trees . . . . . . . . . . . . 127--127
Teofilo F. Gonzalez A simple LP-free approximation algorithm for the minimum weight vertex cover problem . . . . . . . . . . . . . . . . 129--131 John S. Schlipf and Fred S. Annexstein and John V. Franco and R. P. Swaminathan On finding solutions for extended Horn formulas . . . . . . . . . . . . . . . . 133--137 Guillermo A. Alvarez and Marcelo O. Fernández Efficient management of multiple outstanding timeouts . . . . . . . . . . 139--145 Robert Snelick and Joseph JáJá and Raghu Kacker and Gordon Lyon Using synthetic perturbations and statistical screening to assay shared-memory programs . . . . . . . . . 147--153 Gerhard J. Woeginger Scheduling with time-dependent execution times . . . . . . . . . . . . . . . . . 155--156 Robert H. Sloan Four types of noise in data for PAC learning . . . . . . . . . . . . . . . . 157--162 Ravi Jain and John Werth Analysis of approximate algorithms for edge-coloring bipartite graphs . . . . . 163--168 Birgit Jenner Knapsack problems for NL . . . . . . . . 169--174 Stanislaw Gawiejnowicz and Lidia Pankowska Scheduling jobs with varying processing times . . . . . . . . . . . . . . . . . 175--178 Rajesh P. N. Rao A note on $P$-selective sets and closeness . . . . . . . . . . . . . . . 179--185
Xiaokang Yu A new solution for Thue's problem . . . 187--191 Rossella Petreschi and Andrea Sterbini Recognizing strict $2$-threshold graphs in $O(m)$ time . . . . . . . . . . . . . 193--198 Henning Fernau A note on uniformly limited ET0L systems with unique interpretation . . . . . . . 199--204 Martin Kummer A learning-theoretic characterization of classes of recursive functions . . . . . 205--211 Ferruccio Barsi Decoding residue codes . . . . . . . . . 213--222 Satoshi Fujita A note on the size of a multicast tree in hypercubes . . . . . . . . . . . . . 223--227 Massimiliano Goldwurm Random generation of words in an algebraic language in linear binary space . . . . . . . . . . . . . . . . . 229--233 Jean-Jacques Hébrard Unique Horn renaming and Unique $2$-Satisfiability . . . . . . . . . . . 235--239 M. Chrobak and T. H. Payne A linear-time algorithm for drawing a planar graph on a grid . . . . . . . . . 241--246 Ashok Subramanian Erratum: ``A polynomial bound on the number of light cycles in an undirected graph'' [Inform. Process. Lett. \bf 53 (1995), no. 4, 173--176; MR 95k:05096] 247--247
Klaus Simon A note on lexicographic breadth first search for chordal graphs . . . . . . . 249--251 Derek G. Corneil and Stephan Olariu and Lorna Stewart A linear time algorithm to compute a dominating path in an AT-free graph . . 253--257 Ted Herman and Sukumar Ghosh Stabilizing phase-clocks . . . . . . . . 259--265 Eddy Fromentin and Claude Jard and Guy-Vincent Jourdan and Michel Raynal On-the-fly analysis of distributed computations . . . . . . . . . . . . . . 267--274 Kokichi Sugihara and Hiroshi Inagaki Why is the 3D Delaunay triangulation difficult to construct? . . . . . . . . 275--280 Stéphane Demri $3$-${\rm SAT}={\rm SAT}$ for a class of normal modal logics . . . . . . . . . . 281--287 Kazuo Iwama and Toniann Pitassi Exponential lower bounds for the tree-like Hajós calculus . . . . . . . . 289--294 Akihiro Fujiwara and Toshimitsu Masuzawa and Hideo Fujiwara An optimal parallel algorithm for the Euclidean distance maps of $2$-D binary images . . . . . . . . . . . . . . . . . 295--300 A. Blokhuis and T. Kloks On the equivalence covering number of splitgraphs . . . . . . . . . . . . . . 301--304 G. Sajith and Sanjeev Saxena Corrigendum: ``Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees'' [Inform. Process. Lett. \bf 49 (22 March 1994), no. 6, 303--308; MR 95a:68058] . . . . . . . . 305--305
Aldo de Luca A division property of the Fibonacci word . . . . . . . . . . . . . . . . . . 307--312 John Tromp and Jeffrey Shallit Subword complexity of a generalized Thue--Morse word . . . . . . . . . . . . 313--316 V. Zissimopoulos On the performance guarantee of neural networks for NP-hard optimization problems . . . . . . . . . . . . . . . . 317--322 James P. Schmeiser and David T. Barnard Producing a top-down parse order with bottom-up parsing . . . . . . . . . . . 323--326 Jörg Desel and Ekkart Kindler and Tobias Vesper and Rolf Walter A simplified proof for a self-stabilizing protocol: a game of cards . . . . . . . . . . . . . . . . . 327--328 Premkumar Vadapalli and Pradip K. Srimani Trivalent Cayley graphs for interconnection networks . . . . . . . . 329--335 Noga Alon and Yishay Mansour $\varepsilon$-discrepancy sets and their application for interpolation of sparse polynomials . . . . . . . . . . . . . . 337--342 F. Laroussinie About the expressive power of CTL combinators . . . . . . . . . . . . . . 343--345 B. Litow The influence of graph structure on generalized dimension exchange . . . . . 347--353 Yen-Jen Oyang A tight upper bound of the lumped disk seek time for the Scan disk scheduling policy . . . . . . . . . . . . . . . . . 355--358 Ralph P. Boland and Jorge Urrutia Corrigendum: ``Separating collections of points in Euclidean spaces'' [Inform. Process. Lett. \bf 53(4), 24 February 1995, pp. 177--183] . . . . . . . . . . 359--359
Chung-Ming Huang and Jenq-Muh Hsu and Shiun-Wei Lee ECFSM-based probabilistic protocol verification . . . . . . . . . . . . . . 1--9 T. Kloks and D. Kratsch Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph . . . . . . . . . . . . 11--16 Dawei Hong and Joseph Y.-T. Leung Probabilistic analysis of $k$-dimensional packing algorithms . . . 17--24 Ferrucio Barsi and M. Cristina Perotti Addendum to ``A fully parallel algorithm for residue to binary conversion'' [Inform. Process. Lett. \bf 50(1), 8 April 1994, pp. 1--8] . . . . . . . . . 25--26 Meena Mahajan and N. V. Vinodchandran A note on Mod and generalised Mod classes . . . . . . . . . . . . . . . . 27--31 Walter Vogler Fairness and partial order semantics . . 33--39 Alak K. Datta and Ranjan K. Sen 1-Approximation algorithm for bottleneck disjoint path matching . . . . . . . . . 41--44 Hung-Yu Lin and Lein Harn Fair reconstruction of a secret . . . . 45--47 Fouad B. Chedid On the generalized twisted cube . . . . 49--52 Paul Cull and Shawn M. Larson On generalized twisted cubes . . . . . . 53--55 Greg Butler Easy verification of behavioural subtyping in common cases . . . . . . . 57--58
Jeffery Westbrook and Dicky Yan Linear bounds for on-line Steiner problems . . . . . . . . . . . . . . . . 59--63 Steve Hill The lazy $z$-buffer . . . . . . . . . . 65--70 R. P. Swaminathan and D. Giriraj and D. K. Bhatia The pagenumber of the class of bandwidth-$k$ graphs is $k - 1$ . . . . 71--74 Muhammad H. Alsuwaiyel and D. T. Lee Finding an approximate minimum-link visibility path inside a simple polygon 75--79 Jie Wang Some results on selectivity and self-reducibility . . . . . . . . . . . 81--87 John D. Valois A $3$-valued wakeup protocol . . . . . . 89--93 Youssef Saab Iterative improvement of vertex covers 95--98 Derek G. Corneil and Hiryoung Kim and Sridhar Natarajan and Stephan Olariu and Alan P. Sprague Simple linear time recognition of unit interval graphs . . . . . . . . . . . . 99--104 A. Dermouche A fast algorithm for string matching with mismatches . . . . . . . . . . . . 105--110 Tien Huynh and Kim Marriott Incremental constraint deletion in systems of linear constraints . . . . . 111--115
Mukesh Singhal and Friedemann Mattern An optimality proof for asynchronous recovery algorithms in distributed systems . . . . . . . . . . . . . . . . 117--121 Pranava K. Jha and Giora Slutzki A scheme to construct distance-three codes using Latin squares, with applications to the $n$-cube . . . . . . 123--127 Béatrice Bérard Untiming timed languages . . . . . . . . 129--135 Hongchi Shi and Gerhard X. Ritter and Joseph N. Wilson Simulations between two reconfigurable mesh models . . . . . . . . . . . . . . 137--142 Borislav Nikolik Constraint preservation through loops 143--148 Ortrud Oellermann and Jeremy P. Spinrad A polynomial algorithm for testing whether a graph is $3$-Steiner distance hereditary . . . . . . . . . . . . . . . 149--154 Ee-Chien Chang and Chee Yap A note on improved deterministic time simulation of nondeterministic space for small space . . . . . . . . . . . . . . 155--157 Lydia E. Kavraki and Mihail N. Kolountzakis Partitioning a planar assembly into two connected parts is NP-complete . . . . . 159--165 Li Gong Collisionful keyed hash functions with selectable collisions . . . . . . . . . 167--170 Walter Hower Constraint satisfaction --- Algorithms and complexity analysis . . . . . . . . 171--178
Rainer Schuler Some properties of sets tractable under every polynomial-time computable distribution . . . . . . . . . . . . . . 179--184 Nguyen Huong Lam A note on codes having no finite completions . . . . . . . . . . . . . . 185--188 Carlo Blundo A note on dynamic threshold schemes . . 189--193 Jörg Keller and Thomas Walle A note on implementing combining networks . . . . . . . . . . . . . . . . 195--200 Simon Atkinson and David Scholefield Transformational vs. reactive refinement in real-time systems . . . . . . . . . . 201--210 K. Thirusangu and K. Rangarajan A note on the construction of marked graphs . . . . . . . . . . . . . . . . . 211--215 Xavier Droubay Palindromes in the Fibonacci word . . . 217--221 Xuehou Tan and Xiaoyu Song Hexagonal three-layer channel routing 223--228 Young Park and Benjamin Goldberg Static analysis for optimizing reference counting . . . . . . . . . . . . . . . . 229--234
Tatsuya Akutsu Approximate string matching with don't care characters . . . . . . . . . . . . 235--239 J. Ramachandran Modulo classes and logarithmic advice 241--245 Gwoboa Horng Password authentication without using a password table . . . . . . . . . . . . . 247--250 Kian-Lee Tan and Hongjun Lu Workload scheduling for multiple query processing . . . . . . . . . . . . . . . 251--257 Lin Chen Solving the shortest-paths problem on bipartite permutation graphs efficiently 259--264 Soojung Lee and Junguk L. Kim Resolving all deadlocks in distributed systems . . . . . . . . . . . . . . . . 265--271 Tung-Shou Chen \em SIMPLE: An optimal disk system with two restricted heads . . . . . . . . . . 273--277 H. Leung and D. Ranjan and H. J. Hernández and D. Tang and A. González A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs . . . . . 279--282 Ung Kyu Park and Hwang Kyu Choi and Tag Gon Kim Uniform partitioning of relations using histogram equalization framework: An efficient parallel hash-based join . . . 283--289 Serdar Bozta\cs A robust multi-priority topology-independent transmission schedule for packet radio networks . . . 291--295
Martin Farach and Teresa M. Przytycka and Mikkel Thorup On the agreement of many trees . . . . . 297--301 Zhi-Zhong Chen A fast and efficient NC algorithm for maximal matching . . . . . . . . . . . . 303--307 J. Nievergelt and Narsingh Deo Metric graphs elastically embeddable in the plane . . . . . . . . . . . . . . . 309--315 Pallab Dasgupta and P. P. Chakrabarti and S. C. De Sarkar Utility of pathmax in partial order heuristic search . . . . . . . . . . . . 317--322 Vasco Thudichum Vasconcelos Unification of kinded infinite trees . . 323--328 Andrei Z. Broder and Alan Frieze and Carsten Lund and Steven Phillips and Nick Reingold Balanced allocations for tree-like inputs . . . . . . . . . . . . . . . . . 329--332 Weifa Liang Fast parallel algorithms for the approximate edge-coloring problem . . . 333--338 Amiya Nayak and Vincenzo Accia and Paolo Gissi A note on isomorphic chordal rings . . . 339--341 Young G. Park and Benjamin Goldberg Order-of-demand analysis for lazy languages . . . . . . . . . . . . . . . 343--348 Gisela Pitsch ${\rm LR}(k)$-coupled-context-free grammars . . . . . . . . . . . . . . . . 349--358
Stephen Thomas Garbage collection in shared-environment closure reducers: Space-efficient depth first copying using a tailored approach 1--7 Vladimir Estivill-Castro and Joseph O'Rourke and Jorge Urrutia and Dianna Xu Illumination of polygons with vertex lights . . . . . . . . . . . . . . . . . 9--13 Alberto Bertoni and Nicol\`o Cesa-Bianchi and Guido Fiorino Efficient learning with equivalence queries of conjunctions of modulo functions . . . . . . . . . . . . . . . 15--17 Garrison W. Greenwood On the equity of mutual exclusion algorithms in distributed systems . . . 19--22 Ian Parberry A real-time algorithm for the $(n^2-1)$-puzzle . . . . . . . . . . . . 23--28 Qian Ping Gu and Shietung Peng Node-to-node cluster fault tolerant routing in star graphs . . . . . . . . . 29--35 Sanjeev Saxena and N. Malahal Rao Parallel algorithms for connectivity problems on interval graphs . . . . . . 37--44 Joseph S. B. Mitchell and Günter Rote and Gopalakrishnan Sundaram and Gerhard Woeginger Counting convex polygons in planar point sets . . . . . . . . . . . . . . . . . . 45--49 Joseph Y.-T.-T. Leung and W.-D.-D. Wei Tighter bounds on a heuristic for a partition problem . . . . . . . . . . . 51--57 Torben Hagerup The parallel complexity of integer prefix summation . . . . . . . . . . . . 59--64 Rossella Petreschi and Andrea Sterbini Erratum: ``Recognizing strict $2$-threshold graphs in $O(m)$ time'' 65--65
S. O. Krumke On a generalization of the $p$-Center Problem . . . . . . . . . . . . . . . . 67--71 Thomas W. Cusick Cryptanalysis of a public key system based on Diophantine equations . . . . . 73--75 Uday Kumar Chakraborty A simpler derivation of schema hazard in genetic algorithms . . . . . . . . . . . 77--78 Andrei Z. Broder and Martin E. Dyer and Alan M. Frieze and Prabhakar Raghavan and Eli Upfal The worst-case running time of the random simplex algorithm is exponential in the height . . . . . . . . . . . . . 79--81 Yue Li Wang and Hon Chan Chen and Chen Yu Lee An $O(\log n)$ parallel algorithm for constructing a spanning tree on permutation graphs . . . . . . . . . . . 83--87 Eugene L. Lawler and Sergei Sarkissian An algorithm for ``Ulam's Game'' and its application to error correcting codes 89--93 Luc Devroye and Paul Kruszewski A note on the Horton--Strahler number for random trees . . . . . . . . . . . . 95--99 Y. Daniel Liang Steiner set and connected domination in trapezoid graphs . . . . . . . . . . . . 101--108 V. Arvind and J. Köbler and M. Mundhenk On reductions to sets that avoid EXPSPACE . . . . . . . . . . . . . . . . 109--114 Bengt Aspvall Minimizing elimination tree height can increase fill more than linearly . . . . 115--120 F. Barsi and M. C. Pinotti Erratum: Addendum to ``A fully parallel algorithm for residue to binary conversion'' [Inform. Process. Lett. \bf 50(1), 8 April 1994, pp. 1--8] . . . . . 121--121
Helmut Prodinger Multiple Quickselect --- Hoare's Find algorithm for several elements . . . . . 123--129 Gavin Lowe An attack on the Needham--Schroeder public-key authentication protocol . . . 131--133 Susanne Albers and Bernhard von Stengel and Ralph Werchner A combined BIT and TIMESTAMP algorithm for the list update problem . . . . . . 135--139 Dennis Volpano and Geoffrey Smith A type soundness proof for variables in LCF ML . . . . . . . . . . . . . . . . . 141--146 Stasys Jukna Computing threshold functions by depth-$3$ threshold circuits with smaller thresholds of their gates . . . 147--150 John Clark and Jeremy Jacob On the security of recent protocols . . 151--155 Olivier Devillers and Mordecai J. Golin Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas . . . . . . . . . 157--164 Anand Srinivasan and K. Madhukar and P. Nagavamsi and C. Pandu Rangan and Maw-Shang Chang Edge domination on bipartite permutation graphs and cotriangulated graphs . . . . 165--171 Andrew Tomkins Lower bounds for two call control problems . . . . . . . . . . . . . . . . 173--178 Celina M. Herrera de Figueiredo and João Meidanis and Célia Picinin de Mello A linear-time algorithm for proper interval graph recognition . . . . . . . 179--184
Roy S. Rubinstein and John N. Shutt Self-modifying finite automata: An introduction . . . . . . . . . . . . . . 185--190 Bruno Codenotti and Giovanni Manzini and Luciano Margara Algebraic techniques in communication complexity . . . . . . . . . . . . . . . 191--195 Jean-Eric Pin A negative answer to a question of Wilke on varieties of $\omega$-languages . . . 197--200 Jose M. Sempere and Damián López A McCulloch-Pitts neural net to characterize even linear languages . . . 201--208 Leonid Libkin and Limsoon Wong On representation and querying incomplete information in databases with bags . . . . . . . . . . . . . . . . . . 209--214 Y. Daniel Liang and Norbert Blum Circular convex bipartite graphs: maximum matching and Hamiltonian circuits . . . . . . . . . . . . . . . . 215--219 Gil Utard and Gaétan Hains Deadlock-free absorption of barrier synchronisations . . . . . . . . . . . . 221--227 Carlo Mereghetti and Giovanni Pighizzini A remark on middle space bounded alternating Turing machines . . . . . . 229--232 Peter Damaschke A parallel algorithm for nearly optimal edge search . . . . . . . . . . . . . . 233--236
Hsu-Chun Yen A note on fine covers and iterable factors of VAS languages . . . . . . . . 237--243 Ryuhei Uehara Efficient simulations by a biased coin 245--248 A. M. Youssef and S. E. Tavares Resistance of balanced $s$-boxes to linear and differential cryptanalysis 249--252 Xin Yao A note on neural sorting networks with $O(1)$ time complexity . . . . . . . . . 253--254 Bo-Ting Yang A better subgraph of the minimum weight triangulation . . . . . . . . . . . . . 255--258 Wei-Kuo Chiang and Rong-Jaye Chen The $(n,k)$-star graph: A generalized star graph . . . . . . . . . . . . . . . 259--264 Juan Miguel Vilar Reducing the overhead of the AESA metric-space nearest neighbour searching algorithm . . . . . . . . . . . . . . . 265--271 V. Bokka and H. Gurla and S. Olariu and J. L. Schwing Time- and VLSI-optimal convex hull computation on meshes with multiple broadcasting . . . . . . . . . . . . . . 273--280 Uday Kumar Chakraborty A branching process model for genetic algorithms . . . . . . . . . . . . . . . 281--292 Anonymous Note from the Publisher . . . . . . . . i--i
Werner Kuich Representations and complete semiring morphisms . . . . . . . . . . . . . . . 293--298 Arundhati Raychaudhuri The total interval number of a tree and the Hamiltonian completion number of its line graph . . . . . . . . . . . . . . . 299--306 Sebastian Danicic and Mark Harman and Yoga Sivagurunathan A parallel algorithm for static program slicing . . . . . . . . . . . . . . . . 307--313 S. Mazzanti Succinct iterative characterizations of primitive computable unary functions . . 315--319 Xiao Zhou and Nobuaki Nagai and Takao Nishizeki Generalized vertex-rankings of trees . . 321--328 Nader H. Bshouty On the additive complexity of $2 \times 2$ matrix multiplication . . . . . . . . 329--335 Paul Pritchard A simple sub-quadratic algorithm for computing the subset partial order . . . 337--341 Yijie Han An improvement on parallel computation of a maximal matching . . . . . . . . . 343--348 Anonymous Note from the Publisher . . . . . . . . i--i
S. K. Das Modal logics in the theory of relational databases . . . . . . . . . . . . . . . 1--7 Dennis M. Volpano Lower bounds on type checking overloading . . . . . . . . . . . . . . 9--13 Robert Harper A note on: ``A simplified account of polymorphic references'' [Inform. Process. Lett. \bf 51 (1994), no. 4, 201--206; MR 95f:68142] . . . . . . . . 15--16 Akio Yanbe and Kouichi Sakurai A short certificate of the number of universal optimal strategies for stopping simple stochastic games . . . . 17--24 Michael W. Herman and Waldemar W. Koczkodaj A Monte Carlo study of pairwise comparison . . . . . . . . . . . . . . . 25--29 Vlado Dan\vcík Complexity of Boolean functions over bases with unbounded fan-in gates . . . 31--34 Maciej Drozdowski Real-time scheduling of linear speedup parallel tasks . . . . . . . . . . . . . 35--40 Dyi-Rong Duh and Gen-Huey Chen and D. Frank Hsu Combinatorial properties of generalized hypercube graphs . . . . . . . . . . . . 41--45 Qingbo Xue On a class of square-free graphs . . . . 47--48 Wei-Bin Lee and Chin-Chen Chang Integrating authentication in public key distribution system . . . . . . . . . . 49--52 Donatella Merlini and Renzo Sprugnoli and M. Cecilia Verri A uniform model for the storage utilization of $B$-tree-like structures 53--58
Marius Zimand A high-low Kolmogorov complexity law equivalent to the $0$-$1$ law . . . . . 59--64 Norbert Blum An ${O}(n \log n)$ implementation of the standard method for minimizing $n$-state finite automata . . . . . . . . . . . . 65--69 Anca Muscholl and Holger Petersen A note on the commutative closure of star-free languages . . . . . . . . . . 71--74 Shahram Ghandeharizadeh and Doug Ierardi and Roger Zimmermann An on-line algorithm to optimize file layout in a dynamic environment . . . . 75--81 Oscar Garrido and Stefan Jarominek and Andrzej Lingas and Wojciech Rytter A simple randomized parallel algorithm for maximal $f$-matchings . . . . . . . 83--87 Bengt Aspvall and Christos Levcopoulos and Andrzej Lingas and Robert Storlind On $2$-QBF truth testing in parallel . . 89--93 Guozhu Dong and Jianwen Su Conjunctive query containment with respect to views and constraints . . . . 95--102 Xiaotie Deng A lower bound for communication on the crossbar . . . . . . . . . . . . . . . . 103--108 Rolf Fagerberg A generalization of binomial queues . . 109--114 Amiya Nayak and Vincenzo Acciaro and Paolo Gissi Erratum: ``A note on isomorphic chordal rings'' [Inform. Process. Lett. \bf 55 (1995), no. 6, 339--341; MR 96d:68016] 115--115
Peter Clote A note on the monotone complexity of $2$-REF . . . . . . . . . . . . . . . . 117--123 G. Dányi and Z. Fülöp A note on the equivalence problem of $E$-patterns . . . . . . . . . . . . . . 125--128 Christos Levcopoulos and Drago Krznaric Tight lower bounds for minimum weight triangulation heuristics . . . . . . . . 129--135 Judy Goldsmith and Steven Homer Scalability and the Isomorphism Problem 137--143 Tsong Yueh Chen and Yuen Tak Yu A more general sufficient condition for partition testing to be better than random testing . . . . . . . . . . . . . 145--149 Paola Alimonti New local search approximation techniques for maximum generalized satisfiability problems . . . . . . . . 151--158 Michael Müller and Christine Rüb and Wolfgang Rülling A circuit for exact summation of floating-point numbers . . . . . . . . . 159--163 Manuel Abellanas and Jesús García and Gregorio Hernández-Peñalver and Ferrán Hurtado and Oriol Serra and Jorge Urrutia Onion polygonizations . . . . . . . . . 165--173
Yves Métivier and Nasser Saheb Medians and centres of polyominoes . . . 175--181 Premkumar Vadapalli and Pradip K. Srimani Shortest routing in trivalent Cayley graph network . . . . . . . . . . . . . 183--188 Javed A. Aslam and Scott E. Decatur On the sample complexity of noise-tolerant learning . . . . . . . . 189--195 Kevin Cattell and Michael J. Dinneen and Michael R. Fellows A simple linear-time algorithm for finding path- decompositions of small width . . . . . . . . . . . . . . . . . 197--203 M. Manzur Murshed and M. Kaykobad Seek distances in two-headed disk systems . . . . . . . . . . . . . . . . 205--209 Kenneth Baclawski and Dan A. Simovici A characterization of the information content of a classification . . . . . . 211--214 Antonios Symvonis Routing on trees . . . . . . . . . . . . 215--223 Margus Veanes and Jonas Barklund On the number of edges in cycletrees . . 225--229
Luca Trevisan A note on minimum-area upward drawing of complete and Fibonacci trees . . . . . . 231--236 Ran Canetti More on BPP and the Polynomial-time Hierarchy . . . . . . . . . . . . . . . 237--241 Hagit Attiya and Roy Friedman Limitations of fast consistency conditions for distributed shared memories . . . . . . . . . . . . . . . . 243--248 Elias Koutsoupias and Christos Papadimitriou The $2$-evader problem . . . . . . . . . 249--252 William Lenhart and Giuseppe Liotta Drawing outerplanar minimum weight triangulations . . . . . . . . . . . . . 253--260 Thomas W. Cusick Bounds on the number of functions satisfying the Strict Avalanche Criterion . . . . . . . . . . . . . . . 261--263 Suresh Viswanathan and Éva Czabarka and Abhijit Sengupta On fault-tolerant embedding of Hamiltonian circuits in line digraph interconnection networks . . . . . . . . 265--271 S. Seshadri and D. Rotem The two headed disk: Stochastic dominance of the greedy policy . . . . . 273--277 Angelo Monti and Alessandro Roncato A gap theorem for the anonymous torus 279--285 Chongkye Rhee and Y. Daniel Liang An ${\rm NC}$ algorithm for the clique cover problem in cocomparability graphs and its application . . . . . . . . . . 287--290
Angelo Monti On the computational complexity of graph closures . . . . . . . . . . . . . . . . 291--295 Stanis\law Gawiejnowicz A note on scheduling on a single processor with speed dependent on a number of executed jobs . . . . . . . . 297--300 I-Ling Yen A highly safe self-stabilizing mutual exclusion algorithm . . . . . . . . . . 301--305 Ioannis Fudos and Evaggelia Pitoura and Wojciech Szpankowski On pattern occurrences in a random text 307--312 Danny Z. Chen and Kevin S. Klenk Rectilinear short path queries among rectangular obstacles . . . . . . . . . 313--319 Sarnath Ramnath and Sivaprakasam Sunder On two-processor scheduling and maximum matching in permutation graphs . . . . . 321--327 Michael Ben-Or and Dana Ron Agreement in the presence of faults, on networks of bounded degree . . . . . . . 329--334 Sung Kwon Kim A note on finding compact sets in graphs represented by an adjacency list . . . . 335--338
Thierry Lacoste Finitistic proofs of $0$-$1$ laws for fragments of second-order logic . . . . 1--4 Stewart W. Neufeld A pursuit-evasion problem on a grid . . 5--9 S. Harikumar and Shashi Kumar Iterative deepening multiobjective ${\rm A}^*$ . . . . . . . . . . . . . . . . . 11--15 Bagirath R. Krishnamachari and Ravi Mittal Design and analysis of a generalized multi-ring architecture . . . . . . . . 17--21 M. V. Marathe and S. S. Ravi On approximation algorithms for the minimum satisfiability problem . . . . . 23--29 Hervé Caussinus A note on a theorem of Barrington, Straubing and Thérien . . . . . . . . . . 31--33 Mitsunori Ogihara Functions computable with limited access to NP . . . . . . . . . . . . . . . . . 35--38 Richard J. Lipton On proving that a graph has no large clique: A connection with Ramsey theory 39--42 Wen-Guey Tzeng On path equivalence of nondeterministic finite automata . . . . . . . . . . . . 43--46 Lefteris M. Kirousis and Paul Spirakis and Philippas Tsigas Simple atomic snapshots: A linear complexity solution with unbounded time-stamps . . . . . . . . . . . . . . 47--53
Oscar Garrido and Pierre Kelsen and Andrzej Lingas A simple ${\rm NC}$-algorithm for a maximal independent set in a hypergraph of poly-log arboricity . . . . . . . . . 55--58 R. Balasubramanian and S. V. Nagaraj Perfect power testing . . . . . . . . . 59--63 Chia-Chiang Chao and Wen-Tsuen Chen and Gen-Huey Chen Multiple search problem on reconfigurable meshes . . . . . . . . . 65--69 H. A. Eiselt and Michel Gendreau and Gilbert Laporte Optimal location of facilities on a network with an unreliable node or link 71--74 Changwook Kim Unambiguous description of chain code picture languages . . . . . . . . . . . 75--79 Marcelo M. de Azevedo and Nader Bagherzadeh and Martin Dowd and Shahram Latifi Some topological properties of star connected cycles . . . . . . . . . . . . 81--85 Dong-Yul Ra and Jong-Hyun Kim A parallel parsing algorithm for arbitrary context-free grammars . . . . 87--96 Shigetomo Kimura and Atsushi Togashi and Norio Shiratori Extension of synthesis algorithm of recursive processes to $\mu$-calculus 97--104
Viggo Kann and Jens Lagergren and Alessandro Panconesi Approximability of maximum splitting of $k$-sets and some other $Apx$-complete problems . . . . . . . . . . . . . . . . 105--110 B. S. Panda New linear time algorithms for generating perfect elimination orderings of chordal graphs . . . . . . . . . . . 111--115 Koji Obokata and Yasuaki Nishitani and Yoshihide Igarashi A probably optimal embedding of hyper-rings in hypercubes . . . . . . . 117--122 Sang Koo Seo and Yoon Joon Lee Applicability of genetic algorithms to optimal evaluation of path predicates in object-oriented queries . . . . . . . . 123--128 Tomio Hirata A unified linear-time algorithm for computing distance maps . . . . . . . . 129--133 Amnon Ta-Shma A note on PCP vs. MIP . . . . . . . . . 135--140 Twan Basten Branching bisimilarity is an equivalence indeed! . . . . . . . . . . . . . . . . 141--147 Weifa Liang and Brendan D. McKay and Hong Shen NC algorithms for dynamically solving the all pairs shortest paths problem and related problems . . . . . . . . . . . . 149--155
Jakob Rehof Strong normalization for non-structural subtyping via saturated sets . . . . . . 157--162 Anna Ciampolini and Evelina Lamma and Paola Mello An abstract interpretation framework for optimizing dynamic modular logic languages . . . . . . . . . . . . . . . 163--170 Leizhen Cai Fixed-parameter tractability of graph modification problems for hereditary properties . . . . . . . . . . . . . . . 171--176 Piercarlo Grandi Implementing (nondeterministic) parallel assignments . . . . . . . . . . . . . . 177--179 V. Balachandran and P. Nagavamsi and C. Pandu Rangan Clique transversal and clique independence on comparability graphs . . 181--184 Jean-Camille Birget The state complexity of $\overline{\Sigma^*\overline L}$ and its connection with temporal logic . . . . . 185--188 Shin-Jia Hwang and Chin-Chen Chang and Wei-Pang Yang Authenticated encryption schemes with message linkage . . . . . . . . . . . . 189--194 Kai Salomaa Yield-languages of two-way pushdown tree automata . . . . . . . . . . . . . . . . 195--199 Vishv M. Malhotra and Bala Srinivasan and Santosh Kulkarni Storage-efficient data structure for large lookup dictionaries . . . . . . . 201--206
Thomas Hofmeister and Hanno Lefmann Independent sets in graphs with triangles . . . . . . . . . . . . . . . 207--210 Boris Shidlovsky and Elisa Bertino On the number of descendants in an object DAG . . . . . . . . . . . . . . . 211--216 Livio Colussi and Alessia De Col A time and space efficient data structure for string searching on large texts . . . . . . . . . . . . . . . . . 217--222 Alan Burns and Robert Davis Choosing task periods to minimise system utilisation in time triggered systems 223--229 Lucas Chi Kwong Hui and Charles U. Martel Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches . . . . . . . . . 231--236 Rutger M. Dijkstra ``Everywhere'' in predicate algebra and modal logic . . . . . . . . . . . . . . 237--243 Micha Sharir Excess in arrangements of segments . . . 245--247 Domenico Sacc\`a Multiple total stable models are definitely needed to solve unique solution problems . . . . . . . . . . . 249--254 Jacek B\la\.zewicz and Pascal Bouvry and Frédéric Guinand and Denis Trystram Scheduling complete intrees on two uniform processors with communication delays . . . . . . . . . . . . . . . . . 255--263
Andrew Lim Minimum area joining of $k$ compacted cells . . . . . . . . . . . . . . . . . 265--269 Aaron B. Binkley and Stephen R. Schach A comparison of sixteen quality metrics for object-oriented design . . . . . . . 271--275 Siu-Wing Cheng Widest empty $L$-shaped corridor . . . . 277--283 Wakaha Ogata and Keiichi Sakano and Kaoru Kurosawa Multisymbol majority vote and hard core 285--292 Satoshi Obana and Kaoru Kurosawa Veto is impossible in secret sharing schemes . . . . . . . . . . . . . . . . 293--295 Ludwig Staiger Codes, simplifying words, and open set condition . . . . . . . . . . . . . . . 297--301 Ben H. H. Juurlink and Harry A. G. Wijshoff Communication primitives for BSP computers . . . . . . . . . . . . . . . 303--310 Pallab Dasgupta and P. P. Chakrabarti and S. C. DeSarkar Agent search in uniform $b$-ary trees: Multiple goals and unequal costs . . . . 311--318 Lisa Higham and Teresa Przytycka A simple, efficient algorithm for maximum finding on rings . . . . . . . . 319--324 Mohan Ahuja Erratum: ``Assertions about past and future in \em Highways: Global flush broadcast and flush-vector-time'' [Inform. Process. Lett. \bf 48(1), 29 October 1993, pp. 21--28] . . . . . . . 325--325 G. Dányi and Z. Fülöp Letter to the editor: ``A note on the equivalence problem of $E$-patterns'' [Inform. Process. Lett. 57 (1996), no. 3, 125--128; MR 96m:68090] . . . . . . . 327--327
Gurmeet Singh Manku A linear time algorithm for the bottleneck biconnected spanning subgraph problem . . . . . . . . . . . . . . . . 1--7 Stephen Alstrup and Jens Clausen and Kristian Jòrgensen An $O(|V|*|E|)$ algorithm for finding immediate multiple-vertex dominators . . 9--11 Dietmar Wätjen and Heike Spilker Decidability results concerning $k$-limited ED0L systems . . . . . . . . 13--17 Thomas Natschläger and Michael Schmitt Exact VC-dimension of Boolean monomials 19--20 Ricardo A. Baeza-Yates and Chris H. Perleberg Fast and practical approximate string matching . . . . . . . . . . . . . . . . 21--27 Uri Zwick On the number of ANDs versus the number of ORs in monotone Boolean circuits . . 29--30 Yu-Chen Kuo and Shing-Tsaan Huang A simple scheme to construct $k$-coteries with $O(\sqrt N)$ uniform quorum sizes . . . . . . . . . . . . . . 31--36 Nader H. Bshouty A subexponential exact learning algorithm for DNF using equivalence queries . . . . . . . . . . . . . . . . 37--39 Monika Henzinger and David P. Williamson On the number of small cuts in a graph 41--44 Xiaodong Wang and Qingxiang Fu A frame for general divide-and-conquer recurrences 1 . . . . . . . . . . . . . 45--51 Alberto Marchetti-Spaccamela and Umberto Nanni and Hans Rohnert Maintaining a topological order under edge insertions . . . . . . . . . . . . 53--58
Toshihiro Fujito A note on approximation of the vertex cover and feedback vertex set problems---unified approach . . . . . . 59--63 Paul G. Howard and Jeffrey Scott Vitter Parallel lossless image compression using Huffman and arithmetic coding . . 65--73 Ian Glaister and Jeffrey Shallit A lower bound technique for the size of nondeterministic finite automata . . . . 75--77 Brian Dunten and Julie Jones and Jonathan Sorenson A space-efficient fast prime number sieve . . . . . . . . . . . . . . . . . 79--84 Dominique Barth Optimal broadcasting in the back to back $d$-ary trees . . . . . . . . . . . . . 85--89 Hideo Nagumo and Mi Lu and Karan Watson On-line longest fragment first parsing algorithm . . . . . . . . . . . . . . . 91--96 M. S. Madanlal and G. Venkatesan and C. Pandu Rangan Tree $3$-spanners on interval, permutation and regular bipartite graphs 97--102 Ting-Yem Ho and Yue-Li Wang and Ming-Tsan Juan A linear time algorithm for finding all hinge vertices of a permutation graph 103--107 Soon M. Chung and Pyeong S. Mah Semantics-based transaction management for multidatabase systems . . . . . . . 109--115
Hong Shen and Sarnath Ramnath Optimal parallel selection in sorted matrices . . . . . . . . . . . . . . . . 117--122 Noga Alon and Phillip G. Bradford and Rudolf Fleischer Matching nuts and bolts faster . . . . . 123--127 Gheorghe P\uaun Splicing systems with targets are computationally universal . . . . . . . 129--133 Christel Baier and Mila E. Majster-Cederbaum Denotational linear time semantics and sequential composition . . . . . . . . . 135--143 R. F. M. Aranha and C. Pandu Rangan An efficient distributed algorithm for centering a spanning tree of a biconnected graph . . . . . . . . . . . 145--150 A. Bernasconi Sensitivity vs. block sensitivity (an average-case study) . . . . . . . . . . 151--157 Carroll Morgan and Annabelle McIver Unifying $wp$ and $wlp$ . . . . . . . . 159--163 Tetsuo Moriya and Hideki Yamasaki Literal shuffle on $\omega$-languages 165--168 Sergio De Agostino and James A. Storer On-line versus off-line computation in dynamic text compression . . . . . . . . 169--174
Francisco Santos Inscribing a symmetric body in an ellipse . . . . . . . . . . . . . . . . 175--178 Ursula Goltz and Heike Wehrheim Modelling causality via action dependencies in branching time semantics 179--184 Petri\csor Panaite Hypercube permutations routable under all dimension orderings . . . . . . . . 185--189 Christopher H. Young and Philip A. Wilsey A distributed method to bound rollback lengths for fossil collection in time warp simulators . . . . . . . . . . . . 191--196 W\lodzimierz Holszty\'nski and Waldemar W. Koczkodaj Convergence of inconsistency algorithms for the pairwise comparisons . . . . . . 197--202 Andrzej Szepietowski The element distinctness problem on one-tape Turing machines . . . . . . . . 203--206 Muhammad H. Alsuwaiyel Finding a shortest Hamiltonian path inside a simple polygon . . . . . . . . 207--210 Bernd Borchert and Antoni Lozano Succinct circuit representations and leaf language classes are basically the same concept . . . . . . . . . . . . . . 211--215 Yu-Chee Tseng Embedding a ring in a hypercube with both faulty links and faulty nodes . . . 217--222 G. Athithan and T. Sony Roy Hyperspherical neighbourhoods and pattern recognition using neural networks . . . . . . . . . . . . . . . . 223--228 Zoran Ivkovi\'c and Errol L. Lloyd A fundamental restriction on fully dynamic maintenance of bin packing . . . 229--232
Beate Bollig and Martin Löbbing and Ingo Wegener On the effect of local changes in the variable ordering of ordered decision diagrams . . . . . . . . . . . . . . . . 233--239 Ricardo A. Baeza-Yates and Luis O. Fuentes A framework to animate string algorithms 241--244 Judi Romijn and Frits Vaandrager A note on fairness in I/O automata . . . 245--250 György Turán and Farrokh Vatan A size-depth trade-off for the analog computation of Boolean functions . . . . 251--254 Franck Nielsen Output-sensitive peeling of convex and maximal layers . . . . . . . . . . . . . 255--259 Antonio Hernández Barrera Algorithms for deciding the containment of polygons . . . . . . . . . . . . . . 261--265 Wojciech Plandowski and Wojciech Rytter and Tomasz Szymacha Parallel tree-contraction and Fibonacci numbers . . . . . . . . . . . . . . . . 267--271 Keisuke Tanaka and Tetsuro Nishino and Robert Beals Negation-limited circuit complexity of symmetric functions . . . . . . . . . . 273--279 Sukumar Ghosh and Arobinda Gupta An exercise in fault-containment: self-stabilizing leader election . . . . 281--288
Artur Czumaj and Krzysztof Diks and Teresa M. Przytycka Parallel maximum independent set in convex bipartite graphs . . . . . . . . 289--294 Vladimir G. De\uìneko and Gerhard J. Woeginger The convex-hull-and-$k$-line travelling salesman problem . . . . . . . . . . . . 295--301 Helmut Seidl Fast and simple nested fixpoints . . . . 303--308 Roberto De Prisco and Giuseppe Parlati and Giuseppe Persiano A note on the expected path length of trees with known fringe . . . . . . . . 309--315 Adele A. Rescigno On the communication complexity of polling . . . . . . . . . . . . . . . . 317--323 A. P. Ustimenko Algebra of two-level cause-effect structures . . . . . . . . . . . . . . . 325--330 Shin-ichi Tokunaga Intersection number of two connected geometric graphs . . . . . . . . . . . . 331--333 Avraham A. Melkman and Solomon E. Shimony Algorithms for parsimonious complete sets in directed graphs . . . . . . . . 335--339
S. Julia and I. Litovsky and B. Patrou On codes, $\omega$-codes and $\omega$-generators . . . . . . . . . . 1--5 S. A. M. Makki and George Havas Distributed algorithms for depth-first search . . . . . . . . . . . . . . . . . 7--12 Alfredo García and Javier Tejel Using total monotonicity for two optimization problems on the plane . . . 13--17 Dong-Tsan Lee Semantic data modelling using linear logic . . . . . . . . . . . . . . . . . 19--27 Vassilis Giakoumakis ${P}_4$-laden graphs: A new class of brittle graphs . . . . . . . . . . . . . 29--36 Martin Otto and Jan Van den Bussche First-order queries on databases embedded in an infinite structure . . . 37--41 A. Kh. Al Jabri The unicity distance: An upper bound on the probability of an eavesdropper successfully estimating the secret key 43--47 Ingo Wegener On the complexity of encoding in analog circuits . . . . . . . . . . . . . . . . 49--52
Guy Melançon Viennot factorization of infinite words 53--57 Paulo A. S. Veloso On pushout consistency, modularity and interpolation for logical specifications 59--66 K. Sere Procedures and atomicity refinement . . 67--74 Nick Reingold and Jeffery Westbrook Off-line algorithms for the list update problem . . . . . . . . . . . . . . . . 75--80 Shyue-Horng Shiau and Chang-Biau Yang A fast maximum finding algorithm on broadcast communication . . . . . . . . 81--89 K. Gopalakrishnan and D. R. Stinson A simple analysis of the error probability of two-point based sampling 91--96 Peter Eades and Charles Stirk and Sue Whitesides The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings . . . . . . . . . . . . . . . . 97--103 Danny Z. Chen and Kevin S. Klenk Erratum to ``Rectilinear short path queries among rectangular obstacles''. Information Processing Letters 57 (6) (25 March 1996) 313--319 . . . . . . . . 105--105 Thomas Natschläger and Michael Schmitt Erratum to ``Exact VC-dimension of Boolean monomials'' Information Processing Letters 59 (1) (8 July 1996) 19--20 . . . . . . . . . . . . . . . . . 107--107
R. Banach Transitive term graph rewriting . . . . 109--114 Úlfar Erlingsson and Mukkai Krishnamoorthy and T. V. Raman Efficient multiway radix search trees 115--120 Otfried Schwarzkopf and Jules Vleugels Range searching in low-density environments . . . . . . . . . . . . . . 121--127 Ching-Tsun Chou Simple proof techniques for property preservation via simulation . . . . . . 129--134 Tsong Yueh Chen and Man Fai Lau Dividing strategies for the optimization of a test suite . . . . . . . . . . . . 135--141 Ronald E. Prather The subprogram problem for software metric design . . . . . . . . . . . . . 143--149 Galen C. Hunt and Maged M. Michael and Srinivasan Parthasarathy and Michael L. Scott An efficient algorithm for concurrent priority queue heaps . . . . . . . . . . 151--157 Y. Daniel Liang and Chongkye Rhee Finding biconnected components in $O(n)$ time for a class of graphs . . . . . . . 159--163
David A. Christie Sorting permutations by block-interchanges . . . . . . . . . . . 165--169 Eric Bax and Joel Franklin A finite-difference sieve to count paths and cycles by length . . . . . . . . . . 171--176 Meghanad D. Wagh and Jiancheng Mo Hamilton cycles in Trivalent Cayley graphs . . . . . . . . . . . . . . . . . 177--181 Yen-Chun Lin Perfectly overlapped merging and sorting on a two-way linear array . . . . . . . 183--187 Bahram Alidaee and Ahmad Ahmadian Scheduling on a single processor with variable speed . . . . . . . . . . . . . 189--193 Nectarios Kitsios and Athanasios Tsakalidis Space-optimal hidden line elimination for rectangles . . . . . . . . . . . . . 195--200 Ulrich Nitsche and Peter Ochsenschläger Approximately satisfied properties of systems and simple language homomorphisms . . . . . . . . . . . . . 201--206 D. S. Buh\uaceanu and W. H. J. Feijen Formal derivation of an algorithm for distributed phase synchronization . . . 207--213 Thomas W. Cusick and Pantelimon St\uanic\ua Bounds on the number of functions satisfying the Strict Avalanche Criterion . . . . . . . . . . . . . . . 215--219 T. Kloks $K_{1,3}$-free and $W_4$-free graphs . . 221--223
Janka Chlebíková Approximating the Maximally Balanced Connected Partition Problem in graphs 225--230 D. B. Skillicorn A parallel tree difference algorithm . . 231--235 Yong Sun Term rewriting and Hoare logic --- Coded rewriting . . . . . . . . . . . . . . . 237--242 Sven Venema and Hong Shen and Francis Suraweera NC algorithms for the Single Most Vital Edge problem with respect to shortest paths . . . . . . . . . . . . . . . . . 243--248 G. Venkatesan and C. Pandu Rangan Approximate triclique coloring for register allocation . . . . . . . . . . 249--253 Nayla Nassif and Nader Bagherzadeh A grid embedding into the star graph for image analysis solutions . . . . . . . . 255--260 Jinn-Ke Jan and Yuh-Min Tseng On the security of image encryption method . . . . . . . . . . . . . . . . . 261--265 Masayuki Ito and Naofumi Takagi and Shuzo Yajima Square rooting by iterative multiply-additions . . . . . . . . . . . 267--269 A. M. Youssef and S. E. Tavares Comment on: ``Bounds on the number of functions satisfying the strict avalanche criterion'' [Inform. Process. Lett. \bf 60 (1996), no. 4, 215--219; 1 435 155] by T. W. Cusick and P. St\uanic\ua . . . . . . . . . . . . . . 271--275 Josep Domingo i. Ferrer A new privacy homomorphism and applications . . . . . . . . . . . . . . 277--282
Christian Germain and Jean Pallo Two shortest path metrics on well-formed parentheses strings . . . . . . . . . . 283--287 Sven-Olof Nyström There is no fully abstract fixpoint semantics for non-deterministic languages with infinite computations . . 289--293 David A. Grable Nearly-perfect hypergraph packing is in NC . . . . . . . . . . . . . . . . . . . 295--299 Kaoru Kurosawa and Koji Okada Combinatorial lower bounds for secret sharing schemes . . . . . . . . . . . . 301--304 Seyit Kocberber and Fazli Can Partial evaluation of queries for bit-sliced signature files . . . . . . . 305--311 Margus Veanes and Jonas Barklund Construction of natural cycletrees . . . 313--318 Mitchell N. Neilsen and Masaaki Mizuno Erratum to ``Nondominated $k$-coteries for multiple mutual exclusion''. Information Processing Letters 50 (5) (10 June 1994) 247--252 . . . . . . . . 319--319 Anonymous Author Index: Volume 60 (1996) . . . . . 322--324 Anonymous Master Subject Index: Volumes 51--60 . . 325--336 Anonymous Master Index Volumes 51--60 . . . . . . 337--351
Yongge Wang NP-hard sets are superterse unless NP is small . . . . . . . . . . . . . . . . . 1--6 Martin Farach and S. Muthukrishnan Optimal parallel randomized renaming . . 7--10 Gow-Hsing King and Wen-Guey Tzeng On-line algorithms for the dominating set problem . . . . . . . . . . . . . . 11--14 Jacob Kornerup Odd--even sort in powerlists . . . . . . 15--24 Toru Hasunuma and Yukio Shibata Containment of butterflies in networks constructed by the line digraph operation . . . . . . . . . . . . . . . 25--30 Mohamed S. Sedjelmaci and Christian Lavault Improvements on the accelerated integer GCD algorithm . . . . . . . . . . . . . 31--36 Panayiotis Bozanis and Nectarios Kitsios and Christos Makris and Athanasios Tsakalidis The space-optimal version of a known rectangle enclosure reporting algorithm 37--41 Yaagoub Ashir and Iain A. Stewart and Aqeel Ahmed Communication algorithms in $k$-ary $n$-cube interconnection networks . . . 43--48 Avrim Blum and David Karger An $\tilde{O}(n^{3/14})$-coloring algorithm for $3$-colorable graphs . . . 49--53 Stephen Taylor and Nabil Hachem and Stanley Selkow The average height of a node in the BANG abstract directory tree . . . . . . . . 55--61
Richard Zippel Zero testing of algebraic functions . . 63--67 Bernd Loescher One unary function says less than two in existential second order logic . . . . . 69--75 D. J. Guan and Xuding Zhu A coloring problem for weighted graphs 77--81 Ryuhei Uehara Collapse of PP with a semi-random source to BPP . . . . . . . . . . . . . . . . . 83--87 Youssef G. Saab An improved algorithm for intersecting convex polygons . . . . . . . . . . . . 89--90 Kayoko Shikishima-Tsuji and Masashi Katsura and Yuji Kobayashi On termination of confluent one-rule string-rewriting systems . . . . . . . . 91--96 Kuo-Liang Chung Efficient Huffman decoding . . . . . . . 97--99 Hans L. Bodlaender and Dimitrios M. Thilikos and Koichi Yamazaki It is hard to know when greedy is good for finding independent sets . . . . . . 101--106 Chin Lung Lu and Chuan Yi Tang A linear-time algorithm for the weighted feedback vertex problem on interval graphs . . . . . . . . . . . . . . . . . 107--111 Paolo G. Franciosa and Giorgio Gambosi and Umberto Nanni The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs . . . . . . . . . . . . . 113--120
Jitender S. Deogun and Dieter Kratsch and George Steiner An approximation algorithm for clustering graphs with dominating diametral path . . . . . . . . . . . . . 121--127 Thierry Lecroq and Guillaume Luce and Jean Frédéric Myoupo A faster linear systolic algorithm for recovering a longest common subsequence 129--136 Raffaele Mosca Polynomial algorithms for the maximum stable set problem on particular classes of $P_5$-free graphs . . . . . . . . . . 137--143 Guochuan Zhang A simple semi on-line algorithm for ${\rm P}2//C_{\rm max}$ with a buffer 145--148 Seok Hee Hong and Myoung Ho Kim Resolving data conflicts with multiple versions and precedence relationships in real-time databases . . . . . . . . . . 149--156 Ivan Fri\vs and Ivan Havel and Petr Liebl The diameter of the cube-connected cycles . . . . . . . . . . . . . . . . . 157--160 Arnold Rosenbloom Monotone real circuits are more powerful than monotone Boolean circuits . . . . . 161--164 M. Z. Wang Linear complexity profiles and jump complexity . . . . . . . . . . . . . . . 165--168 Tadakazu Sato Ergodicity of linear cellular automata over ${\bf Z}_m$ . . . . . . . . . . . . 169--172
Shih-Yih Wang and Lih-Hsing Hsu and Ting-Yi Sung Faithful $1$-edge fault tolerant graphs 173--181 Martin Henk Note on shortest and nearest lattice vectors . . . . . . . . . . . . . . . . 183--188 Patrizio Cintioli and Riccardo Silvestri Revisiting a result of Ko . . . . . . . 189--194 P. Dell'Olmo and S. Giordani and M. G. Speranza An approximation result for a duo-processor task scheduling problem 195--200 Mark J. Encarnación Black-box polynomial resultants . . . . 201--204 Frédéric Roupin On approximating the memory-Constrained Module Allocation Problem . . . . . . . 205--208 Sung Mo Park and Sangjin Lee and Soo Hak Sung and Kwangjo Kim Improving bounds for the number of correlation immune Boolean functions . . 209--212 Y. Choi and T. W. Lam Dynamic suffix tree and two-dimensional texts management . . . . . . . . . . . . 213--220 Priyalal D. Kulasinghe Connectivity of the crossed cube . . . . 221--226
Dimitrios M. Thilikos and Hans L. Bodlaender Fast partitioning $l$-apex graphs with applications to approximating maximum induced-subgraph problems . . . . . . . 227--232 Antoni Mazurkiewicz Distributed enumeration . . . . . . . . 233--239 Joseph M. Morris Non-deterministic expressions and predicate transformers . . . . . . . . . 241--246 Tiziana Calamoneri and Rossella Petreschi A new $3$D representation of trivalent Cayley networks . . . . . . . . . . . . 247--252 Jean-Frédéric Myoupo and Ahmad Wabbi Improved linear systolic algorithms for substring statistics . . . . . . . . . . 253--258 C. Micheneau Disjoint Hamiltonian cycles in recursive circulant graphs . . . . . . . . . . . . 259--264 K. Iwama and C. Iwamoto and T. Ohsawa A faster parallel algorithm for $k$-connectivity . . . . . . . . . . . . 265--269 Knut Verbarg Approximate center points in dense point sets . . . . . . . . . . . . . . . . . . 271--278 Berry Schoenmakers A tight lower bound for top-down skew heaps . . . . . . . . . . . . . . . . . 279--284
Devendra Kumar and Abraham Silberschatz A counter-example to an algorithm for the generalized input-output construct of CSP . . . . . . . . . . . . . . . . . 287--287 Eyal Kushilevitz A simple algorithm for learning $O(\log n)$-term DNF . . . . . . . . . . . . . . 289--292 Louis Ibarra Finding pattern matchings for permutations . . . . . . . . . . . . . . 293--295 Moshe Dror and Wieslaw Kubiak and Paolo Dell'Olmo Scheduling chains to minimize mean flow time . . . . . . . . . . . . . . . . . . 297--301 Nader H. Bshouty On learning multivariate polynomials under the uniform distribution . . . . . 303--309 H. S. Chao and F. R. Hsu and R. C. T. Lee An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs . . . . . . . . . . . 311--316 Jianer Chen and Saroja P. Kanchi and Arkady Kanevsky A note on approximating graph genus . . 317--322 Athena Vakali and Yannis Manolopoulos An exact analysis on expected seeks in shadowed disks . . . . . . . . . . . . . 323--329 Paola Flocchini Minimal sense of direction in regular networks . . . . . . . . . . . . . . . . 331--338
Vesa Halava and Tero Harju and Lucian Ilie On a geometric problem of zigzags . . . 1--4 Burghard von Karger and Rudolf Berghammer Computing kernels in directed bichromatic graphs . . . . . . . . . . . 5--11 Anna Gál A simple function that requires exponential size read-once branching programs . . . . . . . . . . . . . . . . 13--16 H. V. Jagadish Analysis of the Hilbert curve for representing two-dimensional space . . . 17--22 Manolis Gergatsoulis Unfold/fold transformations for disjunctive logic programs . . . . . . . 23--29 Ekkart Kindler and Rolf Walter Mutex needs fairness . . . . . . . . . . 31--39 Ariel Orda and Michael Merritt Efficient test&set constructions for faulty shared memory . . . . . . . . . . 41--46 J. Orozco and R. Cayssials and J. Santos and E. Ferro 802.4 Rate Monotonic scheduling in hard real-time environments: Setting the medium access control parameters . . . . 47--55
Erkki Mäkinen Inferring uniquely terminating regular languages from positive data . . . . . . 57--60 Assef Chmeiss and Philippe Jégou A generalization of chordal graphs and the maximum clique problem . . . . . . . 61--66 Hee-Joong Kang and Kawon Kim and Jin H. Kim Approximating optimally discrete probability distribution with $k$th-order dependency for combining multiple decisions . . . . . . . . . . . 67--75 Sung-Ming Yen and Kuo-Hong Liao Shared authentication token secure against replay and weak key attacks . . 77--80 Goos Kant and Giuseppe Liotta and Roberto Tamassia and Ioannis G. Tollis Area requirement of visibility representations of trees . . . . . . . . 81--88 Kasturi R. Varadarajan and Pankaj K. Agarwal Linear approximation of simple objects 89--94 Amihood Amir and Emanuel Dar An improved deterministic algorithm for generating different many-element random samples . . . . . . . . . . . . . . . . 95--101 Dany Breslauer and Artur Czumaj and Devdatt P. Dubhashi and Friedhelm Meyer auf der Heide Transforming comparison model lower bounds to the parallel-random-access-machine . . . . . 103--110
Fabrice Bouquet and Philippe Jégou Using OBDDs to handle dynamic constraints . . . . . . . . . . . . . . 111--120 David Eppstein Dynamic connectivity in digital images 121--126 Robert Glück and Andrei Klimov A regeneration scheme for generating extensions . . . . . . . . . . . . . . . 127--134 Sarmad Abbasi and Anirvan Sengupta An $O(n\log n)$ algorithm for finding dissimilar strings . . . . . . . . . . . 135--139 Ching-Nung Yang and Chi-Sung Laih A note on error-correcting codes for authentication and subliminal channels 141--143 Eric Bach The complexity of number-theoretic constants . . . . . . . . . . . . . . . 145--152 Valerie King and Chung Keung Poon and Vijaya Ramachandran and Santanu Sinha An optimal EREW PRAM algorithm for minimum spanning tree verification . . . 153--159 Andreas Döring and Wolfgang J. Paul Decimal adjustment of long numbers in constant time . . . . . . . . . . . . . 161--163 Marius Zimand Large sets in ${\rm AC}^0$ have many strings with low Kolmogorov complexity 165--170
Gabriel Istrate The strong equivalence of ET0L grammars 171--176 Rimli Sengupta Cancellation is exponentially powerful for computing the determinant . . . . . 177--181 Wan Fokkink Unification for infinite sets of equations between finite terms . . . . . 183--188 Shouichi Hirose and Katsuo Ikeda A conference key distribution system for the star configuration based on the discrete logarithm problem . . . . . . . 189--192 Guozhu Dong and Chaoyi Pang Maintaining transitive closure in first order after node-set and edge-set deletions . . . . . . . . . . . . . . . 193--199 Qian-Ping Gu and Shietung Peng Node-to-set disjoint paths problem in star graphs . . . . . . . . . . . . . . 201--207 Felipe Cucker and Pascal Koiran and Martín Matamala Complexity and dimension . . . . . . . . 209--212 Feng Bao and Aohan Mei and Yoshihide Igarashi Average competitive ratios of on-line spanning trees . . . . . . . . . . . . . 213--216 W. F. J. Verhaegh and E. H. L. Aarts A polynomial-time algorithm for Knapsack with divisible item sizes . . . . . . . 217--221
Md. Mozammel Huq Azad Khan and Md. Shamsul Alam Algorithms for conversion of minterms to positive polarity Reed--Muller coefficients and vice versa . . . . . . 223--230 Rabah Harbane and Carles Padró Spanners of de Bruijn and Kautz graphs 231--236 Rabah Harbane and Carles Padró Spanners of underlying graphs of iterated line digraphs . . . . . . . . . 237--244 Timothy Lambert An optimal algorithm for realizing a Delaunay triangulation . . . . . . . . . 245--250 James W. Gray, III On the Clark-Jacob version of SPLICE/AS 251--254 Wai Yin Mok On keys and normal forms . . . . . . . . 255--258 Montserrat Hermo Compressibility and uniform complexity 259--264 V. A. Vassiliev On decision trees for orthants . . . . . 265--268 Anna Formica and Michele Missikoff A verification algorithm for inheritance hierarchies in object-oriented databases 269--279
J. L. Fouquet and I. Parfenoff and H. Thuillier An $O(n)$ time algorithm for maximum matching in $P_4$-tidy graphs . . . . . 281--287 J. Justin and G. Pirillo On some factorizations of infinite words by elements of codes . . . . . . . . . . 289--294 S. Ravi Kumar and Rina Panigrahy and Alexander Russell and Ravi Sundaram A note on optical routing on trees . . . 295--300 Yuan Ma and Serge Plotkin An improved lower bound for load balancing of tasks with unknown duration 301--303 Masataka Sassa and Takuya Ookubo Systematic debugging method for attribute grammar description . . . . . 305--313 Shin-ichi Nakano and Md. Saidur Rahman and Takao Nishizeki A linear-time algorithm for four-partitioning four-connected planar graphs . . . . . . . . . . . . . . . . . 315--322 Shin-ichi Nakayama and Shigeru Masuyama A parallel algorithm for solving the coloring problem on trapezoid graphs . . 323--327 Paul Pritchard An old sub-quadratic algorithm for finding extremal sets . . . . . . . . . 329--334
Richard S. Bird and Jesús N. Ravelo On computing representatives . . . . . . 1--7 Enrico Nardelli and Vincenzo Mastrobuoni and Alesiano Santomo On building the transitive reduction of a two-dimensional poset . . . . . . . . 9--12 Hon-Chan Chen and Yue-Li Wang A linear time algorithm for finding depth-first spanning trees on trapezoid graphs . . . . . . . . . . . . . . . . . 13--18 Chin-Chen Chang and Shin-Jia Hwang A simple approach for generating RSA keys . . . . . . . . . . . . . . . . . . 19--21 Paola Flocchini and Bernard Mans and Nicola Santoro On the impact of sense of direction on message complexity . . . . . . . . . . . 23--31 Eric Bax and Joel Franklin A permanent formula with many zero-valued terms . . . . . . . . . . . 33--39 Marten van Dijk More information theoretical inequalities to be used in secret sharing? . . . . . . . . . . . . . . . . 41--44 Zoran Ivkovi\'c and Errol L. Lloyd Partially dynamic bin packing can be solved within $1+\epsilon$ in (amortized) polylogarithmic time . . . . 45--50 Ji\vrí Sgall A lower bound for randomized on-line multiprocessor scheduling . . . . . . . 51--55
Kuo-Liang Chung A fast algorithm for stereo matching . . 57--61 Refael Hassin and Shlomi Rubinstein An approximation algorithm for maximum packing of $3$-edge paths . . . . . . . 63--67 J. G. Gaines Partitions with minimum entropy of regions in ${\mathbb R}^2$ . . . . . . . 69--73 Gudmund S. Frandsen and Sven Skyum Dynamic maintenance of majority information in constant time per update 75--78 Marek Chrobak and Lawrence L. Larmore and Carsten Lund and Nick Reingold A better lower bound on the competitive ratio of the randomized $2$-server problem . . . . . . . . . . . . . . . . 79--83 Costas Busch and Marios Mavronicolas Impossibility results for weak threshold networks . . . . . . . . . . . . . . . . 85--90 Wilfried Imrich and Sandi Klav\vzar Recognizing Hamming graphs in linear time and space . . . . . . . . . . . . . 91--95 Tiziana Calamoneri and Andrea Sterbini $3$D straight-line grid drawing of $4$-colorable graphs . . . . . . . . . . 97--102 Jan-Ming Ho and Ming-Tat Ko Bounded fan-out $m$-center problem . . . 103--108 Y. Afek and M. Cohen and E. Haalman The bit complexity of the predecessor problem . . . . . . . . . . . . . . . . 109--112 Robert Geist Performance bounds for modeling NUMA architectures . . . . . . . . . . . . . 113--117
A. K. Amoura A note on scheduling multiprocessor tasks with precedence constraints on parallel processors . . . . . . . . . . 119--122 Shou-Hsuan S. Huang and Hongfei Liu and Rakesh M. Verma On embedding rectangular meshes into rectangular meshes of smaller aspect ratio . . . . . . . . . . . . . . . . . 123--129 Oded Goldreich and Dana Ron On universal learning algorithms . . . . 131--136 Christian Schittenkopf and Gustavo Deco and Wilfried Brauer Finite automata-models for the investigation of dynamical systems . . . 137--141 P. Jonsson A nonapproximability result for finite function generation . . . . . . . . . . 143--145 A. A. Arratia-Quesada and I. A. Stewart Generalized Hex and logical characterizations of polynomial space 147--152 Bernd Borchert and Riccardo Silvestri A characterization of the leaf language classes . . . . . . . . . . . . . . . . 153--158 L. M. G. Feijs and R. C. van Ommering Abstract derivation of transitive closure algorithms . . . . . . . . . . . 159--164 Lud\vek Ku\vcera Computing OR on a randomized fixed adversary CRCW PRAM . . . . . . . . . . 165--166 Dieter Kratsch and Lorna Stewart Total domination and transformation . . 167--170
János Csirik and Gerhard J. Woeginger Shelf algorithms for on-line strip packing . . . . . . . . . . . . . . . . 171--175 Kumar N. Lalgudi and Marios C. Papaefthymiou Computing strictly-second shortest paths 177--181 Kunsoo Park and Sang Lyul Min and Yookun Cho The working set algorithm has competitive ratio less than two . . . . 183--188 Prabhudev Konana and Juhnyoung Lee and Sudha Ram Updating timestamp interval for dynamic adjustment of serialization order in Optimistic Concurrency Control-Time Interval (OCCTI) protocol . . . . . . . 189--193 Maxime Crochemore and Thierry Lecroq Tight bounds on the complexity of the Apostolico-Giancarlo algorithm . . . . . 195--203 Sying-Jyan Wang Distributed routing in a fault-tolerant multistage interconnection network . . . 205--210 Nader H. Bshouty and Yishay Mansour and Baruch Schieber and Prasoon Tiwari A tight bound for approximating the square root . . . . . . . . . . . . . . 211--213 Mark de Berg and Olivier Devillers and Katrin Dobrindt and Otfried Schwarzkopf Computing a single cell in the overlay of two simple polygons . . . . . . . . . 215--219 Jürgen Ebert and Gottfried Vossen I-serializability: Generalized correctness for transaction-based environments . . . . . . . . . . . . . . 221--227
S. Louis Hakimi and Edward F. Schmeichel and Neal E. Young Orienting graphs to optimize reachability . . . . . . . . . . . . . . 229--235 Clark F. Olson An approximation algorithm for least median of squares regression . . . . . . 237--241 Doron Peled and Thomas Wilke Stutter-invariant temporal properties are expressible without the next-time operator . . . . . . . . . . . . . . . . 243--246 Wei-Bin Lee and Chin-Chen Chang Authenticated encryption schemes with linkage between message blocks . . . . . 247--250 Helmut Veith Languages represented by Boolean formulas . . . . . . . . . . . . . . . . 251--256 Ravi B. Boppana The average sensitivity of bounded-depth circuits . . . . . . . . . . . . . . . . 257--261 B. Y. Wu and C. Y. Tang An $O(n)$ algorithm for finding an optimal position with relative distances in an evolutionary tree . . . . . . . . 263--269 Li-Chiun Wei and Ruay-Shiung Chang Broadcast scheduling in packet radio networks by Hopfield neural networks . . 271--276 Ruay-Shiung Chang and Shing-Jiuan Leu The minimum labeling spanning trees . . 277--282 Vincent D. Blondel and John N. Tsitsiklis When is a pair of matrices mortal? . . . 283--286
Mikael Goldmann On the power of a threshold gate at the top . . . . . . . . . . . . . . . . . . 287--293 Vijay K. Garg and J. Roger Mitchell Detecting conjunctions of global predicates . . . . . . . . . . . . . . . 295--302 Sung Kwon Kim Logarithmic width, linear area upward drawing of AVL trees . . . . . . . . . . 303--307 Seung-Hoon Kim and Kyungshik Lim and Cheeha Kim Efficient stream distribution algorithm for heterogeneous multimedia multicast with link capacity constraint . . . . . 309--315 Carlo Blundo and Alfredo De Santis Lower bounds for robust secret sharing schemes . . . . . . . . . . . . . . . . 317--321 Ng\doc-Minh Lê On non-smooth convex distance functions 323--329 Fabrizio Luccio and Linda Pagli An insight on PRAM computational bounds 331--336
E. Bertino and B. Catania and B. Shidlovsky Towards optimal two-dimensional indexing for constraint databases . . . . . . . . 1--8 Divyakant Agrawal and Ömer E\ugecio\uglu and Amr El Abbadi Billiard quorums on the grid . . . . . . 9--16 E. Belogay and C. Cabrelli and U. Molter and R. Shonkwiler Calculating the Hausdorff distance between curves . . . . . . . . . . . . . 17--22 Hung-Yi Chang and Rong-Jaye Chen Embedding cycles in IEH graphs . . . . . 23--27 Sandeep S. Kulkarni and Anish Arora Multitolerant barrier synchronization 29--36 J. Dj. Goli\'c and M. Salmasizadeh and L. Simpson and E. Dawson Fast correlation attacks on nonlinear filter generators . . . . . . . . . . . 37--42 Sanjoy K. Baruah and Johannes E. Gehrk and C. Greg Plaxton and Ion Stoica and Hussein Abdel-Wahab and Kevin Jeffay Fair on-line scheduling of a dynamic set of tasks on a single resource . . . . . 43--51
A. Arnold and M. Kanta and D. Krob Recognizable subsets of the two letter plactic monoid . . . . . . . . . . . . . 53--59 E. G. Coffman, Jr. and L. Flatto and E. N. Gilbert and A. G. Greenberg An approximate model of processor communication rings under heavy load . . 61--67 Mikhail Y. Kovalyov and Yakov M. Shafransky Batch scheduling with deadlines on parallel machines: An NP-hard case . . . 69--74 Gyung-Ok Lee and Do-Hyung Kim Characterization of extended ${\rm LR}(k)$ grammars . . . . . . . . . . . . 75--82 Laurent Coupry A simple linear algorithm for the edge-disjoint $(s,t)$-paths problem in undirected planar graphs . . . . . . . . 83--86 Injong Rhee and Jennifer L. Welch Time bounds on synchronization in a periodic distributed system . . . . . . 87--93 Ye-In Chang and Bi-Yen Yang Efficient access methods for image databases . . . . . . . . . . . . . . . 95--105
Frank Dehne and Katia Guimarães Exact and approximate computational geometry solutions of an unrestricted point set stereo matching problem . . . 107--114 Eric Aaron and David Gries Formal justification of underspecification for S5 . . . . . . . 115--121 M. Flouret and E. Laugerotte Noncommutative minimization algorithms 123--126 Luca Aceto and Anna Ingólfsdóttir A characterization of finitary bisimulation . . . . . . . . . . . . . . 127--134 Wai Yin Mok and David W. Embley On improving dependency implication algorithms . . . . . . . . . . . . . . . 135--141 Min-Sheng Lin and Deng-Jyi Chen The computational complexity of the reliability problem on distributed systems . . . . . . . . . . . . . . . . 143--147 Enrico Nardelli and Vincenzo Mastrobuoni and Alesiano Santomo Computing a poset from its realizer . . 149--154 Susanne Albers and Michael Mitzenmacher Revisiting the COUNTER algorithms for list update . . . . . . . . . . . . . . 155--160
Stephen Alstrup and Jens Peter Secher and Maz Spork Optimal on-line decremental connectivity in trees . . . . . . . . . . . . . . . . 161--164 Marco Cesati and Luca Trevisan On the efficiency of polynomial time approximation schemes . . . . . . . . . 165--171 S. N. Kabadi and Y. P. Aneja An efficient, strongly polynomial, $\varepsilon$-approximation parametric optimization scheme . . . . . . . . . . 173--177 Carlos Domingo and Tatsuie Tsukiji and Osamu Watanabe Partial Occam's Razor and its applications . . . . . . . . . . . . . . 179--185 Jerzy Tyszkiewicz A note on the Kolmogorov data complexity and nonuniform logical definitions . . . 187--195 Abbas Edalat and David Sharp and Lyndon While Bounding the attractor of an IFS . . . . 197--202 Anindo Bagchi Route selection with multiple metrics 203--205 Silvano Di Zenzo and Paolo Bottoni and Piero Mussio A notion of information related to computation . . . . . . . . . . . . . . 207--215
Edward M. Reingold and Kenneth J. Urban and David Gries K-M-P string matching revisited . . . . 217--223 Kouichi Hirata Constructing simply recursive programs from a finite set of good examples . . . 225--230 Paulo A. S. Veloso and Sheila R. M. Veloso On methods for safe introduction of operations . . . . . . . . . . . . . . . 231--238 Muhammad Rabi and Alan T. Sherman An observation on associative one-way functions in complexity theory . . . . . 239--244 Izabela Wierzbowska Checker for data structures which sort elements . . . . . . . . . . . . . . . . 245--249 Petr Slavík Improved performance of the greedy algorithm for partial cover . . . . . . 251--254 Yang Dai and Kazuo Iwano and Naoki Katoh A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems . . . . . . . . . . . . . . . . 255--261 Prosenjit Gupta and Ravi Janardan and Michiel Smid A technique for adding range restrictions to generalized searching problems . . . . . . . . . . . . . . . . 263--269
Vikram Iyengar and Krishnendu Chakrabarty An efficient finite-state machine implementation of Huffman decoders . . . 271--275 Victor Mitrana Primitive morphisms . . . . . . . . . . 277--281 M. A. Shokrollahi and D. A. Spielman and V. Stemann A remark on matrix rigidity . . . . . . 283--285 T. Graf and V. Kamakoti Sparse dominance queries for many points in optimal time and space . . . . . . . 287--291 Gerhard J. Woeginger There is no asymptotic PTAS for two-dimensional vector packing . . . . . 293--297 Paolo Boldi and Sebastiano Vigna Minimal sense of direction and decision problems for Cayley graphs . . . . . . . 299--303 L. Alonso and J. L. Rémy and R. Schott Uniform generation of a Schröder tree . . 305--308 Alon Efrat and Otfried Schwarzkopf Separating and shattering long line segments . . . . . . . . . . . . . . . . 309--314 Christian Queinnec Fast and compact dispatching for dynamic object-oriented languages . . . . . . . 315--321
Venkatesh Raman and B. Ravikumar and S. Srinivasa Rao A simplified NP-complete MAXSAT problem 1--6 P. Y. A. Ryan and S. A. Schneider An attack on a recursive authentication protocol --- A cautionary tale . . . . . 7--10 J. Lakhal and L. Litzler A polynomial algorithm for the extendability problem in bipartite graphs . . . . . . . . . . . . . . . . . 11--16 Paul E. Dunne and Michele Zito An improved upper bound on the non-3-colourability threshold . . . . . 17--23 Carlo Blundo and Alfredo De Santis and Ugo Vaccaro On secret sharing schemes . . . . . . . 25--32 Amos Israeli and Asaf Shirazi The time complexity of updating snapshot memories . . . . . . . . . . . . . . . . 33--40 Hosam M. Mahmoud On rotations in fringe-balanced binary trees . . . . . . . . . . . . . . . . . 41--46 R. Molva and G. Tsudik Secret sets and applications . . . . . . 47--55
Teodor Knapik and Étienne Payet The full quotient and its closure property for regular languages . . . . . 57--62 Ahmed Ait-Bouziad and Helen Kassel An improved algorithm for retrieving fuzzy information from two systems . . . 63--66 Michiel A. Odijk and Hans van Maaren Improved solutions to the Steiner triple covering problem . . . . . . . . . . . . 67--69 Gwoboa Horng An active attack on protocols for server-aided RSA signature computation 71--73 T. C. E. Cheng and Q. Ding The complexity of scheduling starting time dependent tasks with release times 75--79 Jou-Ming Chang and Chin-Wen Ho The recognition of geodetically connected graphs . . . . . . . . . . . . 81--88 Peter J. Grabner and Helmut Prodinger An asymptotic study of a recursion occurring in the analysis of an algorithm on broadcast communication . . 89--93 Michael Segal and Klara Kedem Enclosing $k$ points in the smallest axis parallel rectangle . . . . . . . . 95--99 D. Dervos and Y. Manolopoulos and P. Linardis Comparison of signature file models with superimposed coding . . . . . . . . . . 101--106 Anders Dessmark and Oscar Garrido and Andrzej Lingas A note on parallel complexity of maximum $f$-matching . . . . . . . . . . . . . . 107--109 Therese C. Biedl Relating bends and size in orthogonal graph drawings . . . . . . . . . . . . . 111--115
Sunil Arya and H. Ramesh A $2.5$-factor approximation algorithm for the $k$-MST problem . . . . . . . . 117--118 Q. S. Wu and K. M. Chao and R. C. T. Lee The NPO-completeness of the longest Hamiltonian cycle problem . . . . . . . 119--123 Pallab Dasgupta Agreement under faulty interfaces . . . 125--129 Shiva Chaudhuri and Naveen Garg and R. Ravi The $p$-neighbor $k$-center problem . . 131--134 Limin Xiang and Kazuo Ushijima ANSV problem on BSRs . . . . . . . . . . 135--138 Jung Je Son and Jong In Lim and Seongtaek Chee and Soo Hak Sung Global avalanche characteristics and nonlinearity of balanced Boolean functions . . . . . . . . . . . . . . . 139--144 Viggo Kann and Jens Lagergren and Alessandro Panconesi Approximate Max $k$-Cut with subgraph guarantee . . . . . . . . . . . . . . . 145--150 Edith Hemaspaandra and Jörg Rothe Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP . . . . . . . . . 151--156 Jeng-Jung Wang and Chun-Nan Hung and Lih-Hsing Hsu Optimal $1$-Hamiltonian graphs . . . . . 157--161 R. Balasubramanian and Michael R. Fellows and Venkatesh Raman An improved fixed-parameter algorithm for vertex cover . . . . . . . . . . . . 163--168
Kim S. Larsen Regular expressions with nested levels of back referencing form a hierarchy . . 169--172 Jerzy R. Nawrocki and Adam Czajka and Wojciech Complak Scheduling cyclic tasks with binary periods . . . . . . . . . . . . . . . . 173--178 Sundararajan Vedantham and S. S. Iyengar The Bandwidth Allocation Problem in the ATM network model is NP-complete . . . . 179--182 S. D. Nikolopoulos and P. Rondogiannis On the number of spanning trees of multi-star related graphs . . . . . . . 183--188 Tzonelih Hwang and Chih-Hung Wang Arbitrated unconditionally secure authentication scheme with multi-senders 189--193 Luc Devroye On the richness of the collection of subtrees in random binary search trees 195--199 Chung Keung Poon and Binhai Zhu and Francis Chin A polynomial time solution for labeling a rectilinear map . . . . . . . . . . . 201--207 Oded Shmueli and Kurt Shoens Data sufficiency for queries on cache 209--216 Nader H. Bshouty and Christino Tamon and David K. Wilson On learning width two branching programs 217--222
Yair Amir and Avishai Wool Optimal availability quorum systems: Theory and practice . . . . . . . . . . 223--228 Paolo Dell'Olmo and Hans Kellerer and Maria Grazia Speranza and Zsolt Tuza A $13/12$ approximation algorithm for bin packing with extendable bins . . . . 229--233 James F. Korsh and Seymour Lipschutz Shifts and loopless generation of $k$-ary trees . . . . . . . . . . . . . 235--240 Jeremy Frank and Ian P. Gent and Toby Walsh Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study . . . . . . . . 241--245 Heung-Taek Kim and Myoung Ho Kim Starvation-free secure multiversion concurrency control . . . . . . . . . . 247--253 D. J. Guan An optimal message routing algorithm for double-loop networks . . . . . . . . . . 255--260 Wen-huei Chen Test sequence generation from the protocol data portion based on the Selecting Chinese Postman algorithm . . 261--268 Danny Z. Chen and Ovidiu Daescu Maintaining visibility of a polygon with a moving point of view . . . . . . . . . 269--275 Prosenjit Bose and Jonathan F. Buss and Anna Lubiw Pattern matching for permutations . . . 277--283
William McCune Automatic proofs and counterexamples for some ortholattice identities . . . . . . 285--291 A. Del Lungo and M. Nivat and R. Pinzani and L. Sorri The medians of discrete sets . . . . . . 293--299 Elias Dahlhaus and Paul D. Manuel and Mirka Miller Maximum $h$-colourable subgraph problem in balanced graphs . . . . . . . . . . . 301--303 Gunnar Andersson and Lars Engebretsen Better approximation algorithms for Set Splitting and Not-All-Equal Sat . . . . 305--311 Philippe Herrmann Timed automata and recognizability . . . 313--318 Kaijung Chang and Yan Huat Tan and Yaakov Varol and Jiang-Hsing Chu A study on interleaving versus segmentation . . . . . . . . . . . . . . 319--324 Shing-Tsaan Huang and Tzong-Jye Liu Four-state stabilizing phase clock for unidirectional rings of odd size . . . . 325--329 Yaw-Wen Chang and Chang-Biau Yang A parallel algorithm for circulant tridiagonal linear systems . . . . . . . 331--337
F\vanic\va Gavril and Oded Shmueli Intersection graphs of $k$-acyclic families of subtrees and relational database query processing . . . . . . . 1--6 A. Rabinovich Non-elementary lower bound for Propositional Duration Calculus . . . . 7--11 Klaus W. Wagner A note on parallel queries and the symmetric-difference hierarchy . . . . . 13--20 Cunsheng Ding and Tor Helleseth On cyclotomic generator of order $r$ . . 21--25 Eisuke Dannoura and Kouichi Sakurai An improvement on El-Yaniv-Fiat-Karp-Turpin's money-making bi-directional trading strategy . . . . 27--33 Ion I. M\uandoiu Optimum extensions of prefix codes . . . 35--40 Walter Hower Revisiting global constraint satisfaction . . . . . . . . . . . . . . 41--48 Ichiro Suzuki and Masafumi Yamashita and Hideki Umemoto and Tsunehiko Kameda Bushiness and a tight worst-case upper bound on the search number of a simple polygon . . . . . . . . . . . . . . . . 49--52
Beate Bollig and Ingo Wegener A very simple function that requires exponential size read-once branching programs . . . . . . . . . . . . . . . . 53--57 Flaminia L. Luccio Almost exact minimum feedback vertex set in meshes and butterflies . . . . . . . 59--64 Maw-Shang Chang and P. Nagavamsi and C. Pandu Rangan Weighted irredundance of interval graphs 65--70 Christel Baier and Marta Kwiatkowska On the verification of qualitative properties of probabilistic processes under fairness constraints . . . . . . . 71--79 Sven O. Krumke and Hans-Christoph Wirth On the minimum label spanning tree problem . . . . . . . . . . . . . . . . 81--85 Chor Ping Low A fast search algorithm for the quorumcast routing problem . . . . . . . 87--92 Ge-Ming Chiu A fault-tolerant broadcasting algorithm for hypercubes . . . . . . . . . . . . . 93--99 Tadakazu Sato Surjective linear cellular automata over $\mathbb{Z}_m$ . . . . . . . . . . . . . 101--104 Jae-Cheol Ha and Sang-Jae Moon A common-multiplicand method to the Montgomery algorithm for speeding up exponentiation . . . . . . . . . . . . . 105--107
Ernst Althaus and Kurt Mehlhorn Maximum network flow with floating point arithmetic . . . . . . . . . . . . . . . 109--113 Chongkye Rhee On the chromatic index of graphs with $2m+1$ vertices and $2m^2$ edges . . . . 115--118 Nakhoon Baek and Sung-Yong Shin On circularly-hidden surface removal . . 119--123 Jurek Czyzowicz and Evangelos Kranakis and Jorge Urrutia A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments . . . . . . . . . . . . . . . . 125--126 Guoliang Xue and Shangzhi Sun and J. Ben Rosen Fast data transmission and maximal dynamic flow . . . . . . . . . . . . . . 127--132 Chan-Su Shin and Sung Kwon Kim and Sung-Ho Kim and Kyung-Yong Chwa Algorithms for drawing binary trees in the plane . . . . . . . . . . . . . . . 133--139 Seongyeol Kim and Ilyong Chung Application of the special Latin square to a parallel routing algorithm on a recursive circulant network . . . . . . 141--147 B. Litow and B. Mans A note on the Ádám conjecture for double loops . . . . . . . . . . . . . . . . . 149--153 V. S. Dimitrov and G. A. Jullien and W. C. Miller An algorithm for modular exponentiation 155--159 Carlos A. Cabrelli and Ursula M. Molter A linear time algorithm for a matching problem on the circle . . . . . . . . . 161--164
Shinichi Shimozono and Kouichi Hirata and Ayumi Shinohara On the hardness of approximating the minimum consistent acyclic DFA and decision diagram . . . . . . . . . . . . 165--170 Sándor P. Fekete and William R. Pulleyblank Traveling the boundary of Minkowski sums 171--174 Esteban Feuerstein and Stefano Leonardi and Alberto Marchetti-Spaccamela and Nicola Santoro Efficient token-based control in rings 175--180 Krzysztof Diks and Stefan Dobrev and Evangelos Kranakis and Andrzej Pelc and Peter Ru\vzi\vcka Broadcasting in unlabeled hypercubes with a linear number of messages . . . . 181--186 Youzou Miyadera and Koushi Anzai and Hiroshi Unno and Takeo Yaku Depth-first layout algorithm for trees 187--194 Hiroshi G. Okuno and Shin-ichi Minato and Hideki Isozaki On the properties of combination set operations . . . . . . . . . . . . . . . 195--199 Ting-Yi Sung and Chun-Yuan Lin and Yen-Chu Chuang and Lih-Hsing Hsu Fault tolerant token ring embedding in double loop networks . . . . . . . . . . 201--207 Hiro Ito and Mitsuo Yokoyama Linear time algorithms for graph search and connectivity determination on complement graphs . . . . . . . . . . . 209--213 Wei-Kuo Chiang and Rong-Jaye Chen On the arrangement graph . . . . . . . . 215--219
Edward A. Luke and Ioana Banicescu and Jin Li The optimal effectiveness metric for parallel application analysis . . . . . 223--229 Duncan K. G. Campbell On the CLUMPS model of parallel computation . . . . . . . . . . . . . . 231--236 Jonathan Nash Scalable and predictable performance for irregular problems using the WPRAM computational model . . . . . . . . . . 237--246 Jin-Soo Kim and Soonhoi Ha and Chu Shik Jhon Relaxed barrier synchronization for the BSP model of computation on message-passing architectures . . . . . 247--253 J. Simon and J.-M. Wierum The Latency-of-Data-Access model for analyzing parallel computation . . . . . 255--261 Clark D. Thomborson The economics of large-memory computations . . . . . . . . . . . . . . 263--268 Bruce M. Maggs and Eric J. Schwabe Real-time emulations of bounded-degree networks . . . . . . . . . . . . . . . . 269--276
Christos Makris and Athanasios Tsakalidis Algorithms for three-dimensional dominance searching in linear space . . 277--283 Masaaki Mizuno and Mikhail Nesterenko A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments . . . . 285--290 S. Schwarz and S. O. Krumke On budget-constrained flow improvement 291--297 A. Salhi and H. Glaser and D. De Roure Parallel implementation of a genetic-programming based tool for symbolic regression . . . . . . . . . . 299--307 Jiun-Liang Chen and Feng-Jian Wang An inheritance flow model for class hierarchy analysis . . . . . . . . . . . 309--315 Tsu-Miin Hsieh and Yi-Shiung Yeh and Yung-Cheng Hsieh and Chan-Chi Wang A homophonic DES . . . . . . . . . . . . 317--320 Gianluca De Marco and Ugo Vaccaro Broadcasting in hypercubes and star graphs with dynamic faults . . . . . . . 321--326
Michael Hanus and Salvador Lucas and Aart Middeldorp Strongly sequential and inductively sequential term rewriting systems . . . 1--8 Vincenzo Liberatore Uniform multipaging reduces to paging 9--12 Paolo Bottoni and Stefano Levialdi and Gheorghe P\uaun Successful visual human-computer interaction is undecidable . . . . . . . 13--19 Wuu Yang A data-parallel algorithm for minimum-width tree layout . . . . . . . 21--28 Andreas Blass and Yuri Gurevich and Vladik Kreinovich and Luc Longpré A variation on the zero-one law . . . . 29--30 Marcia R. Cerioli and Hazel Everett and Celina M. H. de Figueiredo and Sulamita Klein The homogeneous set sandwich problem . . 31--35 Jan Johannsen Lower bounds for monotone real circuit depth and formula size and tree-like Cutting Planes . . . . . . . . . . . . . 37--41 Uwe Waldmann Extending reduction orderings to ACU-compatible reduction orderings . . . 43--49 Enrico Nardelli and Guido Proietti and Peter Widmayer Finding the detour-critical edge of a shortest path between two nodes . . . . 51--54
Annalisa De Bonis and Ugo Vaccaro Improved algorithms for group testing with inhibitors . . . . . . . . . . . . 57--64 N. C. Audsley and A. Burns On fixed priority scheduling, offsets and co-prime task periods . . . . . . . 65--69 Michael Krivelevich and Benny Sudakov Coloring random graphs . . . . . . . . . 71--74 Jorge Castro and David Guijarro and Víctor Lavín Learning nearly monotone $k$-term DNF 75--79 J. L. Montaña and Luis M. Pardo On Kolmogorov complexity in the real Turing machine setting . . . . . . . . . 81--86 Vince Grolmusz A lower bound for depth-$3$ circuits with MOD $m$ gates . . . . . . . . . . . 87--90 Burton Rosenberg Fast nondeterministic recognition of context-free languages using two queues 91--93 Jan A. Bergstra and Alban Ponse Kleene's three-valued logic and process algebra . . . . . . . . . . . . . . . . 95--103 Jeffrey Mark Phillips and Abraham P. Punnen and S. N. Kabadi A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph . . . . . . . . . . . . . 105--110
M. Crochemore and F. Mignosi and A. Restivo Automata and forbidden words . . . . . . 111--117 Mila Majster-Cederbaum and Markus Roggenbach Transition systems from event structures revisited . . . . . . . . . . . . . . . 119--124 Refael Hassin and Shlomi Rubinstein An approximation algorithm for the maximum traveling salesman problem . . . 125--130 Peter Damaschke Randomized group testing for mutually obscuring defectives . . . . . . . . . . 131--135 T. C. Hu and P. A. Tucker Optimal alphabetic trees for binary search . . . . . . . . . . . . . . . . . 137--140 Sanguthevar Rajasekaran An optimal parallel algorithm for sorting multisets . . . . . . . . . . . 141--143 Dino Pedreschi and Salvatore Ruggieri Weakest preconditions for pure Prolog programs . . . . . . . . . . . . . . . . 145--150 Loon-Been Chen and I-Chen Wu On the time complexity of minimum and maximum global snapshot problems . . . . 151--156 Nimmagadda Chalamaiah and Badrinath Ramamurthy Finding shortest paths in distributed loop networks . . . . . . . . . . . . . 157--161
Martin Löbbing and Detlef Sieling and Ingo Wegener Parity OBDDs cannot be handled efficiently enough . . . . . . . . . . . 163--168 Roland Backhouse Pair algebras and Galois connections . . 169--175 Eric Bonabeau and Florian Hénaux Self-organizing maps for drawing large graphs . . . . . . . . . . . . . . . . . 177--184 Fabio Martinelli An improvement of algorithms for solving interface equations . . . . . . . . . . 185--190 Satoshi Fujita A quorum based $k$-mutual exclusion by weighted $k$-quorum systems . . . . . . 191--197 G. Greco Embeddings and the trace of finite sets 199--203 Oded Goldreich and Johan Håstad On the complexity of interactive proofs with bounded communication . . . . . . . 205--214 Franz Baader On the complexity of Boolean unification 215--220
Huaxiong Wang On syntactic nuclei of rational languages . . . . . . . . . . . . . . . 221--226 Frank Harary and Desh Ranjan Breaking symmetry in complete graphs by orienting edges: asymptotic bounds . . . 227--230 Rainer E. Burkard and Vladimir G. De\uìneko On the traveling salesman problem with a relaxed Monge matrix . . . . . . . . . . 231--237 Hiroshi Nagamochi and Toshihide Ibaraki A note on minimizing submodular functions . . . . . . . . . . . . . . . 239--244 Salvador Lucas Root-neededness and approximations of neededness . . . . . . . . . . . . . . . 245--254 Andrea Sterbini and Thomas Raschle An $O(n^3)$ time algorithm for recognizing threshold dimension $2$ graphs . . . . . . . . . . . . . . . . . 255--259 George Gens and Eugene Levner An approximate binary search algorithm for the multiple-choice knapsack problem 261--265 Teofilo F. Gonzalez Improved approximation algorithms for embedding hyperedges in a cycle . . . . 267--271
J. L. Ramírez Alfonsín A special arrangement with minimal number of triangles . . . . . . . . . . 273--276 G. Guaiana and R. Meyer and A. Petit and P. Weil An extension of the wreath product principle for finite Mazurkiewicz traces 277--282 Qian-Ping Gu and Shietung Peng An efficient algorithm for $k$-pairwise disjoint paths in star graphs . . . . . 283--287 Francis Chu Reducing $\Omega$ to $\diamondsuit {W}$ 289--293 Tomás Feder and Sunil M. Shende Online channel allocation in FDMA networks with reuse constraints . . . . 295--302 Timothy M. Chan Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees . . . . . . . . . 303--304 P. Sanders Random permutations on distributed, external and hierarchical memory . . . . 305--309 Kyunghee Choi and Gihyun Jung and Taegeun Kim and Seunhun Jung Real-time scheduling algorithm for minimizing maximum weighted error with $O(N\log N + cN)$ complexity . . . . . . 311--315 Ali Boroujerdi and Jeffrey Uhlmann An efficient algorithm for computing least cost paths with turn constraints 317--321
Andrew Turpin and Alistair Moffat Comment on ``Efficient Huffman decoding'' and ``An efficient finite-state machine implementation of Huffman decoders'' . . . . . . . . . . . 1--2 Alfredo García and Pedro Jodrá and Javier Tejel An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays 3--9 Alberto Caprara and Romeo Rizzi Improving a family of approximation algorithms to edge color multigraphs . . 11--15 Rajeev Govindan and Michael A. Langston and Xudong Yan Approximating the pathwidth of outerplanar graphs . . . . . . . . . . . 17--23 Chan-Su Shin and Sung Yong Shin and Kyung-Yong Chwa The widest $k$-dense corridor problems 25--31 Bernd Gärtner and Sven Schönherr Exact primitives for smallest enclosing ellipses . . . . . . . . . . . . . . . . 33--38 Chi-Hsiang Yeh and Behrooz Parhami VLSI layouts of complete graphs and star graphs . . . . . . . . . . . . . . . . . 39--45 Wojciech Fraczak and Marek B. Zaremba A non-SOS operational semantics for a process algebra . . . . . . . . . . . . 47--54
Anne Bottreau and Yves Métivier Some remarks on the Kronecker product of graphs . . . . . . . . . . . . . . . . . 55--61 Joost P. Warners A linear-time transformation of linear inequalities into conjunctive normal form . . . . . . . . . . . . . . . . . . 63--69 D. Ranjan and E. Pontelli and G. Gupta Efficient algorithms for the temporal precedence problem . . . . . . . . . . . 71--78 Joaquim Gabarró and Xavier Messeguer Parallel dictionaries with local rules on AVL and brother trees . . . . . . . . 79--85 C. J. Fidge A limitation of vector timestamps for reconstructing distributed computations 87--91 S. Venkatesh Pseudo-average block sensitivity equals average sensitivity . . . . . . . . . . 93--95 K. V. Ravi Kanth and Ambuj Singh Efficient dynamic range searching using data replication . . . . . . . . . . . . 97--105
Carles Padró Robust vector space secret sharing schemes . . . . . . . . . . . . . . . . 107--111 Vincent Vajnovszki On the loopless generation of binary tree sequences . . . . . . . . . . . . . 113--117 Marcin Jurdzi\'nski Deciding the winner in parity games is in UP $\cap$ co-UP . . . . . . . . . . . 119--124 Amihood Amir and Gad M. Landau and Moshe Lewenstein and Noa Lewenstein Efficient special cases of pattern matching with swaps . . . . . . . . . . 125--132 F. M. Malvestuto A complete axiomatization of full acyclic join dependencies . . . . . . . 133--139 Chor-Ping Low A polynomial time solvable instance of the feasible minimum cover problem . . . 141--146 Witold Charatonik An undecidable fragment of the theory of set constraints . . . . . . . . . . . . 147--151 Valery Gordon and Wieslaw Kubiak Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs . . . . . . 153--159
Nadia Creignou Complexity versus stability for classes of propositional formulas . . . . . . . 161--165 Roberto Posenato and Massimo Santini A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses . . . 167--171 Wim H. Hesselink Invariants for the construction of a handshake register . . . . . . . . . . . 173--177 Ding-Ming Kwai and Behrooz Parhami Pruned three-dimensional toroidal networks . . . . . . . . . . . . . . . . 179--183 Pedro P. Sanchez and Refik Soyer Information concepts and pairwise comparison matrices . . . . . . . . . . 185--188 Yishay Mansour and Michal Parnas Learning conjunctions with noise under product distributions . . . . . . . . . 189--196 Henri Gilbert and Dipankar Gupta and Andrew Odlyzko and Jean-Jacques Quisquater Attacks on Shamir's `RSA for paranoids' 197--199 Ton Kloks and Haiko Müller and C. K. Wong Vertex ranking of asteroidal triple-free graphs . . . . . . . . . . . . . . . . . 201--206 Abhijit Sengupta On ring embedding in hypercubes with faulty nodes and links . . . . . . . . . 207--214 Yi Chang Cheng and Erl Huei Lu and Shaw Woei Wu A modified version of the Rao--Nam algebraic-code encryption scheme . . . . 215--217
A. P. Ustimenko Colored cause--effect structures . . . . 219--225 Yuliang Zheng and Hideki Imai How to construct efficient signcryption schemes on elliptic curves . . . . . . . 227--233 Kyung Oh Lee and Heon Y. Yeom A dynamic scheduling algorithm for large scale multimedia servers . . . . . . . . 235--240 Venkatesan Guruswami and C. Pandu Rangan A natural family of optimization problems with arbitrarily small approximation thresholds . . . . . . . . 241--248 P. Jonsson Near-optimal nonapproximability results for some Npo PB-complete problems . . . 249--253 Bette Bultena and Frank Ruskey An Eades--McKay algorithm for well-formed parentheses strings . . . . 255--259 Matteo Sereno Binary search with errors and variable cost queries . . . . . . . . . . . . . . 261--270
Josep Rif\`a A new algebraic algorithm to decode the ternary Golay code . . . . . . . . . . . 271--274 Rakesh K. Sinha Simulation of PRAMs with scan primitives by unbounded fan-in circuits . . . . . . 275--282 Jorge Calera-Rubio and Rafael C. Carrasco Computing the relative entropy between regular tree languages . . . . . . . . . 283--289 Janelle J. Harms A simple optimal algorithm for scheduling variable-sized requests . . . 291--293 Wen-Ming Yan and Wendy Myrvold and Kuo-Liang Chung A formula for the number of spanning trees of a multi-star related graph . . 295--298 Andrzej Szepietowski Weak and strong one-way space complexity classes . . . . . . . . . . . . . . . . 299--302 Pierre Fraigniaud Hierarchical broadcast networks . . . . 303--305 Ulrich Kühn Local calculation of Voronoi diagrams 307--312 Ton Kloks and Dieter Kratsch and Haiko Müller Bandwidth of chain graphs . . . . . . . 313--315 Michael J. Collins and Bernard M. E. Moret Improved lower bounds for the link length of rectilinear spanning paths in grids . . . . . . . . . . . . . . . . . 317--319
François Denis Finding a minimal $1$-DNF consistent with a positive sample is LOGSNP-complete . . . . . . . . . . . . 1--5 Prosenjit Gupta and Ravi Janardan and Michiel Smid Efficient algorithms for counting and reporting pairwise intersections between convex polygons . . . . . . . . . . . . 7--13 Jitender S. Deogun and K. Gopalakrishnan Consecutive retrieval property---revisited . . . . . . . . . . 15--20 Soo Hak Sung and Seongtaek Chee and Choonsik Park Global avalanche characteristics and propagation criterion of balanced Boolean functions . . . . . . . . . . . 21--24 Tycho Strijk and Marc van Kreveld Labeling a rectilinear map more efficiently . . . . . . . . . . . . . . 25--30 Jichiang Tsai and Yi-Min Wang and Sy-Yen Kuo Evaluations of domino-free communication-induced checkpointing protocols . . . . . . . . . . . . . . . 31--37 Jae-Ha Lee and Kyung-Yong Chwa Tight analysis of a self-approaching strategy for the online kernel-search problem . . . . . . . . . . . . . . . . 39--45 Paul Kruszewski A note on the Horton--Strahler number for random binary search trees . . . . . 47--51
Guo-Hui Lin and Guoliang Xue Steiner tree problem with minimum number of Steiner points and bounded edge-length . . . . . . . . . . . . . . 53--57 H. Bordihn and M. Holzer On a hierarchy of languages generated by cooperating distributed grammar systems 59--62 Bang Ye Wu and Kun-Mao Chao and Chuan Yi Tang An efficient algorithm for the length-constrained heaviest path problem on a tree . . . . . . . . . . . . . . . 63--67 Ju-Hong Lee and Guang-Ho Cha and Chin-Wan Chung A model for $k$-nearest neighbor query processing cost in multidimensional data space . . . . . . . . . . . . . . . . . 69--76 S. R. Chauhan and I. A. Stewart On the power of built-in relations in certain classes of program schemes . . . 77--82 Marius Zimand Relative to a random oracle, P/poly is not measurable in EXP . . . . . . . . . 83--86 Chin-Wen Ho and Jou-Ming Chang Solving the all-pairs-shortest-length problem on chordal bipartite graphs . . 87--93 Chih-Hung Wang and Tzonelih Hwang and Narn-Yih Lee Comments on two group signatures . . . . 95--97 Mark G. Karpovsky and Krishnendu Chakrabarty and Lev B. Levitin and Dimiter R. Avresky On the covering of vertices for fault diagnosis in hypercubes . . . . . . . . 99--103
P. Crégut and B. Heyd Progress properties for empty Unity programs . . . . . . . . . . . . . . . . 107--109 Zheng Wang On the complexity of quality of service routing . . . . . . . . . . . . . . . . 111--114 Yongge Wang A separation of two randomness concepts 115--118 Hong-Chung Chen and Yue-Li Wang and Yu-Feng Lan A memory-efficient and fast Huffman decoding algorithm . . . . . . . . . . . 119--122 Dominique Roelants van Baronaigien A multi-stack method for the fast generation of permutations with minimal length increasing subsequences . . . . . 123--126 Leizhen Cai and Yinfeng Xu and Binhai Zhu Computing the optimal bridge between two convex polygons . . . . . . . . . . . . 127--130 D. R. Stinson and R. Wei An application of ramp schemes to broadcast encryption . . . . . . . . . . 131--135 Rajeev Alur and Doron Peled Undecidability of partial order logics 137--143 J. Dj. Golic\' Stream cipher encryption of random access files . . . . . . . . . . . . . . 145--148 I. Terekhov and T. Camp Time efficient deadlock resolution algorithms . . . . . . . . . . . . . . . 149--154 Yukihiro Iwasaki and Yuka Kajiwara and Koji Obokata and Yoshihide Igarashi Independent spanning trees of chordal rings . . . . . . . . . . . . . . . . . 155--160
Noriko Sugimoto and Hiroki Ishizaka Generating languages by a derivation procedure for elementary formal systems 161--166 Jin-Yi Cai A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes . . . 167--174 Carsten Damm Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones . . . . . . . . . . . . . . . . . . 175--179 V. Arvind and Jacobo Torán Sparse sets, approximable sets, and parallel queries to NP . . . . . . . . . 181--188 Gabriel Robins and Brian L. Robinson and Bhupinder S. Sethi On detecting spatial regularity in noisy images . . . . . . . . . . . . . . . . . 189--195 A. Arvind and C. Pandu Rangan Symmetric Min--Max heap: A simpler data structure for double-ended priority queue . . . . . . . . . . . . . . . . . 197--199 Alfredo De Santis and Giovanni Di Crescenzo and Oded Goldreich and Giuseppe Persiano The graph clustering problem has a perfect zero-knowledge interactive proof 201--206 V. A. Nepomniaschy Symbolic verification method for definite iteration over data structures 207--213
Oswin Aichholzer and Franz Aurenhammer and Reinhard Hainz New results on MWT subgraphs . . . . . . 215--219 P.-Y. Schobbens and J.-F. Raskin The logic of ``initially'' and ``next'': Complete axiomatization and complexity 221--225 L. J. García-Villalba and A. Fúster-Sabater On the general classification of nonlinear filters of $m$-sequences . . . 227--232 Masaaki Mizuno A structured approach for developing concurrent programs in Java . . . . . . 233--238 Joseph Cheriyan and Kurt Mehlhorn An analysis of the highest-level selection rule in the preflow-push max-flow algorithm . . . . . . . . . . . 239--242 K. Q. Yan and S. C. Wang and Y. H. Chin Consensus under unreliable transmission 243--248 D. Radhakrishnan and A. P. Preethy A parallel approach to direct analog-to-residue conversion . . . . . . 249--252 Marco A. Torres and Susumu Kuroyanagi and Akira Iwata The Self-Indexed Search Algorithm: A bit-level approach to minimal perfect hashing . . . . . . . . . . . . . . . . 253--258 Nader H. Bshouty and Lisa Higham and Jolanta Warpechowska-Gruca Meeting times of random walks on graphs 259--265
Stasys Jukna Linear codes are hard for oblivious read-once parity branching programs . . 267--269 Manfred Göbel A rewriting technique for universal polynomial invariants . . . . . . . . . 271--273 Zhaohui Liu and Wenci Yu and T. C. Edwin Cheng Scheduling groups of unit length jobs on two identical parallel machines . . . . 275--281 Marek Chrobak and Christoph Dürr Reconstructing $hv$-convex polyominoes from orthogonal projections . . . . . . 283--289 Yannick Saouter and Hervé Le Verge Computability of affine non-conditional recurrent systems . . . . . . . . . . . 291--295 Wen-Guey Tzeng and Chi-Ming Hu Inter-protocol interleaving attacks on some authentication and key distribution protocols . . . . . . . . . . . . . . . 297--302 H. Manos Construction of halvers . . . . . . . . 303--307
Robert Harper and John C. Mitchell Parametricity and variants of Girard's J operator . . . . . . . . . . . . . . . . 1--5 James F. Korsh and Paul LaFollette Loopless generation of Gray codes for $k$-ary trees . . . . . . . . . . . . . 7--11 Benjamin Barden and Ran Libeskind-Hadas and Janet Davis and William Williams On edge-disjoint spanning trees in hypercubes . . . . . . . . . . . . . . . 13--16 Cao An Wang and Francis Y. Chin and Bo Ting Yang Maximum weight triangulation and graph drawing . . . . . . . . . . . . . . . . 17--22 Antonín Ku\vcera On finite representations of infinite-state behaviours . . . . . . . 23--30 Jyrki Katajainen and Tomi A. Pasanen In-place sorting with fewer moves . . . 31--37 Samir Khuller and Anna Moss and Joseph (Seffi) Naor The budgeted maximum coverage problem 39--45 Hadas Shachnai and John J. Turek Multiresource malleable task scheduling to minimize response time . . . . . . . 47--52
W. Fernandez de la Vega and M. Karpinski On the approximation hardness of dense TSP and other path problems . . . . . . 53--55 F. Roussel and I. Rusu A linear algorithm to color $i$-triangulated graphs . . . . . . . . 57--62 M. D. Atkinson and J.-R. Sack Pop-stacks in parallel . . . . . . . . . 63--67 Roberto Barbuti and Nicoletta De Francesco and Antonella Santone and Gigliola Vaglini Abstract interpretation of trace semantics for concurrent calculi . . . . 69--78 Narn-Yih Lee and Tzonelih Hwang and Chih-Hung Wang The security of two ID-based multisignature protocols for sequential and broadcasting architectures . . . . . 79--81 Eli Biham and Dan Boneh and Omer Reingold Breaking generalized Diffie--Hellman modulo a composite is no easier than factoring . . . . . . . . . . . . . . . 83--87 L. Simpson and J. Goli\'c and M. Salmasizadeh and E. Dawson A fast correlation attack on multiplexer generators . . . . . . . . . . . . . . . 89--93 Arnold Rosenbloom On the sets of perfect matchings for two bipartite graphs . . . . . . . . . . . . 95--97 K. Rustan M. Leino and Raymie Stata Virginity: A contribution to the specification of object-oriented software . . . . . . . . . . . . . . . . 99--105
William E. Wright A refinement of replacement selection 107--111 Sanjay Jain On a question of nearly minimal identification of functions . . . . . . 113--117 Francesco Quaglia and Roberto Baldoni Exploiting intra-object dependencies in parallel simulation . . . . . . . . . . 119--125 David R. Powell and Lloyd Allison and Trevor I. Dix A versatile divide and conquer technique for optimal string alignment . . . . . . 127--139 Yefim Dinitz and Alon Itai and Michael Rodeh On an algorithm of Zemlyachenko for subtree isomorphism . . . . . . . . . . 141--146 Celina M. H. de Figueiredo and João Meidanis and Célia Picinin de Mello Total-chromatic number and chromatic index of dually chordal graphs . . . . . 147--152 Wen-Guey Tzeng Common modulus and chosen-message attacks on public-key schemes with linear recurrence relations . . . . . . 153--156
A. Bernasconi On the complexity of balanced Boolean functions . . . . . . . . . . . . . . . 157--163 E. Bertino and B. Catania and Limsoon Wong Finitely representable nested relations 165--173 Yangjun Chen Arc consistency revisited . . . . . . . 175--184 Amihood Amir and Ayelet Butman and Moshe Lewenstein Real scaled matching . . . . . . . . . . 185--190 Yen-Chun Lin and Chun-Keng Liu Finding optimal parallel prefix circuits with fan-out $2$ in constant time . . . 191--195 Kuo-Chan Huang and Feng-Jian Wang and Jyun-Hwei Tsai Two design patterns for data-parallel computation based on master-slave model 197--204
Harry Buhrman and Ronald de Wolf A lower bound for quantum search of an ordered list . . . . . . . . . . . . . . 205--209 P. Morillo and C. Padró and G. Sáez and J. L. Villar Weighted threshold secret sharing schemes . . . . . . . . . . . . . . . . 211--216 J. D. Emerald and K. G. Subramanian and D. G. Thomas A note on inferring uniquely terminating code languages . . . . . . . . . . . . . 217--222 Matthew Young-Lai Adding state merging to the DMC data compression algorithm . . . . . . . . . 223--228 Öjvind Johansson Simple distributed $\Delta+1$-coloring of graphs . . . . . . . . . . . . . . . 229--232 David Guijarro and Víctor Lavín and Vijay Raghavan Exact learning when irrelevant variables abound . . . . . . . . . . . . . . . . . 233--239 Suman Kumar Nath and Rezaul Alam Chowdhury and M. Kaykobad On average edge length of minimum spanning trees . . . . . . . . . . . . . 241--243 D. S. Franzblau Ear decomposition with bounds on ear length . . . . . . . . . . . . . . . . . 245--249 Srinivasa R. Arikati and Kurt Mehlhorn A correctness certificate for the Stoer--Wagner min-cut algorithm . . . . 251--254
W.-P. Hwang and C.-L. Wang In-place random list permutations . . . 255--257 C.-y. Chou and D. J. Guan and K.-l. Wang A dynamic fault-tolerant message routing algorithm for double-loop networks . . . 259--264 S. Crvenkovi\'c and I. Dolinka and Z. Ésik A note on equations for commutative regular languages . . . . . . . . . . . 265--267 E. Kindler and W. van der Aalst Liveness, fairness, and recurrence in Petri nets . . . . . . . . . . . . . . . 269--274
Yuh-Min Tseng and Jinn-Ke Jan Attacks on threshold signature schemes with traceable signers . . . . . . . . . 1--4 Andris Ambainis A note on quantum black-box complexity of almost all Boolean functions . . . . 5--7 Alak Kumar Datta and Ranjan Kumar Sen An efficient scheme to solve two problems for two-terminal series parallel graphs . . . . . . . . . . . . 9--15 Eric Torng and Patchrawat Uthaisombut A tight lower bound for the best-$\alpha$ algorithm . . . . . . . . 17--22 Qing Hu and Yixin Zhang and Xiaojun Shen Rearrangeable graphs . . . . . . . . . . 23--27 P. C. Chu Verbs are not cases: Applying case grammar to document retrieval . . . . . 29--34 Tatsuhiro Tsuchiya and Nobuhiko Ido and Tohru Kikuno Constructing Byzantine Quorum systems from combinatorial designs . . . . . . . 35--42 Limin Xiang and Kazuo Ushijima Rearranging scattered information on BSR 43--47
T. C. E. Cheng and G. Wang Two-machine flowshop scheduling with consecutive availability constraints . . 49--54 O. Goldreich and D. Micciancio and S. Safra and J.-P. Seifert Approximating shortest lattice vectors is not harder than approximating closest lattice vectors . . . . . . . . . . . . 55--61 T. Yamakami and A. C. Yao NQP$_C$ = co-C$_=$P . . . . . . . . . . 63--69 L. Xiang and K. Ushijima A theorem on the relation between BSR$_k$ and BSR$^+$ . . . . . . . . . . 71--73 C. M. Li A constraint-based approach to narrow search trees for satisfiability . . . . 75--80 S. Dobrev and I. Vr\uto Optimal broadcasting in hypercubes with dynamic faults . . . . . . . . . . . . . 81--85 S. Klav\vzar and J. Koolen and H. M. Mulder Graphs which locally mirror the hypercube structure . . . . . . . . . . 87--90 Y.-C. Lin and C.-S. Yeh Efficient parallel prefix algorithms on multiport message-passing systems . . . 91--95
Rainer Kemp A one-to-one correspondence between a class of leftist trees and binary trees 97--105 Maxime Crochemore and A. Czumaj and L. Gs\kaieniec and T. Lecroq and W. Plandowski and W. Rytter Fast practical multi-pattern matching 107--113 Mark Levene and George Loizou How to prevent interaction of functional and inclusion dependencies . . . . . . . 115--125 M. Dror and W. Kubiak and J. Y-T. Leung Tree precedence in scheduling: The strong-weak distinction . . . . . . . . 127--134 Amotz Bar-Noy and Magnús M. Halldórsson and Guy Kortsarz A matched approximation bound for the sum of a greedy coloring . . . . . . . . 135--140 P. C. P. Bhatt An interesting way to partition a number 141--148 Subhamoy Maitra and Palash Sarkar Hamming weights of correlation immune Boolean functions . . . . . . . . . . . 149--153 Marcos Kawazoe Aguilera and Sam Toueg A simple bivalency proof that $t$-resilient consensus requires $t+1$ rounds . . . . . . . . . . . . . . . . . 155--158 David A. Plaisted and Gregory Kucherov The complexity of some complementation problems . . . . . . . . . . . . . . . . 159--165 Prasad Jayanti and Tushar Deepak Chandra and Sam Toueg The cost of graceful degradation for omission failures . . . . . . . . . . . 167--172
Jürgen Dassow and Gheorghe P\uaun Min of Mat is not necessarily Mat . . . 175--177 J. L. Ramírez Alfonsín Cyclic arrangements and Roudneff's conjecture in the space . . . . . . . . 179--182 Sarnath Ramnath and Venkatesh Raman Selecting small ranks in EREW PRAM . . . 183--186 Zvi Lotker and Boaz Patt-Shamir A note on randomized mutual search . . . 187--191 Arkadiusz Wojna Counter machines . . . . . . . . . . . . 193--197 Lhouari Nourine and Olivier Raynaud A fast algorithm for building lattices 199--204 Yu-Feng Lan and Yue-Li Wang and Hitoshi Suzuki A linear-time algorithm for solving the center problem on weighted cactus graphs 205--212 Jong Soo Kim and Sung Tak Kang and Myoung Ho Kim On temporal aggregate processing based on time points . . . . . . . . . . . . . 213--220 Manuel Abellanas and Ferran Hurtado and Pedro A. Ramos Structural tolerance and Delaunay triangulation . . . . . . . . . . . . . 221--227 Vasco T. Vasconcelos and António Ravara Communication errors in the $\pi$-calculus are undecidable . . . . . 229--233 Antonios Symvonis A note on deflection worm routing on meshes . . . . . . . . . . . . . . . . . 235--239 Chun-yen Chou and D. J. Guan and Kuei-lin Wang Erratum to ``A dynamic fault-tolerant message routing algorithm for double-loop networks'', Information Processing Letters \bf 70(6) (1999) 259--264 . . . . . . . . . . . . . . . . 241--241 Anonymous Index . . . . . . . . . . . . . . . . . 243--244 Anonymous Index . . . . . . . . . . . . . . . . . 245--246
F. Montoya Vitini and J. Muñoz Masqué and A. Peinado Domínguez Linear complexity of the $x^2 \bmod p$ orbits . . . . . . . . . . . . . . . . . 3--7 Antonín Ku\vcera Regularity of normed PA processes . . . 9--17 Y. Wang and K. Inoue and A. Ito and T. Okazaki A note on self-modifying finite automata 19--24 Z. M. Ma and W. J. Zhang and W. Y. Ma Assessment of data redundancy in fuzzy relational databases based on semantic inclusion degree . . . . . . . . . . . . 25--29 John A. Mount Estimating the range of a function in an online setting . . . . . . . . . . . . . 31--35 Dong-Yul Ra and George C. Stockman A new one pass algorithm for estimating stochastic context-free grammars . . . . 37--45 Jurg Nievergelt and Narsingh Deo and Ambros Marzetta Memory-efficient enumeration of constrained spanning trees . . . . . . . 47--53 Chun-Nan Hung and Lih-Hsing Hsu and Ting-Yi Sung Christmas tree: A versatile $1$-fault-tolerant design for token rings . . . . . . . . . . . . . . . . . 55--63 Gonzalo Navarro and Ricardo Baeza-Yates Very fast and simple approximate string matching . . . . . . . . . . . . . . . . 65--70 Valmir C. Barbosa and Jayme L. Szwarcfiter Generating all the acyclic orientations of an undirected graph . . . . . . . . . 71--74
Chien-Yuan Chen and Chin-Chen Chang A fast modular multiplication algorithm for calculating the product AB modulo N 77--81 Martin Matamala and Klaus Meer On the computational structure of the connected components of a hard problem 83--90 Michel Raynal and Frédéric Tronel Restricted failure detectors: Definition and reduction protocols . . . . . . . . 91--97 G. M. Megson and Xiaofan Yang and Xiaoping Liu Honeycomb tori are Hamiltonian . . . . . 99--103 Samir Khuller An $O(|V|^2)$ algorithm for single connectedness . . . . . . . . . . . . . 105--107 Chang-Hsiung Tsai and Chun-Nan Hung and Lih-Hsing Hsu and Chung-Haw Chang The correct diameter of trivalent Cayley graphs . . . . . . . . . . . . . . . . . 109--111 Ioan I. Macarie and Joel I. Seiferas Amplification of slight probabilistic advantage at absolutely no cost in space 113--118 Yann Verhoeven Random $2$-SAT and unsatisfiability . . 119--123 Christian Lavault and S. Mohamed Sedjelmaci Worst-case analysis of Weber's GCD algorithm . . . . . . . . . . . . . . . 125--130 Shien-Ching Hwang and Gen-Huey Chen A note on cyclic-cubes . . . . . . . . . 131--135 Tiziana Calamoneri and Annalisa Massini An optimal layout of multigrid networks 137--141 K. Sridharan Computing two penetration measures for curved $2$D objects . . . . . . . . . . 143--148
Xiaoyi Jiang and Horst Bunke Optimal vertex ordering of graphs . . . 149--154 Petr Jan\vcar A note on well quasi-orderings for powersets . . . . . . . . . . . . . . . 155--160 Karen Aardal and Fabián A. Chudak and David B. Shmoys A $3$-approximation algorithm for the $k$-level uncapacitated facility location problem . . . . . . . . . . . . 161--167 C. Blundo and A. De Santis and A. Giorgio Gaggia Probability of shares in secret sharing schemes . . . . . . . . . . . . . . . . 169--175 George Lagogiannis and Christos Makris and Athanasios Tsakalidis A new algorithm for rectangle enclosure reporting . . . . . . . . . . . . . . . 177--182 Ramesh Krishnamurti and Daya Ram Gaur An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems . . . . . . . . . 183--188 Gyung-Ok Lee and Kwang-Moo Choe An LR parser with pre-determined reduction goals . . . . . . . . . . . . 189--196 Sven Kosub A note on unambiguous function classes 197--203 Jae-Young Chang and Sang-Goo Lee Extended conditions for answering an aggregate query using materialized views 205--212 Chien-Hung Huang and Ju-Yuan Hsiao and R. C. T. Lee An optimal embedding of cycles into incomplete hypercubes . . . . . . . . . 213--218 Anonymous Index . . . . . . . . . . . . . . . . . 219--220 Anonymous Index . . . . . . . . . . . . . . . . . 221--222
Rajesh P. N. Rao and Jörg Rothe and Osamu Watanabe Corrigendum to ``Upward separation for FewP and related classes'', Information Processing Letters \bf 52(4) (1994) 175--180 . . . . . . . . . . . . . . . . 89--89
Samir Khuller Addendum to ``An $O(|V|^2)$ algorithm for single connectedness'', [Information Processing Letters 72(3--4) (1999) 105--107] . . . . . . . . . . . . . . . 263--263
Gerard J. Chang Corrigendum to ``The path-partition problem in block graphs'': [Information Processing Letters \bf 52 (1994) 317--322] . . . . . . . . . . . . . . . 293--293
E. Brinksmeier Precision fabrication research and development . . . . . . . . . . . . . . 25--109 Eugene Rivin Precision fabrication technology in the former Soviet Union and other East European countries . . . . . . . . . . . 111--131
Hirotoshi Honma and Kodai Abe and Shigeru Masuyama Erratum and addendum to ``A linear time algorithm for finding all hinge vertices of a permutation graph'' [Information Processing Letters \bf 59 (2) (1996) 103--107] . . . . . . . . . . . . . . . 891--894