Automata, Languages and Programming - neues Buch

EAN (ISBN-13): 9783642141652
Erscheinungsjahr: 2010
Herausgeber: Springer Berlin Heidelberg

Buch in der Datenbank seit 2016-12-08T17:18:46+01:00 (Vienna)
Detailseite zuletzt geändert am 2024-03-12T16:46:23+01:00 (Vienna)
ISBN/EAN: 9783642141652

ISBN - alternative Schreibweisen:
978-3-642-14165-2
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: paul meyer, paul kirchner, claude, abramsky
Titel des Buches: automata, bordeaux, colloquium international

---

Daten vom Verlag:

Autor/in: Samson Abramsky; Cyril Gavoille; Claude Kirchner; Friedhelm Meyer auf der Heide; Paul Spirakis
Titel: Theoretical Computer Science and General Issues; Lecture Notes in Computer Science; Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I
Verlag: Springer; Springer Berlin
754 Seiten
Erscheinungsjahr: 2010-07-05
Berlin; Heidelberg; DE
Sprache: Englisch
96,29 € (DE)
99,00 € (AT)
118,00 CHF (CH)
Available
XXIII, 754 p. 42 illus.

EA; E107; eBook; Nonbooks, PBS / Informatik, EDV/Informatik; Software Engineering; Verstehen; C programming language; Rack; algorithms; complexity; logic; programming; algorithm analysis and problem complexity; C; Software Engineering; Programming Techniques; Computer Communication Networks; Algorithms; Artificial Intelligence; Theory of Computation; Computer Science; Computerprogrammierung und Softwareentwicklung; Netzwerk-Hardware; Algorithmen und Datenstrukturen; Künstliche Intelligenz; Theoretische Informatik; BC

Invited Talks.- Local Search: Simple, Successful, But Sometimes Sluggish.- When Conflicting Constraints Can Be Resolved – The Lovász Local Lemma and Satisfiability.- Session 1-Track A. Combinatorial Optimization.- Plane Spanners of Maximum Degree Six.- The Positive Semidefinite Grothendieck Problem with Rank Constraint.- Cycle Detection and Correction.- Decomposition Width of Matroids.- Session 2-Track A1. Game Theory.- The Cooperative Game Theory Foundations of Network Bargaining Games.- On the Existence of Pure Nash Equilibria in Weighted Congestion Games.- On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.- Mean-Payoff Games and Propositional Proofs.- Session 2-Track A2. Security.- Online Network Design with Outliers.- Efficient Completely Non-malleable Public Key Encryption.- Polynomial-Space Approximation of No-Signaling Provers.- From Secrecy to Soundness: Efficient Verification via Secure Computation.- Session 3-Track A1. Data Structures.- Mergeable Dictionaries.- Faster Algorithms for Semi-matching Problems (Extended Abstract).- Clustering with Diversity.- New Data Structures for Subgraph Connectivity.- Session 3-Track A2. Sorting & Hashing.- Tight Thresholds for Cuckoo Hashing via XORSAT.- Resource Oblivious Sorting on Multicores.- Interval Sorting.- Session 4-Track A. Graphs, Nets and Optimization.- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.- Thresholded Covering Algorithms for Robust and Max-min Optimization.- Graph Homomorphisms with Complex Values: A Dichotomy Theorem.- Metrical Task Systems and the k-Server Problem on HSTs.- Session 5-Track A1. Scheduling.- Scheduling Periodic Tasks in a Hard Real-Time Environment.- Scalably Scheduling Power-Heterogeneous Processors.- BetterScalable Algorithms for Broadcast Scheduling.- Max-min Online Allocations with a Reordering Buffer.- Session 5-Track A2. Graphs & Hypergraphs.- Orientability of Random Hypergraphs and the Power of Multiple Choices.- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.- Dynamic Programming for Graphs on Surfaces.- Interval Graphs: Canonical Representation in Logspace.- Session 6-Track A. Best Paper Award.- Approximating the Partition Function of the Ferromagnetic Potts Model.- Session 7-Track A. Algebraic Problems.- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.- On Sums of Roots of Unity.- Exponential Time Complexity of the Permanent and the Tutte Polynomial.- On Approximate Horn Formula Minimization.- Session 8-Track A. Networks & Communication Complexity.- Choosing, Agreeing, and Eliminating in Communication Complexity.- Additive Spanners in Nearly Quadratic Time.- Composition Theorems in Communication Complexity.- Network Design via Core Detouring for Problems without a Core.- Session 9-Track A1. Complexity & Automata.- Weak Completeness Notions for Exponential Time.- Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.- On the Complexity of Searching in Trees: Average-Case Minimization.- Session 9-Track A2. Finding & Testing.- Finding Is as Easy as Detecting for Quantum Walks.- Improved Constructions for Non-adaptive Threshold Group Testing.- Testing Non-uniform k-Wise Independent Distributions over Product Spaces.- Session 10-Track A1. Approximations.- A Sublogarithmic Approximation for Highway and Tollbooth Pricing.- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm.- Cell Probe Lower Bounds and Approximationsfor Range Mode.- SDP Gaps for 2-to-1 and Other Label-Cover Variants.- Session 10-Track A2. Streaming & Preprocessing.- Data Stream Algorithms for Codeword Testing.- Streaming Algorithms for Independent Sets.- Preprocessing of Min Ones Problems: A Dichotomy.- Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems.- Session 11-Track A1. Adaptive, Knowledge & Optimality.- Optimal Trade-Offs for Succinct String Indexes.- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.- Concurrent Knowledge Extraction in the Public-Key Model.- Session 11-Track A2. Covering, Graphs & Independence.- On the k-Independence Required by Linear Probing and Minwise Independence.- Covering and Packing in Linear Space.- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs.