STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science Lübeck, Germany February 27–March 1, 1997 Proceedings

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