STACS 93: 10th Annual Symposium on Theoretical Ascpects of Computer Science Würzburg, Germany, February 25–27, 1993 Proceedings

"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: "Causal and distributed semantics for concurrent processes" (I. Castellani), "Parallel architectures: design and efficient use" (B. Monien et al.), and "Transparent proofs" (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."--PUBLISHER'S WEBSITE Causal and distributed semantics for concurrent processes....Pages 1-1 Editorial note....Pages 2-4 Alternation for two-way machines with sublogarithmic space....Pages 5-15 Separating the lower levels of the sublogarithmic space hierarchy....Pages 16-27 Locating P/poly optimally in the extended low hierarchy....Pages 28-37 Measure, stochasticity, and the density of hard languages....Pages 38-47 Halting problem of one binary Horn clause is undecidable....Pages 48-57 Decidability and undecidability results for duration calculus....Pages 58-68 Defining λ-typed λ-calculi by axiomatizing the typing relation....Pages 69-69 The complexity of logic-based abduction....Pages 70-79 Treewidth of chordal bipartite graphs....Pages 80-89 On paths in networks with valves....Pages 90-99 Scheduling interval ordered tasks in parallel....Pages 100-109 An O(√n)-worst-case-time solution to the granularity problem....Pages 110-119 The synthesis problem of Petri nets....Pages 120-129 General refinement and recursion operators for the Petri Box calculus....Pages 130-140 On fairness in distributed automated deduction....Pages 141-152 Divide-and-conquer algorithms on the hypercube....Pages 153-162 A first-order isomorphism theorem....Pages 163-174 Splittings, robustness and structure of complete sets....Pages 175-184 Defying upward and downward separation....Pages 185-195 Counting, selecting, and sorting by query-bounded machines....Pages 196-205 Cancellation in context-free languages: Enrichment by reduction....Pages 206-215 Counting overlap-free binary words....Pages 216-225 The limit set of recognizable substitution systems....Pages 226-236 Partially commutative Lyndon words....Pages 237-246 Parallel architectures: Design and efficient use....Pages 247-269 Weighted closest pairs....Pages 270-281 Rectilinear path queries in a simple rectilinear polygon....Pages 282-293 Parallel algorithm for the matrix chain product and the optimal triangulation problems (extended abstract)....Pages 294-305 Multi-list ranking: complexity and applications....Pages 306-316 Exact algorithms for a geometric packing problem (extended abstract)....Pages 317-322 A decomposition theorem for probabilistic transition systems....Pages 323-332 Local automata and completion....Pages 333-342 Efficient compression of wavelet coefficients for smooth and fractal-like data....Pages 343-353 On the equivalence of two-way pushdown automata and counter machines over bounded languages....Pages 354-364 Computability properties of low-dimensional dynamical systems....Pages 365-373 Fixed-parameter intractability II (extended abstract)....Pages 374-385 Limits on the power of parallel random access machines with weak forms of write conflict resolution....Pages 386-397 On using oracles that compute values....Pages 398-407 Multicounter automata with sublogarithmic reversal bounds....Pages 408-417 Structured operational semantics for concurrency and hierarchy....Pages 418-427 The complexity of verifying functional programs....Pages 428-439 Towards the formal design of self-stabilizing distributed algorithms....Pages 440-451 Axiomatizations of temporal logics on trace systems....Pages 452-462 Capabilities and complexity of computations with integer division....Pages 463-472 Extended locally definable acceptance types....Pages 473-483 Gap-definability as a closure property....Pages 484-493 On the logical definability of some rational trace languages....Pages 494-504 Solving systems of set constraints using tree automata....Pages 505-514 Complement problems and tree automata in AC-like theories (extended abstract)....Pages 515-524 Transparent (holographic) proofs....Pages 525-534 Computing symmetric functions with AND/OR circuits and a single MAJORITY gate....Pages 535-544 Threshold circuits for iterated multiplication: Using AC 0 for free....Pages 545-554 Circuits with monoidal gates....Pages 555-565 A non-probabilistic switching lemma for the Sipser function....Pages 566-575 Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs....Pages 576-585 On syntactic congruences for ω —languages....Pages 586-594 A polynomial time algorithm for the equivalence of two morphisms on ω-regular languages....Pages 595-606 Locally threshold testable languages of infinite words....Pages 607-616 Deterministic asynchronous automata for infinite traces....Pages 617-628 Recursive automata on infinite words....Pages 629-639 A complexity theoretic approach to incremental computation....Pages 640-649 Precise average case complexity....Pages 650-661 The bit probe complexity measure revisited....Pages 662-671 Language learning with some negative information....Pages 672-681 Language learning with a bounded number of mind changes....Pages 682-691 Efficient sharing of many secrets....Pages 692-703 The KIV system a tool for formal program development....Pages 704-705 1st Grade — A system for implementation, testing and animation of graph algorithms....Pages 706-707 The program verifier Tatzelwurm ....Pages 708-709 LEDA a library of efficient data types and algorithms....Pages 710-711 Defining λ-typed λ-calculi by axiomatizing the typing relation....Pages 712-723 Annotation This volume contains the proceedings of the tenth annualSymposium on Theoretical Aspects of Computer Science (STACS'93), held in W}rzburg, February 25-27, 1993. The STACS symposia are held alternately in Germany andFrance, and organized jointly by the Special Interest Groupfor Theoretical Computer Science of the Gesellschaft f}rInformatik (GI) and theSpecial Interest Group for AppliedMathematics of the Association Francaise des Sciences etTechnologies de l'Information et des Syst mes (afcet). The volume includes the three invited talks which opened thethree days of the symposium: "Causal and distributedsemantics for concurrent processes" (I. Castellani), "Parallel architectures: design and efficient use" (B. Monien et al.), and "Transparent proofs" (L. Babai). Theselection 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, automatatheory and logic, circuit complexity, omega-automata, non-classical complexity, learning theory and cryptography, and systems This volume contains a selection of contributed papers on such topics as computational complexity, logic in computer science, language theory, computational geometry, automata theory, semantics and the logic of programming languages, non-classical complexity and cryptography.