default search action
12th STACS 1995: Munich, Germany
- Ernst W. Mayr, Claude Puech:
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
- Wolfgang Thomas:
On the Synthesis of Strategies in Infinite Games. 1-13
Complexity Theory I
- 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
Cryptography
- 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
Complexity Theory II
- 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
Automata Theory I
- 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
Algorithms
- 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 N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis
On-line and Dynamic Algorithms for Shorted Path Problems. 193-204
Logic
- Marco Cadoli, Francesco M. Donini
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
A Fully Abstract Semantics for Causality in the Pi-Calculus. 243-254
Theory of Parallel Computing I
- 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
Automata Theory II
- 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
Invited Talk
- Albert R. Meyer:
Concurrent Process Equivalences: Some Decision Problems (Abstract). 349
Communication Theory
- Pavol Duris, José D. P. Rolim:
Optimal Lower Bounds on the Multiparty Communication Complexity. 350-360 - László Babai
Simultaneous Messages vs. Communication. 361-372
Automata Theory III
- 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
Graph Theory, Data Bases
- 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
Automata Theory IV
- 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
Theory of Parallel Computing II
- 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
Complexity Theory III
- Martin Strauss:
Normal Numbers and Sources for BPP. 515-526 - Thomas R. Hancock, Tao Jiang
Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). 527-538
Computational Geometry
- 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
Complexity Theory IV
- 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
Invited Talk
- Didier Arquès, Christian J. Michel:
A Prossible Code in the Genetic Code. 640-651
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-06 23:26 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: