STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997 ProceedingsThis 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. |
Contents
I | 1 |
II | 21 |
III | 33 |
IV | 47 |
VI | 55 |
VII | 65 |
VIII | 79 |
IX | 91 |
XXXIII | 327 |
XXXIV | 337 |
XXXV | 349 |
XXXVI | 361 |
XXXVIII | 373 |
XXXIX | 385 |
XL | 397 |
XLI | 411 |
Common terms and phrases
1200 Springer-Verlag Berlin algebra algorithm assume automata automaton Berlin Heidelberg 1997 binary bisimulation Boolean functions chordal graph codewords commitment scheme complexity classes Computer Science configuration consider construction contains Corollary corresponding defined Definition deletions denote deterministic diagram distribution elements equivalent exists finite formula given graph G Hitting Set hypergraph infinite input integer interactive proof systems language Lemma linear logic logn lower bound matrix minimum minimum spanning tree Morvan Eds node non-tree edges nondeterministic NP-complete NP-hard O(log OBDD obtained operations optimal output polynomial polynomial hierarchy polynomial-time probabilistic probability Proc processors properties protocol prove queries random recursive reduced regular expression Reischuk represented resp result semiring sequence shortest paths simulation space spanning tree STACS'97 Proceedings step string subset Theorem theory transition transition relation Turing machine Union-Find v₁ variables vertex vertices weight zero-knowledge proofs