Theoretical Computer Science, Volume 237

Volume 237, Numbers 1-2, 28 April 2000

• Bruno Courcelle:
  The monadic second-order logic of graphs XII: planar graphs and planar maps. 1-32
  
• Yongge Wang:
  Resource bounded randomness and computational complexity. 33-55
  
• Francesco M. Malvestuto, Marina Moscarini:
  Decomposition of a hypergraph by partial-edge separators. 57-79
  
• Jean-Camille Birget:
  Reductions and functors from problems to word problems. 81-104
  
• Petra Schuurman, Gerhard J. Woeginger:
  A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. 105-122
  
• Paola Alimonti, Viggo Kann:
  Some APX-completeness results for cubic graphs. 123-134
  
• Niculae Mandache:
  On the computational power of context-free PC grammar systems. 135-148
  
• Andries P. J. van der Walt, Sigrid Ewert:
  A shrinking lemma for random forbidding context languages. 149-158
  
• Viliam Geffert, Jyrki Katajainen, Tomi Pasanen:
  Asymptotically efficient in-place merging. 159-181
  
• Changwook Kim, Ivan Hal Sudborough:
  Leftmove-bounded picture languages. 183-195
  
• Rimli Sengupta, H. Venkateswaran:
  Non-cancellative Boolean circuits: A generalization of monotone boolean circuits. 197-212
  
• Siu-Wing Cheng:
  The Steiner tree problem for terminals on the boundary of a rectilinear polygon. 213-238
  
• Jean Senellart:
  Fast pattern matching in indexed texts. 239-262
  
• Alberto Apostolico, Valentin E. Brimkov:
  Fibonacci arrays and their two-dimensional repetitions. 263-273
  
• Cristopher Moore, James P. Crutchfield:
  Quantum automata and quantum grammars. 275-306
  
• Petr Kurka, Alejandro Maass:
  Realtime subshifts. 307-325
  
• Chung Keung Poon:
  A space lower bound for st-connectivity on node-named JAGs. 327-345
  
• Kamal Lodaya, Pascal Weil:
  Series-parallel languages and the bounded-width property. 347-380
  
• Hiroaki Tohyama, Akeo Adachi:
  Complexity of path discovery game problems. 381-406
  
• U. K. Sarkar:
  On the design of a constructive algorithm to solve the multi-peg towers of Hanoi problem. 407-421
  
• Alexander Meduna:
  Terminating left-hand sides of scattered context productions M. Nivat. 423-427
  
• Janos Simon, Shi-Chun Tsai:
  On the bottleneck counting argument. 429-437
  
• James A. Anderson:
  The intersection of retracts of A*. 439-445
  
• Bruce E. Litow:
  On Hadamard square roots of unity. 447-454
  
• Gonzalo Navarro:
  Improved approximate pattern matching on hypertext. 455-463
  
• Viliam Geffert:
  A variant of inductive counting. 465-475
  
• Satyanarayana V. Lokam:
  On the rigidity of Vandermonde matrices. 477-483
  
• Kazuo Iwama, Yahiko Kambayashi, Kazuya Takaki:
  Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. 485-494