Overview

This book constitutes the refereed proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001, held in Dresden, Germany in February 2001. The 46 revised full papers presented together with three invited papers were carefully reviewed and selected from a total of 153 submissions. The papers address foundational aspects from all current areas of theoretical computer science including algorithms, data structures, automata, formal languages, complexity, verification, logic, graph theory, optimization, etc.

Full Product Details

Author:   Afonso Ferreira ,  Horst Reichel
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   2001 ed.
Volume:   2010
Dimensions:   Width: 15.50cm , Height: 3.00cm , Length: 23.30cm
Weight:   1.830kg
ISBN:  

9783540416951

ISBN 10:   3540416951
Pages:   580
Publication Date:   07 February 2001
Audience:   Professional and scholarly ,  College/higher education ,  Professional & Vocational ,  Postgraduate, Research & Scholarly
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

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 Frechet 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 x 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 Buchi-Type Theorems and First-Order Logic for N-Free Pomsets.- An Ehrenfeucht-Fraisse Approach to Collapse Results for First-Order Queries over Embedded Databases.- A New Logical Characterization of Buchi 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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions