10. STACS 1993: Würzburg, Germany

Invited Talk

• Ilaria Castellani:
  Causal and Distributed Semantics for Concurrent Processes (Abstract). 1
  

Computational Complexity

• Klaus W. Wagner:
  The Alternation Hierarchy for Sublogarithmic Space: An Exciting Race to STACS'93 (Editorial Note). 2-4
• Burchard von Braunmühl:
  Alternation for Two-way Machines with Sublogarithmic Space. 5-15
  
• Maciej Liskiewicz, Rüdiger Reischuk:
  Separating the Lower Levels of the Sublogarithmic Space Hierarchy. 16-27
  
• Johannes Köbler:
  Locating P/poly Optimally in the Extended Low Hierarchy. 28-37
  
• Jack H. Lutz, Elvira Mayordomo:
  Measure, Stochasticity, and the Density of Hard Languages. 38-47
  

Logic in Computer Science

• Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier:
  Halting Problem of One Binary Horn Clause is Undecidable. 48-57
  
• Zhou Chaochen, Michael R. Hansen, Peter Sestoft:
  Decidability and Undecidability Results for Duration Calculus. 58-68
  
• Philippe de Groote:
  Defining Lambda-Typed Lambda-Calculi by Axiomatizing the Typing Relation. 712-723
  
• Thomas Eiter, Georg Gottlob:
  The Complexity of Logic-Based Abduction. 70-79
  

Efficient Algorithms

• Ton Kloks, Dieter Kratsch:
  Treewidth of Bipartite Graphs. 80-89
  
• Ulrich Huckenbeck:
  On Paths in Networks with Valves. 90-99
  
• Sivaprakasam Sunder, Xin He:
  Scheduling Interval Ordered Tasks in Parallel. 100-109
  
• Andrea Pietracaprina, Franco P. Preparata:
  On O(sqrt(n))-Worst-Case-Time Solution to the Granularity Problem. 110-119
  

Parallel and Distributed Computation

• Jörg Desel, Wolfgang Reisig:
  The Synthesis Problem of Petri Nets. 120-129
  
• Eike Best, Raymond R. Devillers, Javier Esparza:
  General Refinement and Recursion Operators for the Petri Box Calculus. 130-140
  
• Maria Paola Bonacina, Jieh Hsiang:
  On Fairness in Distributed Automated Deduction. 141-152
  
• Ernst W. Mayr, Ralph Werchner:
  Divide-and-Conquer Algorithms on the Hypercube. 153-162
  

Computational Complexity

• Eric Allender, José L. Balcázar, Neil Immerman:
  A First-Order Isomorphism Theorem. 163-174
  
• Harry Buhrman, Albrecht Hoene, Leen Torenvliet:
  Splittings, Robustness and Structure of Complete Sets. 175-184
  
• Lane A. Hemachandra, Sudhir K. Jha:
  Defying Upward and Downward Separation. 185-195
  
• Albrecht Hoene, Arfst Nickelsen:
  Counting, Selecting, adn Sorting by Query-Bounded Machines. 196-205
  

Language Theory

• Matthias Jantzen, Holger Petersen:
  Cancellation on Context-Free Languages: Enrichment by Reduction. 206-215
  
• Julien Cassaigne:
  Counting Overlap-Free Binary Words. 216-225
  
• Philippe Narbel:
  The Limit Set of Recognizable Substitution Systems. 226-236
  
• Daniel Krob, Pierre Lalonde:
  Partially Commutative Lyndon Words. 237-246
  

Invited Talk

• Burkhard Monien, Rainer Feldmann, Ralf Klasing, Reinhard Lüling:
  Parallel Architectures: Design and Efficient Use. 247-269
  

Computational Geometry

• Michael Formann:
  Weighted Closest Pairs. 270-281
  
• Sven Schuierer:
  Rectilinear Path Queries in a Simple Rectilinear Polygon. 282-293
  
• Artur Czumaj:
  Parallel Algorithm for the Matrix Chain Product and the Optimal Triangulation Problems (Extended Abstract). 294-305
  
• Anders Dessmark, Andrzej Lingas, Anil Maheshwari:
  Multi-List Ranking: Complexity and Applications. 306-316
  
• Ludek Kucera, Kurt Mehlhorn, B. Preis, E. Schwarzenecker:
  Exact Algorithms for a Geometric Packing Problem (Extended Abstract). 317-322
  

Automata Theory

• Oded Maler:
  A Decomposition Theorem for Probabilistic Transition Systems. 323-332
  
• Rosa Montalbano:
  Local Automata and Completion. 333-342
  
• Karel Culik II, Simant Dube:
  Efficient Compression of Wavelet Coefficients for Smooth and Fractal-like Data. 343-353
  
