STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings / edited by Afonso Ferreira, Horst Reichel.

Saved in:

Bibliographic Details
Corporate Author:	SpringerLink (Online service)
Other Authors:	Ferreira, Afonso (Editor), Reichel, Horst (Editor)
Format:	eBook
Language:	English
Published:	Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2001.
Edition:	1st ed. 2001.
Series:	Lecture Notes in Computer Science, 2010 Springer eBook Collection.
Subjects:	Computers. Data structures (Computer science). Optical data processing. Computer science—Mathematics. Electronic resources (E-books)
Online Access:	Click to view e-book
Holy Cross Note:	Loaded electronically. Electronic access restricted to members of the Holy Cross Community.

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

STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings / edited by Afonso Ferreira, Horst Reichel.

Similar Items