06285nam 22006975 450 991014360490332120200704023246.03-540-44693-110.1007/3-540-44693-1(CKB)1000000000211444(SSID)ssj0000326855(PQKBManifestationID)11213074(PQKBTitleCode)TC0000326855(PQKBWorkID)10297416(PQKB)10365181(DE-He213)978-3-540-44693-4(MiAaPQ)EBC3071938(PPN)155212044(EXLCZ)99100000000021144420121227d2001 u| 0engurnn|008mamaatxtccrSTACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings /edited by Afonso Ferreira, Horst Reichel1st ed. 2001.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2001.1 online resource (XVI, 580 p.) Lecture Notes in Computer Science,0302-9743 ;2010Bibliographic Level Mode of Issuance: Monograph3-540-41695-1 Includes bibliographical references at the end of each chapters and index.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.Lecture Notes in Computer Science,0302-9743 ;2010ComputersData structures (Computer science)Optical data processingComputer science—MathematicsTheory of Computationhttps://scigraph.springernature.com/ontologies/product-market-codes/I16005Data Structures and Information Theoryhttps://scigraph.springernature.com/ontologies/product-market-codes/I15009Image Processing and Computer Visionhttps://scigraph.springernature.com/ontologies/product-market-codes/I22021Data Structureshttps://scigraph.springernature.com/ontologies/product-market-codes/I15017Mathematics of Computinghttps://scigraph.springernature.com/ontologies/product-market-codes/I17001Computers.Data structures (Computer science)Optical data processing.Computer science—Mathematics.Theory of Computation.Data Structures and Information Theory.Image Processing and Computer Vision.Data Structures.Mathematics of Computing.004Ferreira Afonsoedthttp://id.loc.gov/vocabulary/relators/edtReichel Horstedthttp://id.loc.gov/vocabulary/relators/edtSymposium on Theoretical Aspects of Computer ScienceBOOK9910143604903321STACS 20011424639UNINA