STACS 2002 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings
Other Authors: | , |
---|---|
Format: | eBook |
Language: | English |
Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2002, 2002
|
Edition: | 1st ed. 2002 |
Series: | Lecture Notes in Computer Science
|
Subjects: | |
Online Access: | |
Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Invited Papers
- Hyper-Encryption and Everlasting Security
- Models and Techniques for Communication in Dynamic Networks
- What Is a Theory?
- Algorithms
- A Space Lower Bound for Routing in Trees
- Labeling Schemes for Dynamic Tree Networks
- Tight Bounds for the Performance of Longest-in-System on DAGs
- Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling
- Balanced Coloring: Equally Easy for All Numbers of Colors?
- The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
- On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets
- On Dualization in Products of Forests
- An Asymptotic (ln ?/ ln ln ?)-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs
- Scheduling at Twilight the EasyWay
- Complexity of Multi-dimensional Loop Alignment
- A Probabilistic 3—SAT Algorithm Further Improved
- How Many Missing Answers Can Be Tolerated by Query Learners?
- Games with a Uniqueness Property
- Bi-Immunity Separates Strong NP-Completeness Notions
- Complexity of Semi-algebraic Proofs
- A Lower Bound Technique for Restricted Branching Programs and Applications
- The Complexity of Constraints on Intervals and Lengths
- Automata and Formal Languages
- Nesting Until and Since in Linear Temporal Logic
- Comparing Verboseness for Finite Automata and Turing Machines
- On the Average Parallelism in Trace Monoids
- A Further Step towards a Theory of Regular MSC Languages
- Existential and Positive Theories of Equations in Graph Products
- The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL
- Recognizable Sets of Message Sequence Charts
- Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard
- On the Enumerative Sequences of Regular Languages on k Symbols
- Logic in Computer Science
- Ground Tree Rewriting Graphs of Bounded Tree Width
- Timed Control Synthesis for External Specifications
- Axiomatizing GSOS with Termination
- Axiomatising Tree-Interpretable Structures
- EXPSPACE-Complete Variant of Guarded Fragment with Transitivity
- A Parametric Analysis of the State Explosion Problem in Model Checking
- Generalized Model-Checking over Locally Tree-Decomposable Classes
- Learnability and Definability in Trees and Similar Structures
- The Secret of Selective Game Tree Search, When Using Random-Error Evaluations
- Randomized Acceleration of Fundamental Matrix Computations
- Approximations for ATSP with Parametrized Triangle Inequality
- A New Diagram from Disks in the Plane
- Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles
- Current Challenges
- On the Parameterized Intractability of Closest Substring and Related Problems
- On the Complexity of Protein Similarity Search under mRNA Structure Constraints
- Pure Dominance Constraints
- Improved Quantum Communication Complexity Bounds for Disjointness and Equality
- On Quantum Computation with Some Restricted Amplitudes
- A Quantum Goldreich-Levin Theorem with Cryptographic Applications
- On Quantum and Approximate Privacy
- On Quantum Versions of the Yao Principle.-Computational and Structural Complexity
- Describing Parameterized Complexity Classes
- On the Computational Power of Boolean Decision Lists