STACS 2003 [[electronic resource] ] : 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003. Proceedings / / edited by Helmut Alt, Michel Habib

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003
• Edizione: 1st ed. 2003.
• Descrizione fisica: 1 online resource (XVIII, 706 p.)
• Disciplina: 004
• Soggetto topico: Computers; Computer science; Data structures (Computer science); Computer science—Mathematics; Theory of Computation; Computer Science, general; Data Structures; Discrete Mathematics in Computer Science
• Persona (resp. second.): AltHelmut; HabibMichel
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Invited Papers -- Logic as a Query Language: From Frege to XML -- How Does Computer Science Change Molecular Biology? -- Contributed Papers -- Improved Compact Visibility Representation of Planar Graph via Schnyder’s Realizer -- Rectangle Visibility Graphs: Characterization, Construction, and Compaction -- Approximating Geometric Bottleneck Shortest Paths -- Optimization in Arrangements -- Complete Classifications for the Communication Complexity of Regular Languages -- The Commutation with Codes and Ternary Sets of Words -- On the Confluence of Linear Shallow Term Rewrite Systems -- Wadge Degrees of ?-Languages of Deterministic Turing Machines -- Faster Deterministic Broadcasting in Ad Hoc Radio Networks -- Private Computations in Networks: Topology versus Randomness -- On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements -- Lattice Reduction by Random Sampling and Birthday Methods -- On the Ultimate Complexity of Factorials -- On the Effective Jordan Decomposability -- Fast Algorithms for Extended Regular Expression Matching and Searching -- Algorithms for Transposition Invariant String Matching (Extended Abstract) -- On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets -- Some Results on Derandomization -- On the Representation of Boolean Predicates of the Diffie-Hellman Function -- Quantum Circuits with Unbounded Fan-out -- Analysis of the Harmonic Algorithm for Three Servers -- Non-clairvoyant Scheduling for Minimizing Mean Slowdown -- Space Efficient Hash Tables with Worst Case Constant Access Time -- Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure -- Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs -- Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs -- Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids -- Algebraic Characterizations of Small Classes of Boolean Functions -- On the Difficulty of Some Shortest Path Problems -- Representing Graph Metrics with Fewest Edges -- Computing Shortest Paths with Uncertainty -- Solving Order Constraints in Logarithmic Space -- The Inversion Problem for Computable Linear Operators -- Algebras of Minimal Rank over Arbitrary Fields -- Evolutionary Algorithms and the Maximum Matching Problem -- Alternative Algorithms for Counting All Matchings in Graphs -- Strong Stability in the Hospitals/Residents Problem -- The Inference Problem for Propositional Circumscription of Afine Formulas Is coNP-Complete -- Decidable Theories of Cayley-Graphs -- The Complexity of Resolution with Generalized Symmetry Rules -- Colouring Random Graphs in Expected Polynomial Time -- An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation -- Finding Large Independent Sets in Polynomial Expected Time -- Distributed Soft Path Coloring -- Competing Provers Yield Improved Karp-Lipton Collapse Results -- One Bit of Advice -- Strong Reductions and Immunity for Exponential Time -- The Complexity of Membership Problems for Circuits over Sets of Natural Numbers -- Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem -- Cake-Cutting Is Not a Piece of Cake -- The Price of Truth: Frugality in Truthful Mechanisms -- Untameable Timed Automata! -- The Intrinsic Universality Problem of One-Dimensional Cellular Automata -- On Sand Automata -- Adaptive Sorting and the Information Theoretic Lower Bound -- A Discrete Subexponential Algorithm for Parity Games -- Cryptographically Sound and Machine-Assisted Verification of Security Protocols -- Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic.
• Titolo autorizzato: STACS 2003
• ISBN: 3-540-36494-3
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996465475903316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture Notes in Computer Science, . 0302-9743 ; ; 2607