Theoretical Computer Science, Volume 145

Volume 145, Numbers 1&2, 10 July 1995

• G. Braga, G. Cattaneo, Paola Flocchini, C. Quaranta Vogliotti:
  Pattern Growth in Elementary Cellular Automata. 1-26
  
• G. Srikrishna, C. Pandu Rangan:
  Optimal Parallel Algorithms for Path Problems on Planar Graphs. 27-43
  
• Yuri Breitbart, Harry B. Hunt III, Daniel J. Rosenkrantz:
  On the Size of Binary Decision Diagrams Representing Boolean Functions. 45-69
  
• Ernst L. Leiss:
  Implicit Language Equations: Existence and Uniqueness of Solutions. 71-93
  
• Krzysztof Diks, Evangelos Kranakis, Adam Malinowski, Andrzej Pelc:
  Anonymous Wireless Rings. 95-109
  
• Nadia Creignou:
  The Class of Problems That are Linearly Equivalent to Satisfiability or a Uniform Method for Proving NP-Completeness. 111-145
  
• Iain A. Stewart:
  Complete Problems for Monotone NP. 147-157
  
• Frank Drewes, Annegret Habel, Hans-Jörg Kreowski, Stefan Taubenberger:
  Generating Self-Affine Fractals by Collage Grammars. 159-187
  
• Jiazhen Cai, Robert Paige:
  Using Multiset Discrimination to Solve Language Processing Problems Without Hashing. 189-228
  
• Christophe Reutenauer, Marcel Paul Schützenberger:
  Variétés et fonctions rationnelles. 229-240
  
• Ker-I Ko:
  A Polynomial-Time Computable Curve whose Interior has a Nonrecursive Measure. 241-270
  
• Ofer Biran, Shlomo Moran, Shmuel Zaks:
  Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks. 271-290
  
• Seymour Ginsburg, Katsumi Tanaka:
  Interval Queries on Object Histories. 291-316
  
• Martin Middendorf:
  On Finding Minimal, Maximal, and Consistent Sequences over a Binary Alphabet. 317-327
  
• Beverly Jamison, Stephan Olariu:
  A Linear-Time Recognition Algorithm for P4-Reducible Graphs. 329-344
  
• Liang Zhang, Zhonghui Shen:
  Completion of Recognizable Bifix Codes. 345-355
  
• Gary Benson:
  A Space Efficient Algorithm for Finding the Best Nonoverlapping Alignment Score. 357-369
  
• Lane A. Hemaspaandra, Zhigen Jiang:
  P-Selectivity: Intersections and Indices. 371-380
  
• Shang-Hua Teng:
  Independent Sets Versus Perfect Matchings. 381-390
  
• Oded Maler:
  A Decomposition Theorem for Probabilistic Transition Systems. 391-396