Automata, Languages and Programming 2006 / 1 - Taschenbuch

EAN (ISBN-13): 9783540359043
ISBN (ISBN-10): 3540359044
Gebundene Ausgabe
Taschenbuch
Erscheinungsjahr: 2006
Herausgeber: Bugliesi, Michele, Springer Berlin Heidelberg

Buch in der Datenbank seit 2007-05-27T07:24:53+02:00 (Berlin)
Detailseite zuletzt geändert am 2023-04-07T21:40:20+02:00 (Berlin)
ISBN/EAN: 9783540359043

ISBN - alternative Schreibweisen:
3-540-35904-4, 978-3-540-35904-3
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: programming language, sassone, ingo wegener, sasso, michel, sasson, vladimiro
Titel des Buches: automata art, proceedings the international colloquium language, automata languages and programming, only italy, 2006, seeing venice, lecture notes computer science

---

Daten vom Verlag:

Autor/in: Michele Bugliesi; Bart Preneel; Vladimiro Sassone; Ingo Wegener
Titel: Theoretical Computer Science and General Issues; Lecture Notes in Computer Science; Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I
Verlag: Springer; Springer Berlin
732 Seiten
Erscheinungsjahr: 2006-06-30
Berlin; Heidelberg; DE
Sprache: Englisch
106,99 € (DE)
109,99 € (AT)
118,00 CHF (CH)
Available
XXIV, 732 p.

BC; Hardcover, Softcover / Informatik, EDV/Informatik; Software Engineering; Verstehen; Informatik; Automat; algorithms; automata; complexity; data structures; formal language; formal languages; game theory; programming; regular expressions; security; Software Engineering; Theory of Computation; Discrete Mathematics in Computer Science; Numerical Analysis; Data Science; Data Structures and Information Theory; Theoretische Informatik; Mathematik für Informatiker; Diskrete Mathematik; Numerische Mathematik; Datenbanken; Algorithmen und Datenstrukturen; Informationstheorie; EA

Invited Lectures.- Additive Approximation for Edge-Deletion Problems (Abstract).- Graph Theory I.- Testing Graph Isomorphism in Parallel by Playing a Game.- The Spectral Gap of Random Graphs with Given Expected Degrees.- Embedding Bounded Bandwidth Graphs into ?1.- On Counting Homomorphisms to Directed Acyclic Graphs.- Quantum Computing.- Fault-Tolerance Threshold for a Distance-Three Quantum Code.- Lower Bounds on Matrix Rigidity Via a Quantum Argument.- Self-testing of Quantum Circuits.- Deterministic Extractors for Independent-Symbol Sources.- Randomness.- Gap Amplification in PCPs Using Lazy Random Walks.- Stopping Times, Metrics and Approximate Counting.- Formal Languages.- Algebraic Characterization of the Finite Power Property.- P-completeness of Cellular Automaton Rule 110.- Small Sweeping 2NFAs Are Not Closed Under Complement.- Expressive Power of Pebble Automata.- Approximation Algorithms I.- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs.- Better Algorithms for Minimizing Average Flow-Time on Related Machines.- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.- Edge Disjoint Paths in Moderately Connected Graphs.- Approximation Algorithms II.- A Robust APTAS for the Classical Bin Packing Problem.- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.- Approximating the Orthogonal Knapsack Problem for Hypercubes.- Graph Algorithms I.- A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs.- Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.- Weighted Bipartite Matching in Matrix Multiplication Time.- Algorithms I.- Optimal Resilient Sorting and Searching in the Presence of Memory Faults.- Reliable and Efficient ComputationalGeometry Via Controlled Perturbation.- Tight Bounds for Selfish and Greedy Load Balancing.- Complexity I.- Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies.- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.- Data Structures and Linear Algebra.- Suffix Trays and Suffix Trists: Structures for Faster Text Indexing.- Optimal Lower Bounds for Rank and Select Indexes.- Dynamic Interpolation Search Revisited.- Dynamic Matrix Rank.- Graphs.- Nearly Optimal Visibility Representations of Plane Graphs.- Planar Crossing Numbers of Genus g Graphs.- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover.- Tight Approximation Algorithm for Connectivity Augmentation Problems.- Complexity II.- On the Bipartite Unique Perfect Matching Problem.- Comparing Reductions to NP-Complete Sets.- Design Is as Easy as Optimization.- On the Complexity of 2D Discrete Fixed Point Problem.- Game Theory I.- Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions.- The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games.- Network Games with Atomic Players.- Algorithms II.- Finite-State Dimension and Real Arithmetic.- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings.- The Myriad Virtues of Wavelet Trees.- Game Theory II.- Atomic Congestion Games Among Coalitions.- Computing Equilibrium Prices in Exchange Economies with Tax Distortions.- New Constructions of Mechanisms with Verification.- Networks, Circuits and Regular Expressions.- On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations.- Dynamic Routing Schemes for General Graphs.-Energy Complexity and Entropy of Threshold Circuits.- New Algorithms for Regular Expression Matching.- Fixed Parameter Complexity and Approximation Algorithms.- A Parameterized View on Matroid Optimization Problems.- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction.- Length-Bounded Cuts and Flows.- Graph Algorithms II.- An Adaptive Spectral Heuristic for Partitioning Random Graphs.- Some Results on Matchgates and Holographic Algorithms.- Weighted Popular Matchings.