STACS 20012001年第18届年度计算机科学的理论问题讨论会文集

The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form. Enjoying tight cooperation with the R&D community, with numerous individuals, as well as with prestigious organizations and Societies, LNCS has grown into the most comprehensive computer science research forum available.
The scope of LNCS, including its sub series LNAI, spans the whole range of computer science and information technology including interdisciplinary topics in a variety of application fields. The type of material published traditionally includes
　　- Proceedings (published in time for the respective conference)
　 - Post-proceedings (consisting of thoroughly revised final full papers)
　 -research monographs (which may be based on outstanding PhD work, research projects, technical reports, etc.)

Invited Presentations
　Recurrence in Infinite Words (Extended Abstract)
　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 Educationally Axiomatically
　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 Clasls of Languages Recognizable by 1-Way Quantun Finite Automata
　Star-Free Open Languages and Aperiodic Loops
　A 5/2n2-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 Sub graphs
　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 (Extended Abstract)
　Scalable Sparse Topologies with Small Spectrum
　Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios
……
Author Index