+612 9045 4394
Stacs 97 : 14th Annual Symposium on Theoretical Aspects of Computer Science, Lubeck, Germany, February 27 - March 1, 1997 Proceedings - Rudiger Reischuk

Stacs 97

14th Annual Symposium on Theoretical Aspects of Computer Science, Lubeck, Germany, February 27 - March 1, 1997 Proceedings

By: Rudiger Reischuk (Editor), Michel Morvan (Editor)


Published: 21st February 1997
Ships: 15 business days
15 business days
or 4 easy payments of $48.19 with Learn more

This book constitutes the refereed proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 97, held in Lubeck, Germany, in February/March 1997.
The 46 revised full papers included were carefully selected from a total of 139 submissions; also included are three invited full papers. The papers presented span the whole scope of theoretical computer science. Among the topics covered are, in particular, algorithms and data structures, computational complexity, automata and formal languages, structural complexity, parallel and distributed systems, parallel algorithms, semantics, specification and verification, logic, computational geometry, cryptography, learning and inductive inference.

Unifying Modelsp. 1
Predecessor Queries in Dynamic Integer Setsp. 21
Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphsp. 33
Greibach Normal Form Transformation, Revisitedp. 47
Translating Regular Expressions into Small [epsilon]-Free Nondeterministic Finite Automatap. 55
Memory Management for Union-Find Algorithmsp. 67
Fast Online Multiplication of Real Numbersp. 81
The Operators min and max on the Polynomial Hierarchyp. 93
Resource-Bounded Kolmogorov Complexity Revisitedp. 105
Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computationsp. 117
Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classesp. 129
MOD[subscript p]-tests, Almost Independence and Small Probability Spacesp. 141
Hybrid Diagrams: A Deductive-Algorithmic Approach to Hybrid System Verificationp. 153
Temporal Logics for the Specification of Performance and Reliabilityp. 165
Efficient Scaling-Invariant Checking of Timed Bisimulationp. 177
Gossiping and Broadcasting versus Computing Functions in Networksp. 189
On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagramsp. 201
A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagramsp. 213
On the Classification of Computable Languagesp. 225
A Conditional-Logical Approach to Minimum Cross-Entropyp. 237
Undecidability Results on Two-Variable Logicsp. 249
Methods and Applications of (max,+) Linear Algebrap. 261
Regular Expressions and Context-Free Grammars for Picture Languagesp. 283
Measuring Nondeterminism in Pushdown Automatap. 295
On Polynomially D-Verbose Setsp. 307
A Downward Translation in the Polynomial Hierarchyp. 319
Strict Sequential P-completenessp. 329
An Unambiguous Class Possessing a Complete Setp. 339
Deadlock-Free Interval Routing Schemesp. 351
Power Consumption in Packet Radio Networksp. 363
The Complexity of Generating Test Instancesp. 375
Efficient Construction of Hitting Sets for Systems of Linear Functionsp. 387
Protocols for Collusion-Secure Asymmetric Fingerprintingp. 399
Minimal Transition Systems for History-Preserving Bisimulationp. 413
On Ergodic Linear Cellular Automata over Z[subscript m]p. 427
Intrinsic Universality of a 1-Dimensional Reversible Cellular Automatonp. 439
The Computational Complexity of Some Problems of Linear Algebrap. 451
Algebraic and Logical Characterizations of Deterministic Linear Time Classesp. 463
Finding the k Shortest Paths in Parallelp. 475
Sequential and Parallel Algorithms on Compactly Represented Chordal and Strongly Chordal Graphsp. 487
Distance Approximating Spanning Treesp. 499
A Better Upper Bound on the Bisection Width of de Bruijn Networksp. 511
An Information-Theoretic Treatment of Random-Self-Reducibilityp. 523
Equivalence of Measures of Complexity Classesp. 535
Better Algorithms for Minimum Weight Vertex-Connectivity Problemsp. 547
RNC-Approximation Algorithms for the Steiner Problemp. 559
Pattern Matching in Trace Monoidsp. 571
Removing [epsilon]-Transitions in Timed Automatap. 583
Probabilistic Proof Systems - A Surveyp. 595
List of Authorsp. 613
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540626169
ISBN-10: 3540626166
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 621
Published: 21st February 1997
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.25
Weight (kg): 0.88