14. STACS 1997: Lübeck, Germany

Invited Paper

• Bernhard Steffen:
  Unifying Models. 1-20
  

Algorithms I

• Gerth Stølting Brodal:
  Predecessor Queries in Dynamic Integer Sets. 21-32
  
• Paolo Giulio Franciosa, Daniele Frigioni, Roberto Giaccio:
  Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs. 33-46
  

Automata Theory I

• Robert Koch, Norbert Blum:
  Greibach Normal Form Transformation, Revisited. 47-54
  
• Juraj Hromkovic, Sebastian Seibert, Thomas Wilke:
  Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata. 55-66
  

Algorithms II

• Christophe Fiorio, Jens Gustedt:
  Memory Management for Union-Find Algorithms. 67-79
  
• Matthias Schröder:
  Fast Online Multiplication of Real Numbers. 81-92
  

Structural Complexity I

• Harald Hempel, Gerd Wechsung:
  The Operators min and max on the Polynomial Hierarchy. 93-104
  
• Harry Buhrman, Lance Fortnow:
  Resource-Bounded Kolmogorov Complexity Revisited. 105-116
  

Probabilism

• Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger:
  Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. 117-128
  
• Maciej Liskiewicz:
  Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes. 129-140
  
• Claudia Bertram-Kretzberg, Hanno Lefmann:
  MOD_p-tests, Almost Independence and Small Probability Spaces (Extended Abstract). 141-152
  

Specification and Verification

• Luca de Alfaro, Arjun Kapur, Zohar Manna:
  Hybrid Diagrams: A Deductive-Algorithmic Approach to Hybrid System Verification. 153-164
  
• Luca de Alfaro:
  Temporal Logics for the Specification of Performance and Reliability. 165-176
  
• Carsten Weise, Dirk Lenzkes:
  Efficient Scaling-Invariant Checking of Timed Bisimulation. 177-188
  

Boolean Functions

• Martin Dietzfelbinger:
  Gossiping and Broadcasting versus Computing Functions in Networks. 189-200
  
• Stephan Waack:
  On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams. 201-212
  
• Christoph Meinel, Anna Slobodová:
  A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams. 213-224
  

Logic and Learning

• John Case, Efim B. Kinber, Arun Sharma, Frank Stephan:
  On the Classification of Computable Languages. 225-236
  
• Gabriele Kern-Isberner:
  A Conditional-Logical Approach to Minimum Cross-Entropy. 237-248
  
• Erich Grädel, Martin Otto, Eric Rosen:
  Undecidability Results on Two-Variable Logics. 249-260
  

Invited Paper

• Stephane Gaubert, Max Plus:
  Methods and Applications of (MAX, +) Linear Algebra. 261-282
  

Automata Theory II

• Oliver Matz:
  Regular Expressions and Context-Free Grammars for Picture Languages. 283-294
  
• Jonathan Goldstine, Hing Leung, Detlef Wotschke:
  Measuring Nondeterminism in Pushdown Automata. 295-306
  

Structural Complexity II

• Arfst Nickelsen:
  On Polynomially D-Verbose Sets. 307-318
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  A Downward Translation in the Polynomial Hierarchy. 319-328
  

Complexity Theory I

• Klaus Reinhardt:
  Strict Sequential P-completeness. 329-338
  
• Klaus-Jörn Lange:
  An Unambiguous Class Possessing a Complete Set. 339-350
  

Parallel and Distributed Systems I

• Michele Flammini:
  Deadlock-Free Interval Routing Schemes. 351-362
  
• Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc:
  Power Consumption in Packet Radio Networks (Extended Abstract). 363-374
  

Complexity Theory II

• Christoph Karg, Johannes Köbler, Rainer Schuler:
  The Complexity of Generating Test Instances. 375-386
  
• Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
  Efficient Construction of Hitting Sets for Systems of Linear Functions. 387-398
  
• Ingrid Biehl, Bernd Meyer:
  Protocols for Collusion-Secure Asymmetric Fingerprinting (Extended Abstract). 399-412
  

Parallel and Distributed Systems II

• Ugo Montanari, Marco Pistore:
  Minimal Transition Systems for History-Preserving Bisimulation. 413-425
  
• Gianpiero Cattaneo, Enrico Formenti, Giovanni Manzini, Luciano Margara:
  On Ergodic Linear Cellular Automata over Z_m. 427-438
  
• Jérôme Olivier Durand-Lose:
  Intrinsic Universality of a 1-Dimensional Reversible Cellular Automaton. 439-450
  

Complexity Theory III

• Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey Shallit:
  The Computational Complexity of Some Problems of Linear Algebra (Extended Abstract). 451-462
  
• Thomas Schwentick:
  Algebraic and Logical Characterizations of Deterministic Linear Time Classes. 463-474
  

Parallel Algorithms

• Eric Ruppert:
  Finding the k Shortest Paths in Parallel. 475-486
  
• Elias Dahlhaus:
  Sequential and Parallel Algorithms on Compactly Represented Chordal and Strongly Chordal Graphs. 487-498
  

Algorithms III

• Erich Prisner:
  Distance Approximating Spanning Trees. 499-510
  
• Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Stefan Tschöke:
  A Better Upper Bound on the Bisection Width of de Bruijn Networks (Extended Abstract). 511-522
  

Structural Complexity III

• Joan Feigenbaum, Martin Strauss:
  An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract). 523-534
  
• Josef M. Breutzmann, Jack H. Lutz:
  Equivalence of Measures of Complexity Classes. 535-545
  

Algorithms IV

• Vincenzo Auletta, Domenico Parente:
  Better Algorithms for Minimum Weight Vertex-Connectivity Problems. 547-558
  
• Hans Jürgen Prömel, Angelika Steger:
  RNC-Approximation Algorithms for the Steiner Problem. 559-570
  

Automata Theory III

• Jochen Meßner:
  Pattern Matching in Trace Monoids (Extended Abstract). 571-582
  
• Volker Diekert, Paul Gastin, Antoine Petit:
  Removing epsilon-Transitions in Timed Automata. 583-594
  

Invited Paper

• Oded Goldreich:
  Probabilistic Proof Systems - A Survey. 595-611