## STACS 99 [electronic resource] : 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4–6, 1999 Proceedings / edited by Christoph Meinel, Sophie Tison.

Material type: TextLanguage: English Series: Lecture Notes in Computer Science: 1563Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg, 1999Description: XIV, 590 p. online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783540491163Subject(s): Computer science | Data structures (Computer science) | Information theory | Computer Science | Theory of Computation | Mathematics of Computing | Data Structures | Programming Languages, Compilers, InterpretersAdditional physical formats: Printed edition:: No titleDDC classification: 004.0151 LOC classification: QA75.5-76.95Online resources: Click here to access onlineInvited 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.

The Symposium on Theoretical Aspects of Computer Science (STACS) is held annually, alternating between France and Germany. The current volume cons- tutes the proceedings of the 16th STACS conference, organized jointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft fur ¨ Informatik (GI) in Germany, and Maison de l’Informatique et des Math e- tiques Discr etes (MIMD) in France. The conference took place in Trier { the oldest town in Germany, with more than 2 millennia of history. Previous symposia of the series were held in Paris (1984), Saarbru ¨cken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wur ¨ zburg (1993), Caen (1994), Mu ¨nchen (1995), Grenoble (1996), Lu ¨beck (1997), and Paris (1998). All proceedings of the series have been published in the Lecture Notes of Computer Science series of Springer-Verlag. STACShasbecome oneofthe mostimportantannualmeetingsin Europefor the theoretical computer science community. This time, altogether 300 authors from36countriesonv econtinentssubmittedtheirpapers.Eachsubmissionwas sent to v e members of the program committee for review. During the program committee session 51 out of the 146 submissions were accepted for presen- tion. In two of the selected papers the same result was proved independently.

There are no comments on this title.