STACS 2002 (eBook, PDF)

19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings
Redaktion: Alt, Helmut; Ferreira, Afonso

• Format: PDF

Produktbeschreibung

This book constitutes the refereed proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002, held in Antibes - Juan les Pins, France, in March 2002.The 50 revised full papers presented together with three invited papers were carefully reviewed and selected from a total of 209 submissions. The book offers topical sections on algorithms, current challenges, computational and structural complexity, automata and formal languages, and logic in computer science.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Berlin Heidelberg
• Seitenzahl: 660
• Erscheinungstermin: 3. August 2003
• Englisch
• ISBN-13: 9783540458418
• Artikelnr.: 53389348

Autorenporträt

Helmut Alt, Freie Universität Berlin, Germany / Afonso Ferreira, INRIA Sophia-Antipolis, France

Inhaltsangabe

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.- 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.- 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.