This volume contains the proceedings of the tenth annual Symposium on Theoretical Aspects of Computer Science (STACS '93), held in W}rzburg, February 25-27, 1993. The STACS symposia are held alternately in Germany and France, and organized jointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft f}r Informatik (GI) and theSpecial Interest Group for Applied Mathematics of the Association Francaise des Sciences et Technologies de l'Information et des Syst mes (afcet). The volume includes the three invited talks which opened the three days of the symposium: qCausal and distributed semantics for concurrent processesq (I. Castellani), qParallel architectures: design and efficient useq (B. Monien et al.), and qTransparent proofsq (L. Babai). The selection of contributed papers is organized into parts on: computational complexity, logic in computer science, efficient algorithms, parallel and distributed computation, language theory, computational geometry, automata theory, semantics and logic of programming languages, automata theory and logic, circuit complexity, omega-automata, non-classical complexity, learning theory and cryptography, and systems.We also show that in the case of NP-complcle sets the lower bounds for counting and selecting hold unless P=NP. Finally, we ... In [Kre88] optimization problems such as Clique and Travelling Salesperson were classified. Query-boundedanbsp;...
|Author||:||Patrice Enjalbert, Alain Finkel, Klaus W. Wagner|
|Publisher||:||Springer Science & Business Media - 1993-02-19|