STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997 Proceedings (Lecture Notes in Computer Science, 1200)

This Book Constitutes The Refereed Proceedings Of The 14th Annual Symposium On Theoretical Aspects Of Computer Science, Stacs 97, Held In Lübeck, 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 Models / B. Steffen -- Predecessor Queries In Dynamic Integer Sets / G.s. Brodal -- Semi-dynamic Shortest Paths And Breadth-first Search In Digraphs / P.g. Franciosa, D. Frigioni And R. Giaccio -- Greibach Normal Form Transformation, Revisited / R. Koch And N. Blum -- Translating Regular Expressions Into Small [epsilon]-free Nondeterministic Finite Automata / J. Hromkovic, S. Seibert And T. Wilke -- Memory Management For Union-find Algorithms / C. Fiorio And J. Gustedt -- Fast Online Multiplication Of Real Numbers / M. Schroder -- The Operators Min And Max On The Polynomial Hierarchy / H. Hempel And G. Wechsung -- Resource-bounded Kolmogorov Complexity Revisited / H. Buhrman And L. Fortnow -- Las Vegas Versus Determinism For One-way Communication Complexity, Finite Automata, And Polynomial-time Computations / P. Duris, J. Hromkovic And J.d.p. Rolim [and Others]. Rüdiger Reischuk, Michel Morvan (eds.). Includes Bibliographical References And Index. Unifying models....Pages 1-20 Predecessor queries in dynamic integer sets....Pages 21-32 Semi-dynamic shortest paths and breadth-first search in digraphs....Pages 33-46 Greibach normal form transformation, revisited....Pages 47-54 Translating regular expressions into small ε-free nondeterministic finite automata....Pages 55-66 Memory management for Union-Find algorithms....Pages 67-79 Fast online multiplication of real numbers....Pages 81-92 The operators min and max on the polynomial hierarchy....Pages 93-104 Resource-bounded kolmogorov complexity revisited....Pages 105-116 Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations....Pages 117-128 Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes....Pages 129-140 MOD p -tests, almost independence and small probability spaces....Pages 141-152 Hybrid diagrams: A deductive-algorithmic approach to hybrid system verification....Pages 153-164 Temporal logics for the specification of performance and reliability....Pages 165-176 Efficient scaling-invariant checking of timed bisimulation....Pages 177-188 Gossiping and broadcasting versus computing functions in networks....Pages 189-200 On the descriptive and algorithmic power of parity ordered binary decision diagrams....Pages 201-212 A reducibility concept for problems defined in terms of ordered binary decision diagrams....Pages 213-224 On the classification of computable languages....Pages 225-236 A conditional-logical approach to minimum cross-entropy....Pages 237-248 Undecidability results on two-variable logics....Pages 249-260 Methods and applications of (max,+) linear algebra....Pages 261-282 Regular expressions and context-free grammars for picture languages....Pages 283-294 Measuring nondeterminism in pushdown automata....Pages 295-306 On polynomially D verbose sets....Pages 307-318 A downward translation in the polynomial hierarchy....Pages 319-328 Strict sequential P-completeness....Pages 329-338 An unambiguous class possessing a complete set....Pages 339-350 Deadlock-free interval routing schemes....Pages 351-362 Power consumption in packet radio networks....Pages 363-374 The complexity of generating test instances....Pages 375-386 Efficient constructions of Hitting Sets for systems of linear functions....Pages 387-398 Protocols for collusion-secure asymmetric fingerprinting....Pages 399-412 Minimal transition systems for history-preserving bisimulation....Pages 413-425 On ergodic linear cellular automata over Z m ....Pages 427-438 Intrinsic universality of a 1-dimensional reversible Cellular Automaton....Pages 439-450 The computational complexity of some problems of linear algebra....Pages 451-462 Algebraic and logical characterizations of deterministic linear time classes....Pages 463-474 Finding the k shortest paths in parallel....Pages 475-486 Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs....Pages 487-498 Distance approximating spanning trees....Pages 499-510 A better upper bound on the bisection width of de Bruijn networks....Pages 511-522 An information-theoretic treatment of random-self-reducibility....Pages 523-534 Equivalence of measures of complexity classes....Pages 535-545 Better algorithms for minimum weight vertex-connectivity problems....Pages 547-558 RNC-approximation algorithms for the steiner problem....Pages 559-570 Pattern matching in trace monoids....Pages 571-582 Removing ε-transitions in timed automata....Pages 583-594 Probabilistic proof systems — A survey....Pages 595-611 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; The exploding size and conceptual complexity of programs or, even more strikingly, distributed systems have led to the development of numerous descriptions methods typically aiming at rigorous structured and/or focussed system design.