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

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 PNP = 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 chit-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

Volker Heun , 1994-10-25