Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

STACS '95
12th Symposium on
Theoretical Aspects of Computer Science
March 2-4, 1995, München

List of accepted papers

G. Louchard

Finding the Maximum with Linear Error Probabilities: a sequential analysis approach

Peter Damaschke

Line segmentation of digital curves in parallel

Christiane Bercoff

A Family of Tag Systems for Paperfolding Sequences

Martin Strauss

Normal Numbers and Sources for BPP

Véronique Bruyère, Clelia De Felice

Coding and Strong Coding in Trace Monoids

Marco Cadoli, Francesco M. Donini, Marco Schaerf

On Compact Representations of Propositional Circumscription

Lászlóo Babai, Peter Kimmel, Satyanarayana V. Lokam

Simultaneous Messages vs. Communication

Harry Buhrman, Montserrat Hermo

On the Sparse Set Conjecture for Sets with Low Density

Lance Fortnow, Martin Kummer

Resource-Bound Instance Complexity

Danièle Gardy, Guy Louchard

Dynamic analysis of the sizes of relations

Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

On-line and Dynamic Algorithms for Shortest Path Problems

Sylvain Petitjean

The Number of Views of Piecewise-Smooth Algebraic Objects

S.E. Nikoletsas, P.G. Spirakis

Expander properties in random regular graphs with edge faults

Angelo Monti, Adriano Peron

Systolic Tree omega-Languages

Dora Giammarresi, Rosa Montalbano

Deterministic Generalized Automata

Yenjo Han, Lane A. Hemaspaandra

Pseudorandom Generators and the Frequency of Simplicity

Ioan I. Macarie

On the structure of log-space probabilistic complexity classes

Friedhelm Meyer auf der Heide, Berthold Vöcking

A Packet Routing Protocol for Arbitrary Networks

Frederic Green

Lower Bounds for depth-Three Circuits With Equals and Mod-Gates

Stephen Fenner, Lance Fortnow

Beyond P^NP = NEXP

Pavol Duris, José Rolim

Optimal lower bounds on the multiparty communication complexity

J. Hromkovic, K. Lory's, P. Kanarek, R. Klassing, W. Unger, H. Wagener

On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks

Michele Boreale, Davide Sangiorgi

A fully abstract semantics for causality in the pi-calculus

Matthias Krause

On Realizing Iterated Multiplication by Small Depth Threshold Circuits

Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann

Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations

Volker Diekert, Anca Muscholl, Klaus Reinhardt

On Codings of Traces

Emmanuelle Garel

On the separators on an infinite word generated by a morphism

Bruno Durand

A Random NP-complete problem for inversion of 2D Cellular Automata

Isabelle Fagnot

On the subword equivalence problem for infinite words

Anne-Cécile Fabret, Antoine Petit

On the Undecidability of Deadlock Detection in Families of Nets

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer

Malign Distributions for Average Case Circuit Complexity

Ulrich Hertrampf

Classes of Bounded Counting Type and their Inclusion Relations

Michele Flammini, Giorgio Gambosi, Sandro Salomone

Interval Routing Schemes

Gerhard Buntrock, Friedrich Otto

Growing Context-Sensitive Languages and Church-Rosser Languages

Christine Rüb

On the Average Running Time of Odd-Even Merge Sort

Martin Kummer, Marcus Schäfer

Computability of Convex Sets

Torsten Minkwitz

Algorithms Explained by Symmetries

Thomas Hancock, Tao Jiang, Ming Li, John Tromp

Lower Bounds on Learning Decision Lists and Trees

Felipe Bracho, Manfred Droste, Dietrich Kuske

Dependence Orders for Computations of Concurrent Automata

Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter

Two-Dimensional Pattern Matching in Linear Time and Small Space

Jin-Yi Cai, Richard J. Lipton, Luc Longpre, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar

Communication Complexity of Key Agreement on Small Ranges

Danny Raz

On Slender Context-free Languages

David W. Juedes, Jack H. Lutz

Completeness and Weak Completeness Under Polynomial-Size Circuits

Sriram C. Krishnan, Anuj Puri, R.K. Brayton

Structural Complexity of omega-automata

Giovanna D'Agostino, Angelo Montanari, Alberto Policriti

A Set-Theoretic Translation Method for (Poly)modal Logics

Arvind Gupta, Naomi Nishimura

Finding Largest Common Embedeable Subtrees

Damon Kaller, Arvind Gupta, Tom Shermer

The chi_t-Coloring Problem

Piotr Indyk

Optimal simulation of automata by neural nets

Valentin Antimirov

Partial Derivatives of Regular Expressions and Finite Automata Constructions

Th. Ottmann, S. Schuierer, S. Soundaralakshmi

Enumerating Extreme Points in Higher Dimensions

Paul F. Fischer, Franco P. Preparata, John E. Savage

Generalized Scans and Tri-Diagonal Systems

Oded Maler, A. Pnueli, J. Sifakis

On the Synthesis Of Discrete Controllers for Timed Systems

Manfred Kunde, Rolf Niedermeier, Peter Rossmanith, Klaus Reinhardt

Optimal Average Case Sorting on Arrays