Theoretical Computer Science, Volume 345

Volume 345, Number 1, 21 November 2005

• Kurt Jensen, Andreas Podelski:
  Special issue. 1
  
• Christel Baier, Holger Hermanns, Joost-Pieter Katoen, Boudewijn R. Haverkort:
  Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes. 2-26
  
• Denis Lugiez, Peter Niebert, Sarah Zennou:
  A partial order semantics approach to the clock explosion problem of timed automata. 27-59
  
• Jaco Geldenhuys, Antti Valmari:
  More efficient on-the-fly LTL verification with Tarjan's algorithm. 60-82
  
• Orna Kupferman, Moshe Y. Vardi:
  From complementation to certification. 83-100
  
• Kenneth L. McMillan:
  An interpolating theorem prover. 101-121
  
• Zhendong Su, David Wagner:
  A class of polynomially solvable range constraints for interval analysis without widenings. 122-138
  
• Luca de Alfaro, Marco Faella, Thomas A. Henzinger, Rupak Majumdar, Mariëlle Stoelinga:
  Model checking discounted temporal properties. 139-170
  

Volume 345, Numbers 2-3, 22 November 2005

• Václav Koubek, Jan Kratochvíl:
  Preface. 171-172
  

• Sebastian Bab, Arfst Nickelsen:
  One query reducibilities between partial information classes. 173-189
  
• Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin:
  A hierarchy of shift equivalent sofic shifts. 190-205
  
• Martin Beaudry, José M. Fernandez, Markus Holzer:
  A common algebraic description for probabilistic and quantum computations^, . 206-234
  
• Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari:
  A new dimension sensitive property for cellular automata. 235-247
  
• Alina Beygelzimer, Mitsunori Ogihara:
  The enumerability of P collapses P to NC. 248-259
  
• Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
  Generation problems. 260-295
  
• Elena Czeizler:
  The non-parametrizability of the word equation xyz=zvx: A short proof. 296-303
  
• Michael Domaratzki, Kai Salomaa:
  Decidability of trajectory-based equations. 304-330
  
• Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg:
  Graph exploration by a finite automaton. 331-344
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  All superlinear inverse schemes are coNP-hard. 345-358
  
• Lucian Ilie, Pascal Ochem, Jeffrey Shallit:
  A generalization of repetition threshold. 359-369
  
• Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra:
  Universal test for quantum one-way permutations. 370-385
  
• Troy Lee, Andrei E. Romashchenko:
  Resource bounded symmetry of information revisited. 386-405
  
• Gustav Nordh:
  The complexity of equivalence and isomorphism of systems of equations over finite groups. 406-424
  
• Alexander Okhotin:
  The dual of concatenation. 425-447
  
• Victor L. Selivanov, Klaus W. Wagner:
  A reducibility for the dot-depth hierarchy. 448-472
  
• Klaus Wich:
  Sublogarithmic ambiguity. 473-504