STACS 2000 : 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17 19, 2000 : proceedings
Gardado en:
| Autor Corporativo: | |
|---|---|
| Outros autores: | , |
| Formato: | Livre numérique |
| Idioma: | Anglais |
| Publicado: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Series: | Lecture notes in computer science
1770 |
| Sujets: | |
| Acceso en liña: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Nota: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • STACS 2000, proceedings, 17th Annual Symposium on Theoretical Aspects of computer Science, Lille, France, February 17-19, 2000, 2000, Berlin, Springer, 1 vol. (XIV-662 p.), Lecture notes in computer science, 3-540-67141-2 • STACS 2000, Texte imprimé, 9783662162170 |
Table des matières:
- Codes and Graphs
- A Classification of Symbolic Transition Systems
- Circuits versus Trees in Algebraic Complexity
- On the Many Faces of Block Codes
- A New Algorithm for MAX-2-SAT
- Bias Invariance of Small Upper Spans
- The Complexity of Planarity Testing
- About Cube-Free Morphisms
- Linear Cellular Automata with Multiple State Variables
- Two-Variable Word Equations
- Average-Case Quantum Query Complexity
- Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs
- The Boolean Hierarchy of NP-Partitions
- Binary Exponential Backoff Is Stable for High Arrival Rates
- The Data Broadcast Problem with Preemption
- An Approximate L p-Difference Algorithm for Massive Data Streams
- Succinct Representations of Model Based Belief Revision
- Logics Capturing Local Properties
- The Complexity of Poor Man s Logic
- Fast Integer Sorting in Linear Space
- On the Performance of WEAK-HEAPSORT
- On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
- Real-Time Automata and the Kleene Algebra of Sets of Real Numbers
- Small Progress Measures for Solving Parity Games
- Multi-linearity Self-Testing with Relative Error
- Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
- Hard Instances of Hard Problems
- Simulation and Bisimulation over One-Counter Processes
- Decidability of Reachability Problems for Classes of Two Counters Automata
- Hereditary History Preserving Bisimilarity Is Undecidable
- The Hardness of Approximating Spanner Problems
- An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
- ?-Coloring of Graphs
- Optimal Proof Systems and Sparse Sets
- Almost Complete Sets
- GraphIsomorphism Is Low for ZPP(NP) and Other Lowness Results
- An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications
- Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem
- Controlled Conspiracy-2 Search
- The Stability of Saturated Linear Dynamical Systems Is Undecidable
- Tilings: Recursivity and Regularity
- Listing All Potential Maximal Cliques of a Graph
- Distance Labeling Schemes for Well-Separated Graph Classes
- Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs
- Characterizing and Deciding MSO-Definability of Macro Tree Transductions
- Languages of Dot-Depth 3/2
- Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures
- The CNN Problem and Other k-Server Variants
- The Weighted 2-Server Problem
- On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem
- Spectral Bounds on General Hard Core Predicates
- Randomness in Visual Cryptography
- Online Dial-a-Ride Problems: Minimizing the Completion Time
- The Power Range Assignment Problem in Radio Networks on the Plane.