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

Ilaria Castellani (auth.), P. Enjalbert, A. Finkel, K. W. Wagner (eds.)3540565035, 9783540565031

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.

---

Table of contents :
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