06502nam 22007095 450 99646547590331620200705225955.03-540-36494-310.1007/3-540-36494-3(CKB)1000000000211938(SSID)ssj0000326857(PQKBManifestationID)11225669(PQKBTitleCode)TC0000326857(PQKBWorkID)10297708(PQKB)11139048(DE-He213)978-3-540-36494-8(MiAaPQ)EBC3071509(PPN)155209523(EXLCZ)99100000000021193820121227d2003 u| 0engurnn|008mamaatxtccrSTACS 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 Habib1st ed. 2003.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2003.1 online resource (XVIII, 706 p.) Lecture Notes in Computer Science,0302-9743 ;2607Bibliographic Level Mode of Issuance: Monograph3-540-00623-0 Includes bibliographical references and index.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.Lecture Notes in Computer Science,0302-9743 ;2607ComputersComputer scienceData structures (Computer science)Computer science—MathematicsTheory of Computationhttps://scigraph.springernature.com/ontologies/product-market-codes/I16005Computer Science, generalhttps://scigraph.springernature.com/ontologies/product-market-codes/I00001Data Structureshttps://scigraph.springernature.com/ontologies/product-market-codes/I15017Discrete Mathematics in Computer Sciencehttps://scigraph.springernature.com/ontologies/product-market-codes/I17028Computers.Computer science.Data structures (Computer science).Computer science—Mathematics.Theory of Computation.Computer Science, general.Data Structures.Discrete Mathematics in Computer Science.004Alt Helmutedthttp://id.loc.gov/vocabulary/relators/edtHabib Micheledthttp://id.loc.gov/vocabulary/relators/edtSymposium on Theoretical Aspects of Computer ScienceMiAaPQMiAaPQMiAaPQBOOK996465475903316STACS 20032168171UNISA