• Oscar H. Ibarra, Tao Jiang, Nicholas Q. Trân, Hui Wang:
  On the Equivalence of Two-way Pushdown Automata and Counter Machines over Bounded Languages. 354-364
  
• Michel Cosnard, Max H. Garzon, Pascal Koiran:
  Computability Properties of Low-dimensional Dynamical Systems. 365-373
  

Computational Complexity

• Karl R. Abrahamson, Rodney G. Downey, Michael R. Fellows:
  Fixed-Parameter Intractability II (Extended Abstract). 374-385
  
• Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski:
  Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. 386-397
  
• Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman:
  On Using Oracles That Compute Values. 398-407
  
• Romain Gengler:
  Multicounter Automata with Sublogarithmic Reversal Bounds. 408-417
  

Semantics and Logic of Programming Languages

• Andrew C. Uselton:
  Structured Operational Semantics for Concurrency and Hierarchy. 418-427
  
• Hardi Hungar:
  The Complexity of Verifying Functional Programs. 428-439
  
• P. J. A. Lentfert, S. Doaitse Swierstra:
  Towards the Formal Design of Self-Stabilizing Distributed Algorithms. 440-451
  
• Wojciech Penczek:
  Axiomatizations of Temporal Logics on Trace Systems. 452-462
  

Computational Complexity

• Katharina Lürwer-Brüggemeier, Friedhelm Meyer auf der Heide:
  Capabilities and Complexity of Computations with Integer Division. 463-472
  
• Rolf Niedermeier, Peter Rossmanith:
  Extended Locally Definable Acceptance Types (Extended Abstract). 473-483
  
• Stephen A. Fenner, Lance Fortnow, Lide Li:
  Gap-Definability as a Closure Property. 484-493
  

Automata Theory and Logic

• Christian Choffrut, Leucio Guerra:
  On the Logical Definability of Some Rational Trace Languages. 494-504
  
• Rémi Gilleron, Sophie Tison, Marc Tommasi:
  Solving Systems of Set Constraints using Tree Automata. 505-514
  
• Denis Lugiez, J. L. Moysset:
  Complement Problems and Tree Automata in AC-like Theories (Extended Abstract). 515-524
  

Invited Talk

• László Babai:
  Transparent (Holographic) Proofs. 525-534
  

Circuit Complexity

• Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui:
  Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. 535-544
  
• Alexis Maciel, Denis Thérien:
  Threshold Circuits for Iterated Multiplication: Using AC0 for Free. 545-565
  
• Sorin Istrail, Dejan Zivkovic:
  A Non-Probabilistic Switching Lemma for the Sipser Function. 566-575
  
• Jordan Gergov, Christoph Meinel:
  Frontiers of Feasible and Probabilistic Feasible Boolean Manipulation with Branching Programs. 576-585
  

Omega-Automata

• Oded Maler, Ludwig Staiger:
  On Syntactic Congruences for Omega-Languages. 586-594
  
• Stefano Varricchio:
  Polynomial Time Algorithm for the Equivalence of two Morphisms on Omega-Regular Languages. 595-606
  
• Thomas Wilke:
  Locally Threshold Testable Languages of Infinite Words. 607-616
  
• Volker Diekert, Anca Muscholl:
  Deterministic Asynchronous Automata for Infinite Traces. 617-628
  
• Ludwig Staiger:
  Recursive Automata on Infinite Words. 629-639
  

Non-Classical Complexity

• Sairam Sairam, Jeffrey Scott Vitter, Roberto Tamassia:
  A Complexity Theoretic Approach to Incremental Computation. 640-649
  
• Rüdiger Reischuk, Christian Schindelhauer:
  Precise Average Case Complexity. 650-661
  
• Peter Bro Miltersen:
  The Bit Probe Complexity Measure Revisited. 662-671
  

Learning Theory, Cryptography

• Ganesh Baliga, John Case, Sanjay Jain:
  Language Learning With Some Negative Information. 672-681
  
• Steffen Lange, Thomas Zeugmann:
  Language Learning with a Bounded Number of Mind Changes. 682-691
  
• Carlo Blundo, Alfredo De Santis, Ugo Vaccaro:
  Efficient Sharing of Many Secrets. 692-703
  

Systems

• Rainer Drexler, Wolfgang Reif, Gerhard Schellhorn, Kurt Stenzel, Werner Stephan, Andreas Wolpers:
  The KIV System: A Tool for Formal Program Development. 704-705
  
• Franz Höfting, Egon Wanke, Aurel Balmosan, Curd Bergmann:
  1st Grade - A System for Implementation, Testing and Animation of Graph Algorithms. 706-707
  
• Thomas Käufl:
  The Program Verifier Tatzelwurm. 708-709
  
• Stefan Näher:
  LEDA: A Library of Efficient Data Types and Algorithms. 710-711