STACS 2001 : 18th annual Symposium on theoretical aspects of computer science, Dresden, Germany, february 15-17, 2001 : proceedings
Sparad:
| Institutionell upphovsman: | |
|---|---|
| Övriga upphovsmän: | , |
| Materialtyp: | Livre numérique |
| Språk: | Anglais |
| Publicerad: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Serie: | Lecture notes in computer science
2010 |
| Ämnen: | |
| Länkar: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Anmärkning: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • STACS 2001, 18th annual Symposium on theoretical aspects of computer science, Dresden, Germany, february 15-17, 2001, proceedings, Afonso Ferreira, Horst Reichel (eds.), 2001, Berlin [etc.], Springer, 1 volume (XV-576 pages), Lecture notes in computer science, 3-540-41695-1 • STACS 2001, Texte imprimé, 9783662190920 |
Innehållsförteckning:
- Invited Presentations
- Recurrence in Infinite Words
- Generalized Model-Checking Problems for First-Order Logic
- Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra
- Contributions
- 2-Nested Simulation Is Not Finitely Equationally Axiomatizable
- On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems
- Matching Polygonal Curves with Respect to the Fréchet Distance
- On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
- Star-Free Open Languages and Aperiodic Loops
- A 5/2n 2-Lower Bound for the Multiplicative Complexity of n . n-Matrix Multiplication
- Evasiveness of Subgraph Containment and Related Properties
- On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs
- On Presburger Liveness of Discrete Timed Automata
- Residual Finite State Automata
- Deterministic Radio Broadcasting at Low Cost
- The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE Complete
- Recursive Randomized Coloring Beats Fair Dice Random Colorings
- Randomness, Computability, and Density
- On Multipartition Communication Complexity
- Scalable Sparse Topologies with Small Spectrum
- Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios
- The UPS Problem
- Gathering of Asynchronous Oblivious Robots with Limited Visibility
- Generalized Langton s Ant: Dynamical Behavior and Complexity
- Optimal and Approximate Station Placement in Networks
- Learning Expressions over Monoids
- Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods
- On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages
- Efficient Minimal Perfect Hashing in NearlyMinimal Space
- Small PCPs with Low Query Complexity
- Space Efficient Algorithms for Series-Parallel Graphs
- A Toolkit for First Order Extensions of Monadic Games
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Refining the Hierarchy of Blind Multicounter Languages
- A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab*c
- New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata
- The Complexity of Minimal Satisfiability Problems
- On the Minimal Hardware Complexity of Pseudorandom Function Generators
- Approximation Algorithms for Minimum Size 2-Connectivity Problems
- A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets
- An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases
- A New Logical Characterization of Büchi Automata
- A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph
- The Complexity of Copy Constant Detection in Parallel Programs
- Approximation Algorithms for the Bottleneck Stretch Factor Problem
- Semantical Principles in the Modal Logic of Coalgebras
- The #a = #b Pictures Are Recognizable
- A Logical Approach to Decidability of Hierarchies of Regular Star Free Languages
- Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables
- New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.