12. STACS 1995: Munich, Germany

Invited Talk

• Wolfgang Thomas:
  On the Synthesis of Strategies in Infinite Games. 1-13
  

Complexity Theory I

• Guy Louchard:
  Finding the Maximum with Linear Error Probabilities: A Sequential Analysis Approach. 14-25
  
• David W. Juedes, Jack H. Lutz:
  Completeness and Weak Completeness Under Polynomial-Size Circuits. 26-37
  

Cryptography

• Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar:
  Communication Complexity of Key Agreement on Small Ranges. 38-49
  
• Yenjo Han, Lane A. Hemaspaandra:
  Pseudorandom Generators and the Frequency of Simplicity. 50-59
  

Complexity Theory II

• Ulrich Hertrampf:
  Classes of Bounded Counting Type and their Inclusion Relations. 60-70
  
• Frederic Green:
  Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates. 71-82
  
• Matthias Krause:
  On Realizing Iterated Multiplication by Small Depth Threshold Circuits. 83-94
  
• Bruno Durand:
  A Random NP-Complete Problem for Inversion of 2D Cellular Automata. 95-106
  

Automata Theory I

• Isabelle Fagnot:
  On the Subword Equivalence Problem for Infinite Words. 107-118
  
• Emmanuelle Garel:
  On the Separators on an Infinite Word Generated by a Morphism. 119-130
  
• Angelo Monti, Adriano Peron:
  Systolic Tree Omega-Languages. 131-142
  
• Sriram C. Krishnan, Anuj Puri, Robert K. Brayton:
  Structural Complexity of Omega-Automata. 143-156
  

Algorithms

• Torsten Minkwitz:
  Algorithms Explained by Symmetries. 157-167
  
• Paul F. Fischer, Franco P. Preparata, John E. Savage:
  Generalized Scans and Tri-Diagonal Systems. 168-180
  
• Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter:
  Two-Dimensional Pattern Matching in Linear Time and Small Space. 181-192
  
• Hristo Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis:
  On-line and Dynamic Algorithms for Shorted Path Problems. 193-204
  

Logic

• Marco Cadoli, Francesco M. Donini, Marco Schaerf:
  On Compact Representations of Propositional Circumscription. 205-216
  
• Giovanna D'Agostino, Angelo Montanari, Alberto Policriti:
  A Set-Theoretic Translation Method for (Poly)modal Logics. 217-228
  
• Oded Maler, Amir Pnueli, Joseph Sifakis:
  On the Synthesis of Discrete Controllers for Timed Systems (An Extended Abstract). 229-242
  
• Michele Boreale, Davide Sangiorgi:
  A Fully Abstract Semantics for Causality in the Pi-Calculus. 243-254
  

Theory of Parallel Computing I

• Juraj Hromkovic, Krzysztof Lorys, Przemyslawa Kanarek, Ralf Klasing, Walter Unger, Hubert Wagener:
  On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks. 255-266
  
• Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann:
  Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations. 267-278
  
• Michele Flammini, Giorgio Gambosi, Sandro Salomone:
  Interval Routing Schemes. 279-290
  
• Friedhelm Meyer auf der Heide, Berthold Vöcking:
  A Packet Routing Protocol for Arbitrary Networks. 291-302
  

Automata Theory II

• Christiane Bercoff:
  A Family of Tag Systems for Paperfolding Sequences. 303-312
  
• Gerhard Buntrock, Friedrich Otto:
  Growing Context-Sensitive Languages and Church-Rosser Languages. 313-324
  
• Dora Giammarresi, Rosa Montalbano:
  Deterministic Generalized Automata. 325-336
  
• Piotr Indyk:
  Optimal Simulation of Automata by Neural Nets. 337-348
  

Invited Talk

• Albert R. Meyer:
  Concurrent Process Equivalences: Some Decision Problems (Abstract). 349
  

Communication Theory

• Pavol Duris, José D. P. Rolim:
  Optimal Lower Bounds on the Multiparty Communication Complexity. 350-360
  
• László Babai, Peter G. Kimmel, Satyanarayana V. Lokam:
  Simultaneous Messages vs. Communication. 361-372
  

Automata Theory III

• Véronique Bruyère, Clelia de Felice:
  Coding and Strong Coding in Trace Monoids. 373-384
  
• Volker Diekert, Anca Muscholl, Klaus Reinhardt:
  On Codings of Traces. 385-396
  

Graph Theory, Data Bases

• Arvind Gupta, Naomi Nishimura:
  Finding Largest Common Embeddable Subtrees. 397-408
  
• Damon Kaller, Arvind Gupta, Thomas C. Shermer:
  The Chi-t-Coloring Problem. 409-420
  
• Sotiris E. Nikoletseas, Paul G. Spirakis:
  Expander Properties in Random Regular Graphs with Edge Faults. 421-432
  
• Danièle Gardy, Guy Louchard:
  Dynamic Analysis of the Sizes of Relations. 433-444
  

Automata Theory IV

• Danny Raz:
  On Slender Context-free Languages. 445-454
  
• Valentin M. Antimirov:
  Partial Derivates of Regular Expressions and Finite Automata Constructions. 455-466
  
• Felipe Bracho, Manfred Droste, Dietrich Kuske:
  Dependence Orders for Computations of Concurrent Automata. 467-478
  
• Anne-Cécile Fabret, Antoine Petit:
  On the Undecidability of Deadlock Detection in Families of Nets. 479-490
  

Theory of Parallel Computing II

• Christine Rüb:
  On the Average Running Time of Odd-Even Merge Sort. 491-502
  
• Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt, Peter Rossmanith:
  Optimal Average Case Sorting on Arrays. 503-514
  

Complexity Theory III

• Martin Strauss:
  Normal Numbers and Sources for BPP. 515-526
  
• Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp:
  Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). 527-538
  

Computational Geometry

• Peter Damaschke:
  Line Segmentation of Digital Curves in Parallel. 539-549
  
• Martin Kummer, Marcus Schäfer:
  Computability of Convex Sets (Extended Abstract). 550-561
  
• Thomas Ottmann, Sven Schuierer, Subbiah Soundaralakshmi:
  Enumerating Extreme Points in Higher Dimensions. 562-570
  
• Sylvain Petitjean:
  The Number of Views of Piecewise-Smooth Algebraic Objects. 571-582
  

Complexity Theory IV

• Ioan I. Macarie:
  On the Structure of Log-Space Probabilistic Complexity Classes (Extended Abstract). 583-596
  
• Lance Fortnow, Martin Kummer:
  Resource-Bounded Instance Complexity (Extended Abstract). 597-608
  
• Harry Buhrman, Montserrat Hermo:
  On the Sparse Set Conjecture for Sets with Low Denisty. 609-618
  
• Stephen A. Fenner, Lance Fortnow:
  Beyond P^(NP) - NEXP. 619-627
  
• Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
  Malign Distributions for Average Case Circuit Complexity. 628-639
  

Invited Talk

• Didier Arquès, Christian J. Michel:
  A Prossible Code in the Genetic Code. 640-651