STACS 93

Causal and distributed semantics for concurrent processes.- Editorial note.- Alternation for two-way machines with sublogarithmic space.- Separating the lower levels of the sublogarithmic space hierarchy.- Locating P/poly optimally in the extended low hierarchy.- Measure, stochasticity, and the density of hard languages.- Halting problem of one binary Horn clause is undecidable.- Decidability and undecidability results for duration calculus.- Defining ?-typed ?-calculi by axiomatizing the typing relation.- The complexity of logic-based abduction.- Treewidth of chordal bipartite graphs.- On paths in networks with valves.- Scheduling interval ordered tasks in parallel.- An O(?n)-worst-case-time solution to the granularity problem.- The synthesis problem of Petri nets.- General refinement and recursion operators for the Petri Box calculus.- On fairness in distributed automated deduction.- Divide-and-conquer algorithms on the hypercube.- A first-order isomorphism theorem.- Splittings, robustness and structure of complete sets.- Defying upward and downward separation.- Counting, selecting, and sorting by query-bounded machines.- Cancellation in context-free languages: Enrichment by reduction.- Counting overlap-free binary words.- The limit set of recognizable substitution systems.- Partially commutative Lyndon words.- Parallel architectures: Design and efficient use.- Weighted closest pairs.- Rectilinear path queries in a simple rectilinear polygon.- Parallel algorithm for the matrix chain product and the optimal triangulation problems (extended abstract).- Multi-list ranking: complexity and applications.- Exact algorithms for a geometric packing problem (extended abstract).- A decomposition theorem for probabilistic transition systems.- Local automata and completion.-Efficient compression of wavelet coefficients for smooth and fractal-like data.- On the equivalence of two-way pushdown automata and counter machines over bounded languages.- Computability properties of low-dimensional dynamical systems.- Fixed-parameter intractability II (extended abstract).- Limits on the power of parallel random access machines with weak forms of write conflict resolution.- On using oracles that compute values.- Multicounter automata with sublogarithmic reversal bounds.- Structured operational semantics for concurrency and hierarchy.- The complexity of verifying functional programs.- Towards the formal design of self-stabilizing distributed algorithms.- Axiomatizations of temporal logics on trace systems.- Capabilities and complexity of computations with integer division.- Extended locally definable acceptance types.- Gap-definability as a closure property.- On the logical definability of some rational trace languages.- Solving systems of set constraints using tree automata.- Complement problems and tree automata in AC-like theories (extended abstract).- Transparent (holographic) proofs.- Computing symmetric functions with AND/OR circuits and a single MAJORITY gate.- Threshold circuits for iterated multiplication: Using AC0 for free.- Circuits with monoidal gates.- A non-probabilistic switching lemma for the Sipser function.- Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs.- On syntactic congruences for ?-languages.- A polynomial time algorithm for the equivalence of two morphisms on ?-regular languages.- Locally threshold testable languages of infinite words.- Deterministic asynchronous automata for infinite traces.- Recursive automata on infinite words.- A complexity theoretic approach toincremental computation.- Precise average case complexity.- The bit probe complexity measure revisited.- Language learning with some negative information.- Language learning with a bounded number of mind changes.- Efficient sharing of many secrets.- The KIV system a tool for formal program development.- 1st Grade - A system for implementation, testing and animation of graph algorithms.- The program verifier Tatzelwurm.- LEDA a library of efficient data types and algorithms.- Defining ?-typed ?-calculi by axiomatizing the typing relation.