Theoretical Computer Science, Volume 380

Volume 380, Numbers 1-2, June 2007

• Giuseppe F. Italiano, Catuscia Palamidessi:
  Preface. 1
  

• Chen Avin, Gunes Ercal:
  On the cover time and mixing time of random geometric graphs. 2-22
  
• Eugen Czeizler, Jarkko Kari:
  A tight linear bound on the synchronization delay of bijective automata. 23-36
  
• Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas:
  Faster algorithms for finding lowest common ancestors in directed acyclic graphs. 37-46
  
• Martin Dietzfelbinger, Christoph Weidling:
  Balanced allocation and dictionaries with tightly packed constant size bins. 47-68
  
• Manfred Droste, Paul Gastin:
  Weighted automata and weighted logics. 69-86
  
• Martin Gairing, Burkhard Monien, Andreas Woclaw:
  A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. 87-99
  
• Juraj Hromkovic, Georg Schnitger:
  Comparing the size of NFAs with and without epsilon-transitions. 100-114
  
• Pascal Koiran, Vincent Nesme, Natacha Portier:
  The quantum query complexity of the abelian hidden subgroup problem. 115-126
  
• Mihai Patrascu, Corina E. Tarnita:
  On dynamic bit-probe complexity. 127-142
  
• Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell:
  Recursively defined metric spaces without contraction. 143-163
  
• Damien Pous:
  New up-to techniques for weak bisimulation. 164-180
  
• Michael W. Mislove:
  Discrete random variables over domains. 181-198
  
• Martin Grohe, Christoph Koch, Nicole Schweikardt:
  Tight lower bounds for query processing on streaming and external memory data. 199-217
  

Volume 380, Number 3, June 2007

• Srecko Brlek, Christophe Reutenauer:
  Preface. 219
  

• Boris Adamczewski, Jean-Paul Allouche:
  Reversals and palindromes in continued fractions. 220-237
  
• Petr Ambroz, Christiane Frougny:
  On alpha-adic expansions in Pisot bases. 238-250
  
• Pierre Arnoux, Valérie Berthé, Thomas Fernique, Damien Jamet:
  Functional stepped surfaces, flips, and generalized substitutions. 251-265
  
• Peter Balázi, Zuzana Masáková, Edita Pelantová:
  Factor versus palindromic complexity of uniformly recurrent infinite words. 266-275
  
• Valérie Berthé, Bertrand Nouvel:
  Discrete rotations and symbolic dynamics. 276-285
  
• Jean-Pierre Borel:
  A geometrical characterization of factors of multidimensional Billiard words and some applications. 286-303
  
• Julien Cassaigne, Anna E. Frid:
  On the arithmetical complexity of Sturmian words. 304-316
  
• Thomas Fernique:
  Local rule substitutions and stepped surfaces. 317-329
  
• Amy Glen:
  Powers in a class of A-strict standard episturmian words. 330-354
  
• Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux:
  Extension of the decidability of the marked PCP to instances with unique blocks. 355-362
  
• Stepan Holub, Juha Kortelainen:
  On systems of word equations with simple loop sets. 363-372
  
• Lucian Ilie:
  A note on the number of squares in a word. 373-376
  
• Arto Lepistö, Francesco Pappalardi, Kalle Saari:
  Transposition invariant words. 377-387
  
• Pascal Ochem:
  Letter frequency in infinite repetition-free words. 388-392
  
• Gwénaël Richomme:
  Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words. 393-400
  
• Maurice H. ter Beek, Jetty Kleijn:
  Infinite unfair shuffles and associativity. 401-410