Stacs 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 P by Christoph MeinelStacs 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 P by Christoph Meinel

Stacs 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4…

EditorChristoph Meinel, Sophie Tison


Pricing and Purchase Info


Earn 970 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


This book constitutes the refereed proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 99, held in Trier, Germany in March 1999. The 51 revised full papers presented were selected from a total of 146 submissions. Also included are three invited papers. The volume is divided in topical sections on complexity, parallel algorithms, computational geometry, algorithms and data structures, automata and formal languages, verification, algorithmic learning, and logic in computer science.
Title:Stacs 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4…Format:PaperbackDimensions:596 pagesPublisher:Springer Berlin Heidelberg

The following ISBNs are associated with this title:

ISBN - 10:354065691X

ISBN - 13:9783540656913

Look for similar items by category:


Table of Contents

Invited Talks.- Algorithms for Selfish Agents.- The Reduced Genus of a Multigraph.- Classifying Discrete Temporal Properties.- Complexity 1.- Circuit Complexity of Testing Square-Free Numbers.- Relating Branching Program Size and Formula Size over the Full Binary Basis.- Theory of Parallel Algorithms 1.- Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines.- The Average Time Complexity to Compute Prefix Functions in Processor Networks.- Complexity 2.- On the Hardness of Permanent.- One-Sided Versus Two-Sided Error in Probabilistic Computation.- Computational Geometry.- An Optimal Competitive Strategy for Walking in Streets.- An Optimal Strategy for Searching in Unknown Streets.- Parallel Searching on m Rays.- Complexity 3.- A Logical Characterisation of Linear Time on Nondeterministic Turing Machines.- Descriptive Complexity of Computable Sequences.- Complexity of Some Problems in Universal Algebra.- Algorithms and Data Structures 1.- New Branchwidth Territories.- Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions.- Treewidth and Minimum Fill-In of Weakly Triangulated Graphs.- Automata and Formal Languages.- Decidability and Undecidability of Marked PCP.- On Quadratic Word Equations.- Some Undecidability Results Related to the Star Problem in Trace Monoids.- Algorithms and Data Structures 2.- An Approximation Algorithm for Max p-Section.- Approximating Bandwidth by Mixing Layouts of Interval Graphs.- Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs.- Complexity 4.- Extending Downward Collapse from 1-versus-2 Queries to j-versus-j + 1 Queries.- Sparse Sets, Approximable Sets, and Parallel Queries to NP.- Algorithms and Data Structures 3.- External Selection.- Fast Computations of the Exponential Function.- Verification.- A Model of Behaviour Abstraction for Communicating Processes.- Model Checking Lossy Vector Addition Systems.- Algorithms and Data Structures 4.- Constructing Light Spanning Trees with Small Routing Cost.- Finding Paths with the Right Cost.- Complexity 5.- In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?.- Lower Bounds for Dynamic Algebraic Problems.- An Explicit Lower Bound for TSP with Distances One and Two.- Theory of Parallel Algorithms 2.- Scheduling Dynamic Graphs.- Supporting Increment and Decrement Operations in Balancing Networks.- Worst-Case Equilibria.- Algorithmic Learning.- A Complete and Tight Average-Case Analysis of Learning Monomials.- Costs of General Purpose Learning.- Universal Distributions and Time-Bounded Kolmogorov Complexity.- Logic in Computer Science.- The Descriptive Complexity Approach to LOGCFL.- The Weakness of Self-Complementation.- On the Difference of Horn Theories.- Complexity 6.- On Quantum Algorithms for Noncommutative Hidden Subgroups.- On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions.- How To Forget a Secret.- Logic in Computer Science 2.- A Modal Fixpoint Logic with Chop.- Completeness of Neighbourhood Logic.- Eliminating Recursion in the ?-Calculus.- Complexity 7.- On Optimal Algorithms and Optimal Proof Systems.- Space Bounds for Resolution.- Algorithms and Data Structures 5.- Upper Bounds for Vertex Cover Further Improved.- Online Matching for Scheduling Problems.