PROGRAM SESSIONS


STACS '97

14th Symposium on Theoretical Aspects of Computer Science

Hansestadt Lübeck, Germany

February 27 - March 1, 1997


All technical sessions will take place at

Mövenpick Hotel, Beim Holstentor, D-23554 Lübeck,
Lecture rooms: "Prismensaal" and "Saal Münster/Braunschweig"

Program sessions in detail:


Invited Talk: Thursday, February 27, 1997, 9:05 - 10:05

Unifying Models
Bernhard Steffen (Passau, Germany)


Session 1: Thursday, February 27, 1997, 10:15 - 11:15

Session 1A: Algorithms I (Chair: Afonso Ferreira)

10:15 - 10:45 Predecessor Queries in Dynamic Integer Sets
Gerth Stolting Brodal (Aarhus, Denmark)
10:45 - 11:15 Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs
Paolo Giulio Franciosa (Roma, Italy), Daniele Frigioni (L'Aquila, Italy), Roberto Giaccio (Roma, Italy)

Session 1B: Automata Theory I (Chair: Jürgen Dassow)

10:15 - 10:45 Greibach Normal Form Transformation, Revisited
Robert Koch, Norbert Blum (Bonn, Germany)
10:45 - 11:15 Translating Regular Expressions into Small e(psilon)-Free Nondeterministic Finite Automata
Juraj Hromkovic, Sebastian Seibert, Thomas Wilke (Kiel, Germany)


Session 2: Thursday, February 27, 1997, 11:45 - 12:45

Session 2A: Algorithms II (Chair: Dorothea Wagner)

11:45 - 12:15 Memory Management for Union-Find Algorithms
Christophe Fiorio, Jens Gustedt (Berlin, Germany)
12:15 - 12:45 Fast Online Multiplication of Real Numbers
Matthias Schröder (Hagen, Germany)

Session 2B: Structural Complexity I (Chair: Miklos Santha)

11:45 - 12:15 The Operators min and max on the Polynomial Hierarchy
Harald Hempel, Gerd Wechsung (Jena, Germany)
12:15 - 12:45 Resource-Bounded Kolmogorov Complexity Revisited
Harry Buhrman (Amsterdam, The Netherlands), Lance Fortnow (Chicago, USA)


Session 3: Thursday, February 27, 1997, 14:30 - 16:00

Session 3A: Probabilism (Chair: Miklos Santha)

14:30 - 15:00 Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations
Pavol Duris (Bratislava, Slovakia), Juraj Hromkovic (Kiel, Germany), José D.P. Rolim (Geneva, Switzerland), Georg Schnitger (Frankfurt/Main, Germany)
15:00 - 15:30 Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes
Maciej Liskiewicz (Berkeley, USA)
15:30 - 16:00 MODp-tests, Almost Independence and Small Probability Spaces
Claudia Bertram-Kretzberg, Hanno Lefmann (Dortmund, Germany)

Session 3B: Specification and Verification (Chair: Christian Lengauer)

14:30 - 15:00 Hybrid Diagrams: A Deductive-Algorithmic Approach to Hybrid System Verification
Luca de Alfaro, Arjun Kapur, Zohar Manna (Stanford, USA)
15:00 - 15:30 Temporal Logics for the Specification of Performance and Reliability
Luca de Alfaro (Stanford, USA)
15:30 - 16:00 Efficient Scaling-Invariant Checking of Timed Bisimulation
Carsten Weise, Dirk Lenzkes (Aachen, Germany)


Session 4: Thursday, February 27, 1997, 16:30 - 18:00

Session 4A: Boolean Functions (Chair: Dorothea Wagner)

16:30 - 17:00 Gossiping and Broadcasting versus Computing Functions in Networks
Martin Dietzfelbinger (Dortmund, Germany)
17:00 - 17:30 On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams
Stephan Waack (Göttingen, Germany)
17:30 - 18:00 A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams
Christoph Meinel, Anna Slobodová (Trier, Germany)

Session 4B: Logic and Learning (Chair: Martin Kummer)

16:30 - 17:00 On the Classification of Computable Languages
John Case (Newark, USA), Efim Kinber (Fairfield, USA), Arun Sharma (Sydney, Australia), Frank Stephan (Heidelberg, Germany)
17:00 - 17:30 A Conditional-Logical Approach to Minimum Cross-Entropy
Gabriele Kern-Isberner (Hagen, Germany)
17:30 - 18:00 Undecidability Results on Two-Variable Logics
Erich Grädel, Martin Otto (Aachen, Germany), Eric Rosen (Haifa, Israel)


Invited Talk: Friday, February 28, 1997, 9:00 - 10:00

Methods and Applications of (MAX,+) Linear Algebra
Stephane Gaubert (Rocquencourt, France)


Session 5: Friday, February 28, 1997, 10:15 - 11:15

Session 5A: Automata Theory II (Chair: Jürgen Dassow)

10:15 - 10:45 Regular Expressions and Context-Free Grammars for Picture Languages
Oliver Matz (Kiel, Germany)
10:45 - 11:15 Measuring Nondeterminism in Pushdown Automata
Jonathan Goldstine (University Park, PA, USA), Hing Leung (Las Cruces, USA), Detlef Wotschke (Frankfurt/Main, Germany)

Session 5B: Structural Complexity II (Chair: Martin Kummer)

10:15 - 10:45 On Polynomially D-Verbose Sets
Arfst Nickelsen (Berlin, Germany)
10:45 - 11:15 A Downward Translation in the Polynomial Hierarchy
Edith Hemaspaandra (Syracuse, USA), Lane A. Hemaspaandra (Rochester, USA), Harald Hempel (Jena, Germany)


Session 6: Friday, February 28, 1997, 11:45 - 12:45

Session 6A: Complexity Theory I (Chair: Dorothea Wagner)

11:45 - 12:15 Strict Sequential P-completeness
Klaus Reinhardt (Tübingen, Germany)
12:15 - 12:45 An Unambiguous Class Possessing a Complete Set
Klaus-Jörn Lange (Tübingen, Germany)

Session 6B: Parallel and Distributed Systems I (Chair: Afonso Ferreira)

11:45 - 12:15 Deadlock-Free Interval Routing Schemes
Michele Flammini (L'Aquila, Italy)
12:15 - 12:45 Power Consumption in Packet Radio Networks
Lefteris M. Kirousis (Patras, Greece) , Evangelos Kranakis, Danny Krizanc (Ottawa, Canada), Andrzej Pelc (Québec, Canada)


Session 7: Friday, February 28, 1997, 14:30 - 16:00

Session 7A: Complexity Theory II (Chair: Jean-Paul Allouche)

14:30 - 15:00 The Complexity of Generating Test Instances
Christoph Karg, Johannes Köbler, Rainer Schuler (Ulm, Germany)
15:00 - 15:30 Efficient Construction of Hitting Sets for Systems of Linear Functions
Alexander E. Andreev (Moscow, Russia), Andrea E.F. Clementi (Rome, Italy), José D.P. Rolim (Geneva, Switzerland)
15:30 - 16:00 Protocols for Collusion-Secure Asymmetric Fingerprinting
Ingrid Biehl, Bernd Meyer (Saarbrücken, Germany)

Session 7B: Parallel and Distributed Systems II (Chair: Christian Lengauer)

14:30 - 15:00 Minimal Transition Systems for History-Preserving Bisimulation
Ugo Montanari, Marco Pistore (Pisa, Italy)
15:00 - 15:30 On Ergodic Linear Cellular Automata over Zm
Gianpiero Cattaneo, Enrico Formenti (Milano, Italy), Giovanni Manzini (Torino, Italy), Luciano Margara (Bologna, Italy)
15:30 - 16:00 Intrinsic Universality of a 1-Dimensional Reversible Cellular Automaton
Jérôme Olivier Durand-Lose (Bordeaux, France)


Session 8: Friday, February 28, 1997, 16:30 - 17:30

Session 8A: Complexity Theory III (Chair: Miklos Santha)

16:30 - 17:00 The Computational Complexity of Some Problems of Linear Algebra
Jonathan F. Buss (Waterloo, Canada), Gudmund S. Frandsen (Aarhus, Denmark), Jeffrey O. Shallit (Waterloo, Canada)
17:00 - 17:30 Algebraic and Logical Characterizations of Deterministic Linear Time Classes
Thomas Schwentick (Mainz, Germany)

Session 8B: Parallel Algorithms (Chair: Afonso Ferreira)

16:30 - 17:00 Finding the k Shortest Paths in Parallel
Eric Ruppert (Toronto, Canada)
17:00 - 17:30 Sequential and Parallel Algorithms on Compactly Represented Chordal and Strongly Chordal Graphs
Elias Dahlhaus (Bonn, Germany)


Session 9: Saturday, March 1, 1997, 9:15 - 10:15

Session 9A: Algorithms III (Chair: Christian Lengauer)

9:15 - 9:45 Distance Approximating Spanning Trees
Erich Prisner (Clemson, USA)
9:45 - 10:15 A Better Upper Bound on the Bisection Width of de Bruijn Networks
Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Stefan Tschöke (Paderborn, Germany)

Session 9B: Structural Complexity III (Chair: Martin Kummer)

9:15 - 9:45 An Information-Theoretic Treatment of Random-Self-Reducibility
Joan Feigenbaum (Murray Hill, USA), Martin Strauss (Ames, USA)
9:45 - 10:15 Equivalence of Measures of Complexity Classes
Josef M. Breutzmann (Waverly, USA), Jack H. Lutz (Ames, USA)


Session 10: Saturday, March 1, 1997, 10:45 - 11:45

Session 10A: Algorithms IV (Chair: Jean-Paul Allouche)

10:45 - 11:15 Better Algorithms for Minimum Weight Vertex-Connectivity Problems
Vincenzo Auletta, Mimmo Parente (Baronissi, Italy)
11:15 - 11:45 RNC-Approximation Algorithms for the Steiner Problem
Hans Jürgen Prömel (Berlin, Germany), Angelika Steger (München, Germany)

Session 10B: Automata Theory III (Chair: Jürgen Dassow)

10:45 - 11:15 Pattern Matching in Trace Monoids
Jochen Messner (Ulm, Germany)
11:15 - 11:45 Removing e(psilon) Transitions in Timed Automata
Volker Diekert (Stuttgart, Germany), Paul Gastin (Paris, France), Antoine Petit (Cachan, France)


Invited Talk: Saturday, March 1, 1997, 11:50 - 12:50

Probabilistic Proof Systems - A Survey
Oded Goldreich (Rehovot, Israel)


Back to the STACS'97 front page.


Last modified: February 19, 1997 by K. Genther.