Theoretical Computer Science, Volume 339

Volume 339, Number 1, June 2005

• Tero Harju, Juhani Karhumäki, Antonio Restivo:
  Preface. 1-2
  
• Sergei I. Adian:
  Divisibility problem for one relator monoids. 3-6
  
• James D. Currie:
  Pattern avoidance: themes and variations. 7-18
  
• Narad Rampersad, Jeffrey Shallit, Ming-wei Wang:
  Avoiding large squares in infinite binary words. 19-34
  
• Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov:
  Space efficient search for maximal repetitions. 35-48
  
• Sorin Constantinescu, Lucian Ilie:
  Generalised fine and Wilf's theorem for arbitrary number of periods. 49-60
  
• Stepan Holub:
  A proof of the extended Duval's conjecture. 61-67
  
• Anna E. Frid:
  Sequences of linear arithmetical complexity. 68-87
  
• Isabel M. Araújo, Véronique Bruyère:
  Sturmian words and a criterium by Michaux-Villemaire. 88-102
  
• Florence Levé, Gwénaël Richomme:
  On a conjecture about finite fixed points of morphisms. 103-128
  
• Florent Hivert, Jean-Christophe Novelli, Jean-Yves Thibon:
  The algebra of binary search trees. 129-165
  

Volume 339, Number 2-3, June 2005

• Yijia Chen, Jörg Flum, Martin Grohe:
  Machine-based methods in parameterized complexity theory. 167-199
  
• Andreas Maletti:
  HASSE diagrams for classes of deterministic bottom-up tree-to-tree-series transformations. 200-240
  
• Shengyu Zhang:
  On the power of Ambainis lower bounds. 241-256
  
• Cheng-Kuan Lin, Hua-Min Huang, Lih-Hsing Hsu:
  The super connectivity of the pancake graphs and the super laceability of the star graphs. 257-271
  
• Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos:
  Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. 272-292
  
• Yong He, Yiwei Jiang:
  Optimal semi-online preemptive algorithms for machine covering on two uniform machines. 293-314
  
• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman:
  Short length Menger's theorem and reliable optical routing. 315-332
  
• Peter Damaschke, Zhen Zhou:
  On queuing lengths in on-line switching. 333-343
  
• Murray J. Elder:
  A context-free and a 1-counter geodesic language for a Baumslag-Solitar group. 344-371