12. STACS 1995: Munich, Germany

Ernst W. Mayr, Claude Puech (Eds.): STACS 95, 12th Annual Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 2-4, 1995, Proceedings. Lecture Notes in Computer Science 900 Springer 1995, ISBN 3-540-59042-0

Invited Talk

Guy Louchard:
Finding the Maximum with Linear Error Probabilities: A Sequential Analysis Approach. 14-25
David W. Juedes, Jack H. Lutz:
Completeness and Weak Completeness Under Polynomial-Size Circuits. 26-37

Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar:
Communication Complexity of Key Agreement on Small Ranges. 38-49
Yenjo Han, Lane A. Hemaspaandra:
Pseudorandom Generators and the Frequency of Simplicity. 50-59

Ulrich Hertrampf:
Classes of Bounded Counting Type and their Inclusion Relations. 60-70
Frederic Green:
Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates. 71-82
Matthias Krause:
On Realizing Iterated Multiplication by Small Depth Threshold Circuits. 83-94
Bruno Durand:
A Random NP-Complete Problem for Inversion of 2D Cellular Automata. 95-106

Isabelle Fagnot:
On the Subword Equivalence Problem for Infinite Words. 107-118
Emmanuelle Garel:
On the Separators on an Infinite Word Generated by a Morphism. 119-130
Angelo Monti, Adriano Peron:
Systolic Tree Omega-Languages. 131-142
Sriram C. Krishnan, Anuj Puri, Robert K. Brayton:
Structural Complexity of Omega-Automata. 143-156

Torsten Minkwitz:
Algorithms Explained by Symmetries. 157-167
Paul F. Fischer, Franco P. Preparata, John E. Savage:
Generalized Scans and Tri-Diagonal Systems. 168-180
Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter:
Two-Dimensional Pattern Matching in Linear Time and Small Space. 181-192
Hristo Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis:
On-line and Dynamic Algorithms for Shorted Path Problems. 193-204

Marco Cadoli, Francesco M. Donini, Marco Schaerf:
On Compact Representations of Propositional Circumscription. 205-216
Giovanna D'Agostino, Angelo Montanari, Alberto Policriti:
A Set-Theoretic Translation Method for (Poly)modal Logics. 217-228
Oded Maler, Amir Pnueli, Joseph Sifakis:
On the Synthesis of Discrete Controllers for Timed Systems (An Extended Abstract). 229-242
Michele Boreale, Davide Sangiorgi:
A Fully Abstract Semantics for Causality in the Pi-Calculus. 243-254

Juraj Hromkovic, Krzysztof Lorys, Przemyslawa Kanarek, Ralf Klasing, Walter Unger, Hubert Wagener:
On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks. 255-266
Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann:
Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations. 267-278
Michele Flammini, Giorgio Gambosi, Sandro Salomone:
Interval Routing Schemes. 279-290
Friedhelm Meyer auf der Heide, Berthold Vöcking:
A Packet Routing Protocol for Arbitrary Networks. 291-302

Christiane Bercoff:
A Family of Tag Systems for Paperfolding Sequences. 303-312
Gerhard Buntrock, Friedrich Otto:
Growing Context-Sensitive Languages and Church-Rosser Languages. 313-324
Dora Giammarresi, Rosa Montalbano:
Deterministic Generalized Automata. 325-336
Piotr Indyk:
Optimal Simulation of Automata by Neural Nets. 337-348

Albert R. Meyer:
Concurrent Process Equivalences: Some Decision Problems (Abstract). 349

Pavol Duris, José D. P. Rolim:
Optimal Lower Bounds on the Multiparty Communication Complexity. 350-360
László Babai, Peter G. Kimmel, Satyanarayana V. Lokam:
Simultaneous Messages vs. Communication. 361-372

Véronique Bruyère, Clelia de Felice:
Coding and Strong Coding in Trace Monoids. 373-384
Volker Diekert, Anca Muscholl, Klaus Reinhardt:
On Codings of Traces. 385-396

Arvind Gupta, Naomi Nishimura:
Finding Largest Common Embeddable Subtrees. 397-408
Damon Kaller, Arvind Gupta, Thomas C. Shermer:
The Chi-t-Coloring Problem. 409-420
Sotiris E. Nikoletseas, Paul G. Spirakis:
Expander Properties in Random Regular Graphs with Edge Faults. 421-432
Danièle Gardy, Guy Louchard:
Dynamic Analysis of the Sizes of Relations. 433-444

Danny Raz:
On Slender Context-free Languages. 445-454
Valentin M. Antimirov:
Partial Derivates of Regular Expressions and Finite Automata Constructions. 455-466
Felipe Bracho, Manfred Droste, Dietrich Kuske:
Dependence Orders for Computations of Concurrent Automata. 467-478
Anne-Cécile Fabret, Antoine Petit:
On the Undecidability of Deadlock Detection in Families of Nets. 479-490

Christine Rüb:
On the Average Running Time of Odd-Even Merge Sort. 491-502
Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt, Peter Rossmanith:
Optimal Average Case Sorting on Arrays. 503-514

Martin Strauss:
Normal Numbers and Sources for BPP. 515-526
Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp:
Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). 527-538

Peter Damaschke:
Line Segmentation of Digital Curves in Parallel. 539-549
Martin Kummer, Marcus Schäfer:
Computability of Convex Sets (Extended Abstract). 550-561
Thomas Ottmann, Sven Schuierer, Subbiah Soundaralakshmi:
Enumerating Extreme Points in Higher Dimensions. 562-570
Sylvain Petitjean:
The Number of Views of Piecewise-Smooth Algebraic Objects. 571-582

Ioan I. Macarie:
On the Structure of Log-Space Probabilistic Complexity Classes (Extended Abstract). 583-596
Lance Fortnow, Martin Kummer:
Resource-Bounded Instance Complexity (Extended Abstract). 597-608
Harry Buhrman, Montserrat Hermo:
On the Sparse Set Conjecture for Sets with Low Denisty. 609-618
Stephen A. Fenner, Lance Fortnow:
Beyond P^(NP) - NEXP. 619-627
Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Malign Distributions for Average Case Circuit Complexity. 628-639

Didier Arquès, Christian J. Michel:
A Prossible Code in the Genetic Code. 640-651

Last update Fri May 25 08:41:59 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page