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
Session 1: Algorithms I, Automata Theory I
Session 2: Algorithms II, Structural Complexity I
Session 3: Probabilism, Specification and Verification
Session 4: Boolean Functions, Logic and Learning
Invited Talk
Session 5: Automata Theory II, Structural Complexity II
Session 6: Complexity Theory I, Parallel and Distributed Systems I
Session 7: Complexity Theory II, Parallel and Distributed Systems II
Session 8: Complexity Theory III, Parallel Algorithms
Session 9: Algorithms III, Structural Complexity III
Session 10: Algorithms IV, Automata Theory III
Invited Talk

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	MOD_p-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 Z_m 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.