15. SWAT 1974: New Orleans, Louisiana, USA

Session I

• Jack W. Carlyle, Sheila A. Greibach, Azaria Paz:
  A Two-Dimensional Generating System Modeling Growth by Binary Cell Division (Preliminary Report). 1-12
  
• Juris Hartmanis, Janos Simon:
  On the Power of Multiplication in Random Access Machines. 13-23
  
• José Lucas Rangel:
  The Equivalence Problem for Regular Expressions over one Letter Is Elementary. 24-27
  
• Sartaj Sahni, Teofilo F. Gonzalez:
  P-Complete Problems and Approximate Solutions. 28-32
  
• Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II:
  Approximate Algorithms for the Traveling Salesperson Problem. 33-42
  

Session II

• Emily P. Friedman:
  Relationships between Monadic Recursion Schemes and Deterministic Context-Free Languages. 43-51
  
• Bruno Courcelle:
  Recursive Schemes, Algebraic Trees and Deterministic Languages. 52-62
  
• Joseph A. Goguen, James W. Thatcher:
  Initial Algebra Semantics. 63-77
  
• Christoph M. Hoffmann, Lawrence H. Landweber:
  Axiomatic Equivalence of Programs with Structured Variables. 78-83
  
• Nobuki Tokura, Tadao Kasami, Shukichi Furuta:
  Ianov Schemas Augmented by a Pushdown Memory. 84-94
  

Session III

• Ronald L. Rivest:
  On Hash-Coding Algorithms for Partial-Match Retrieval (Extended Abstract). 95-103
  
• Alfred V. Aho, Daniel S. Hirschberg, Jeffrey D. Ullman:
  Bounds on the Complexity of the Longest Common Subsequence Problem (Extended Abstract). 104-109
  
• Andrew Chi-Chih Yao:
  Bounds on Selection Networks. 110-116
  
• H. T. Kung:
  On the Computational Complexity of Finding the Maxima of a Set of Vectors. 117-121
  
• Ronald L. Rivest:
  On Self-Organizing Sequential Search Heuristics. 122-126
  
• Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman:
  Operations on Sparse Relations and Efficient Algorithms for Grammar Problems (Extended Abstract). 127-132
  

Session IV

• John P. Hayes:
  Minimization of Fanout in Switching Networks. 133-139
  
• Edmund A. Lamagna, John E. Savage:
  Combinational Complexity of Some Monotone Functions. 140-144
  
• Pawel Kerntopf:
  On Boolean Functions Having Maximal Number of Subfunction Classes. 205-211
  
• Richard J. Lipton, Lawrence Snyder, Yechezkel Zalcstein:
  A Comparative Study of Models of Parallel Computation. 145-155
  
• Michel Hack:
  The Recursive Equivalence of the Reachability Problem and the Liveness Problem for Petri Nets and Vector Addition Systems. 156-164
  

Session V

• Robert P. Daley:
  Non-Complex Sequences: Characterizations and Examples. 165-169
  
• Zvi Galil:
  Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation. 170-177
  
• Theodore P. Baker:
  ``Natural'' Properties of Flowchart Complexity Measures. 178-184
  
• Alan J. Demers:
  Skeletal LR Parsing. 185-198
  
• Armin B. Cremers, Seymour Ginsburg:
  Characterization of Context-Free Grammatical Families. 199-204
  

Last update Fri May 25 08:14:14 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page