STACS '97

The following papers have been accepted (order is random):

• Greibach Normal Form Transformation, Revisited
  Robert Koch, Norbert Blum (Bonn, Germany)

• Power Consumption in Packet Radio Networks
  Lefteris M. Kirousis (Patras, Greece) , Evangelos Kranakis, Danny Krizanc (Ottawa, Canada), Andrzej Pelc (Québec, Canada)

• Algebraic and Logical Characterizations of Deterministic Linear Time Classes
  Thomas Schwentick (Mainz, Germany)

• Finding the k Shortest Paths in Parallel
  Eric Ruppert (Toronto, Canada)

• Removing e(psilon) Transitions in Timed Automata
  Volker Diekert (Stuttgart, Germany), Paul Gastin (Paris, France), Antoine Petit (Cachan, France)

• Undecidability Results on Two-Variable Logics
  Erich Grädel, Martin Otto (Aachen, Germany), Eric Rosen (Haifa, Israel)

• The Operators min and max on the Polynomial Hierarchy
  Harald Hempel, Gerd Wechsung (Jena, Germany)

• 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)

• A Downward Translation in the Polynomial Hierarchy
  Edith Hemaspaandra (Syracuse, USA), Lane A. Hemaspaandra (Rochester, USA), Harald Hempel (Jena, Germany)

• On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams
  Stephan Waack (Göttingen, Germany)

• A Conditional-Logical Approach to Minimum Cross-Entropy
  Gabriele Kern-Isberner (Hagen, Germany)

• Fast Online Multiplication of Real Numbers
  Matthias Schröder (Hagen, Germany)

• Hybrid Diagrams: A Deductive-Algorithmic Approach to Hybrid System Verification
  Luca de Alfaro, Arjun Kapur, Zohar Manna (Stanford, USA)

• 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)

• Intrinsic Universality of a One-Dimension Reversible Cellular Automaton
  Jérôme Olivier Durand-Lose (Bordeaux, France)

• Distance Approximating Spanning Trees
  Erich Prisner (Clemson, USA)

• Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs
  Paolo Giulio Franciosa (Roma, Italy), Daniele Frigioni (L'Aquila, Italy), Roberto Giaccio (Roma, Italy)

• The Computational Complexity of Some Problems of Linear Algebra
  Jonathan F. Buss (Waterloo, Canada), Gudmund S. Frandsen (Aarhus, Denmark), Jeffrey O. Shallit (Waterloo, Canada)

• Strict Sequential P-completeness
  Klaus Reinhardt (Tübingen, Germany)

• Sequential and Parallel Algorithms on Compactly Represented Chordal and Strongly Chordal Graphs
  Elias Dahlhaus (Bonn, Germany)

• An Unambiguous Class Possessing a Complete Set
  Klaus-Jörn Lange (Tübingen, Germany)

• Deadlock-Free Interval Routing Schemes
  Michele Flammini (L'Aquila, Italy)

• Memory Management for Union-Find Algorithms
  Christophe Fiorio, Jens Gustedt (Berlin, Germany)

• A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams
  Christoph Meinel, Anna Slobodová (Trier, Germany)

• Regular Expressions and Contextfree Grammars for Picture Languages
  Oliver Matz (Kiel, Germany)

• MOD_p-tests, Almost Independence and Small Probability Spaces
  Claudia Bertram-Kretzberg, Hanno Lefmann (Dortmund, Germany)

• Equivalence of Measures of Complexity Classes
  Josef M. Breutzmann (Waverly, USA), Jack H. Lutz (Ames, USA)

• RNC-Approximation Algorithms for the Steiner Problem
  Hans Jürgen Prömel (Berlin, Germany), Angelika Steger (München, Germany)

• On the Classification of Computable Languages
  John Case (Newark, USA), Efim Kinber (Fairfield, USA), Arun Sharma (Sydney, Australia), Frank Stephan (Heidelberg, Germany)

• Pattern Matching in Trace Monoids
  Jochen Messner (Ulm, Germany)

• The Complexity of Generating Test Instances
  Christoph Karg, Johannes Köbler, Rainer Schuler (Ulm, Germany)

• Resource-Bounded Kolmogorov Complexity Revisited
  Harry Buhrman (Amsterdam, The Netherlands), Lance Fortnow (Chicago, USA)

• Protocols for Collusion-Secure Asymmetric Fingerprinting
  Ingrid Biehl, Bernd Meyer (Saarbrücken, Germany)

• Gossiping and Broadcasting versus Computing Functions in Networks
  Martin Dietzfelbinger (Dortmund, Germany)

• Minimal Transition Systems for History-Preserving Bisimulation
  Ugo Montanari, Marco Pistore (Pisa, Italy)

• Better Algorithms for Minimum Weight Vertex-Connectivity Problems
  Vincenzo Auletta, Mimmo Parente (Baronissi, Italy)

• An Information-Theoretic Treatment of Random-Self-Reducibility
  Joan Feigenbaum (Murray Hill, USA), Martin Strauss (Ames, USA)

• On Ergodic Linear Cellular Automata over Z_m
  Gianpiero Cattaneo, Enrico Formenti (Milano, Italy), Giovanni Manzini (Torino, Italy), Luciano Margara (Bologna, Italy)

• Translating Regular Expressions into Small e(psilon)-Free Nondeterministic Finite Automata
  Juraj Hromkovic, Sebastian Seibert, Thomas Wilke (Kiel, Germany)

• Efficient Scaling-Invariant Checking of Timed Bisimulation
  Carsten Weise, Dirk Lenzkes (Aachen, Germany)

• Predecessor Queries in Dynamic Integer Sets
  Gerth Stolting Brodal (Aarhus, Denmark)

• Temporal Logics for the Specification of Performance and Reliability
  Luca de Alfaro (Stanford, USA)

• Measuring Nondeterminism in Pushdown Automata
  Jonathan Goldstine (University Park, PA, USA), Hing Leung (Las Cruces, USA), Detlef Wotschke (Frankfurt/Main, Germany)

• A Better Upper Bound on the Bisection Width of de Bruijn Networks
  Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Stefan Tschöke (Paderborn, Germany)

• On Polynomially D-verbose Sets
  Arfst Nickelsen (Berlin, Germany)

• Interactive Proof Systems with Public Coins: Lower Space Bounds and Hierarchies of Complexity Classes
  Maciej Liskiewicz (Berkeley, USA)

Back to the STACS'97 front page.

Last modified: November 28, 1996 by K. Genther.