STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2001.
|
| Έκδοση: | 1st ed. 2001. |
| Σειρά: | Lecture Notes in Computer Science,
2010 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- 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 Nearly Minimal 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.
