STACS 97

Unifying models.- Predecessor queries in dynamic integer sets.- Semi-dynamic shortest paths and breadth-first search in digraphs.- Greibach normal form transformation, revisited.- Translating regular expressions into small ?-free nondeterministic finite automata.- Memory management for Union-Find algorithms.- Fast online multiplication of real numbers.- The operators min and max on the polynomial hierarchy.- Resource-bounded kolmogorov complexity revisited.- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations.- Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes.- MODp-tests, almost independence and small probability spaces.- Hybrid diagrams: A deductive-algorithmic approach to hybrid system verification.- Temporal logics for the specification of performance and reliability.- Efficient scaling-invariant checking of timed bisimulation.- Gossiping and broadcasting versus computing functions in networks.- On the descriptive and algorithmic power of parity ordered binary decision diagrams.- A reducibility concept for problems defined in terms of ordered binary decision diagrams.- On the classification of computable languages.- A conditional-logical approach to minimum cross-entropy.- Undecidability results on two-variable logics.- Methods and applications of (max,+) linear algebra.- Regular expressions and context-free grammars for picture languages.- Measuring nondeterminism in pushdown automata.- On polynomially D verbose sets.- A downward translation in the polynomial hierarchy.- Strict sequential P-completeness.- An unambiguous class possessing a complete set.- Deadlock-free interval routing schemes.- Power consumption in packet radio networks.- The complexity of generating test instances.- Efficient constructions of Hitting Sets for systems of linear functions.- Protocols for collusion-secure asymmetric fingerprinting.- Minimal transition systems for