Theoretical Computer Science, Volume 215

Volume 215, Numbers 1-2, 28 February 1999

• Yacine Boufkhad, Olivier Dubois:
  Length of Prime Implicants and Number of Solutions of Random CNF Formulae. 1-30
  
• Gilles Didier:
  Caractérisation des N-écritures et application à l'étude des suites de complexité ultimement n+c^ste. 31-49
  
• Yaghout Nourani, Bjarne Andresen:
  Exploration of NP-hard Enumeration Problems by Simulated Annealing - the Spectrum Values of Permanents. 51-68
  
• Djelloul Ziadi, Jean-Marc Champarnaud:
  An Optimal Parallel Algorithm to Convert a Regular Expression into its Glushkov Automaton. 69-87
  
• Ryuhei Uehara, Zhi-Zhong Chen, Xin He:
  Fast RNC and NC Algorithms for Maximal Path Sets. 89-98
  
• Mireille Clerbout, Yves Roos, Isabelle Ryl:
  Synchronization Languages. 99-121
  
• Johann Hagauer, Wilfried Imrich, Sandi Klavzar:
  Recognizing Median Graphs in Subquadratic Time. 123-136
  
• Martin Middendorf, Welf Löwe, Wolf Zimmermann:
  Scheduling Inverse Trees Under the Communication Model of the LogP-Machine. 137-168
  
• Valeria Mihalache:
  Decidability Problems in Grammar Systems. 169-189
  
• Dora Giammarresi, Rosa Montalbano:
  Deterministic Generalized Automata. 191-208
  
• Oh-Heum Kwon, Kyung-Yong Chwa:
  Scheduling Parallel Tasks with Individual Deadlines. 209-223
  
• Bruno Durand, Anne-Cécile Fabret:
  On the Complexity of Deadlock Detection in Families of Planar Nets. 225-237
  
• Martin Kutrib:
  Pushdown Cellular Automata. 239-261
  
• Peter Buchholz:
  Exact Performance Equivalence: An Equivalence Relation for Stochastic Automata. 263-287
  
• Pascal Koiran:
  Elimination of Parameters in the Polynomial Hierarchy. 289-304
  
• Thomas Andreae, Felix Hartenstein, Andrea Wolter:
  A Two-Person Game on Graphs Where Each Player Tries to Encircle his Opponent's Men. 305-323
  
• Rotislav I. Grigorchuk, A. Machì:
  An Example of an Indexed Language of Intermediate Growth. 325-327
  
• Véronique Bruyère, Christophe Reutenauer:
  A Proof of Choffrut's Theorem on Subsequential Functions. 329-335
  
• Arne Andersson, Peter Bro Miltersen, Mikkel Thorup:
  Fusion Trees can be Implemented with AC⁰ Instructions Only. 337-344
  
• Herbert Fischer, Harley Flanders:
  A Minimal Code List. 345-348
  
• Erzsébet Csuhaj-Varjú, György Vaszil:
  On the Computational Completeness of Context-Free Parallel Communicating Grammar Systems. 349-358
  
• Lusheng Wang, Xiaohua Jia:
  Fixed Topology Steiner Trees and Spanning Forests. 359-370
  
• Philippe Flajolet:
  Singularity Analysis and Asymptotics of Bernoulli Sums. 371-381
  
• Jean-Michel Autebert:
  Some Results about Centralized PC Grammar Systems. 383-398