The Resource Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)
Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)
Resource Information
The item Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Missouri Libraries.This item is available to borrow from 2 library branches.
Resource Information
The item Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.) represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Missouri Libraries.
This item is available to borrow from 2 library branches.
 Summary
 Annotation The twovolume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008. The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing
 Language
 eng
 Extent
 1 online resource (896 pages).
 Contents

 Invited Lectures
 Graph Structure and Monadic SecondOrder Logic: Language Theoretical Aspects
 Internet Ad Auctions: Insights and Directions
 Track A: Algorithms, Automata, Complexity, and Games
 The Complexity of Boolean Formula Minimization
 Optimal Cryptographic Hardness of Learning Monotone Functions
 On Berge Multiplication for Monotone Boolean Dualization
 Diagonal Circuit Identity Testing and Lower Bounds
 CellProbe Proofs and Nondeterministic CellProbe Complexity
 Constructing Efficient Dictionaries in Close to Sorting Time
 On List Update with Locality of Reference
 A New Combinatorial Approach for Sparse Graph Problems
 How to Explore a FastChanging World (Cover Time of a Simple Random Walk on Evolving Graphs)
 Networks Become Navigable as Nodes Move and Forget
 Fast Distributed Computation of Cuts Via Random Circulations
 Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
 Function Evaluation Via Linear Programming in the Priced Information Model
 Improved Approximation Algorithms for Budgeted Allocations
 The Travelling Salesman Problem in Bounded Degree Graphs
 Treewidth Computation and Extremal Combinatorics
 Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines
 Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
 A PTAS for Static Priority RealTime Scheduling with Resource Augmentation
 Optimal Monotone Encodings
 PolynomialTime Construction of Linear Network Coding
 Complexity of Decoding PositiveRate ReedSolomon Codes
 Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
 The Randomized Coloring Procedure with SymmetryBreaking
 The Local Nature of List Colorings for Graphs of High Girth
 Approximating ListColoring on a Fixed Surface
 Asymptotically Optimal Hitting Sets Against Polynomials
 The Smoothed Complexity of Edit Distance
 Randomized Selfassembly for Approximate Shapes
 Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
 Competitive Weighted Matching in Transversal Matroids
 Scheduling for Speed Bounded Processors
 Faster Algorithms for Incremental Topological Ordering
 Dynamic Normal Forms and Dynamic Characteristic Polynomial
 Algorithms for?Approximations of Terrains
 An Approximation Algorithm for Binary Searching in Trees
 Algorithms for 2Route Cut Problems
 The TwoEdge Connectivity Survivable Network Problem in Planar Graphs
 Efficiently Testing Sparse GF(2) Polynomials
 Testing Properties of Sets of Points in Metric Spaces
 An Expansion Tester for Bounded Degree Graphs
 Property Testing on kVertexConnectivity of Graphs
 Almost 2SAT Is FixedParameter Tractable (Extended Abstract)
 On Problems without Polynomial Kernels (Extended Abstract)
 Faster Algebraic Algorithms for Path and Packing Problems
 Understanding the Complexity of Induced Subgraph Isomorphisms
 Spanners in Sparse Graphs
 Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
 AllPairs Shortest Paths with a Sublinear Additive Error
 Simpler LinearTime Modular Decomposition Via Recursive Factorizing Permutations
 The Complexity of the Counting Constraint Satisfaction Problem
 On the Hardness of Losing Weight
 Product Theorems Via Semidefinite Programming
 Sound 3Query PCPPs Are Long
 Approximative Methods for Monotone Systems of MinMaxPolynomial Equations
 Recursive Stochastic Games with Positive Rewards
 Complementation, Disambiguation, and Determinization of Büchi Automata Unified
 Tree Projections: Hypergraph Games and Minimality
 Explicit Nonadaptive Combinatorial Group Testing Schemes
 Tight Lower Bounds for Multipass Stream Computation Via Pass Elimination
 Impossibility of a Quantum SpeedUp with a Faulty Oracle
 Superpolynomial Speedups Based on Almost Any Quantum Circuit
 The Speed of Convergence in Congestion Games under BestResponse Dynamics
 Uniform Budgets and the EnvyFree Pricing Problem
 Bayesian Combinatorial Auctions
 Truthful Unification Framework for Packing Integer Programs with Choices
 Upper Bounds on the Noise Threshold for FaultTolerant Quantum Computing
 Finding Optimal Flows Efficiently
 Optimal Quantum Adversary Lower Bounds for Ordered Search
 Quantum SAT for a QutritCinquit Pair Is QMA 1Complete
 Superpolynomial Speedups Based on Almost Any Quantum Circuit
 Isbn
 9783540705741
 Label
 Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I
 Title
 Automata, languages and programming
 Title remainder
 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings
 Title number
 Part I
 Statement of responsibility
 Luca Aceto [and others] (eds.)
 Subject

 Computer programming
 Computer programming
 Computer programming
 Computer programming  Congresses
 Computer science
 Conference papers and proceedings
 Conference papers and proceedings
 Data Structures, Cryptology and Information Theory
 Data structures
 Discrete Mathematics in Computer Science
 Formal languages
 Formal languages
 Formal languages
 Formal languages  Congresses
 Informatique
 Machine theory
 Machine theory
 Machine theory
 Machine theory  Congresses
 Numeric Computing
 Software Engineering/Programming and Operating Systems
 Theory of Computation
 Language
 eng
 Summary
 Annotation The twovolume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008. The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing
 Cataloging source
 GW5XE
 Dewey number
 004.0151
 Index
 no index present
 LC call number
 QA267
 LC item number
 .I55 2008eb
 Literary form
 non fiction
 Nature of contents

 dictionaries
 bibliography
 Series statement
 Lecture notes in computer science,
 Series volume
 5125
 http://library.link/vocab/subjectName

 Machine theory
 Computer programming
 Formal languages
 Computer programming
 Computer science
 Data structures
 Data Structures, Cryptology and Information Theory
 Discrete Mathematics in Computer Science
 Numeric Computing
 Software Engineering/Programming and Operating Systems
 Theory of Computation
 Machine theory
 Formal languages
 Informatique
 Computer programming
 Formal languages
 Machine theory
 Label
 Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)
 Bibliography note
 Includes bibliographical references
 Carrier category
 online resource
 Carrier category code

 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code

 txt
 Content type MARC source
 rdacontent
 Contents
 Invited Lectures  Graph Structure and Monadic SecondOrder Logic: Language Theoretical Aspects  Internet Ad Auctions: Insights and Directions  Track A: Algorithms, Automata, Complexity, and Games  The Complexity of Boolean Formula Minimization  Optimal Cryptographic Hardness of Learning Monotone Functions  On Berge Multiplication for Monotone Boolean Dualization  Diagonal Circuit Identity Testing and Lower Bounds  CellProbe Proofs and Nondeterministic CellProbe Complexity  Constructing Efficient Dictionaries in Close to Sorting Time  On List Update with Locality of Reference  A New Combinatorial Approach for Sparse Graph Problems  How to Explore a FastChanging World (Cover Time of a Simple Random Walk on Evolving Graphs)  Networks Become Navigable as Nodes Move and Forget  Fast Distributed Computation of Cuts Via Random Circulations  Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time  Function Evaluation Via Linear Programming in the Priced Information Model  Improved Approximation Algorithms for Budgeted Allocations  The Travelling Salesman Problem in Bounded Degree Graphs  Treewidth Computation and Extremal Combinatorics  Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines  Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2  A PTAS for Static Priority RealTime Scheduling with Resource Augmentation  Optimal Monotone Encodings  PolynomialTime Construction of Linear Network Coding  Complexity of Decoding PositiveRate ReedSolomon Codes  Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)  The Randomized Coloring Procedure with SymmetryBreaking  The Local Nature of List Colorings for Graphs of High Girth  Approximating ListColoring on a Fixed Surface  Asymptotically Optimal Hitting Sets Against Polynomials  The Smoothed Complexity of Edit Distance  Randomized Selfassembly for Approximate Shapes  Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)  Competitive Weighted Matching in Transversal Matroids  Scheduling for Speed Bounded Processors  Faster Algorithms for Incremental Topological Ordering  Dynamic Normal Forms and Dynamic Characteristic Polynomial  Algorithms for?Approximations of Terrains  An Approximation Algorithm for Binary Searching in Trees  Algorithms for 2Route Cut Problems  The TwoEdge Connectivity Survivable Network Problem in Planar Graphs  Efficiently Testing Sparse GF(2) Polynomials  Testing Properties of Sets of Points in Metric Spaces  An Expansion Tester for Bounded Degree Graphs  Property Testing on kVertexConnectivity of Graphs  Almost 2SAT Is FixedParameter Tractable (Extended Abstract)  On Problems without Polynomial Kernels (Extended Abstract)  Faster Algebraic Algorithms for Path and Packing Problems  Understanding the Complexity of Induced Subgraph Isomorphisms  Spanners in Sparse Graphs  Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error  AllPairs Shortest Paths with a Sublinear Additive Error  Simpler LinearTime Modular Decomposition Via Recursive Factorizing Permutations  The Complexity of the Counting Constraint Satisfaction Problem  On the Hardness of Losing Weight  Product Theorems Via Semidefinite Programming  Sound 3Query PCPPs Are Long  Approximative Methods for Monotone Systems of MinMaxPolynomial Equations  Recursive Stochastic Games with Positive Rewards  Complementation, Disambiguation, and Determinization of Büchi Automata Unified  Tree Projections: Hypergraph Games and Minimality  Explicit Nonadaptive Combinatorial Group Testing Schemes  Tight Lower Bounds for Multipass Stream Computation Via Pass Elimination  Impossibility of a Quantum SpeedUp with a Faulty Oracle  Superpolynomial Speedups Based on Almost Any Quantum Circuit  The Speed of Convergence in Congestion Games under BestResponse Dynamics  Uniform Budgets and the EnvyFree Pricing Problem  Bayesian Combinatorial Auctions  Truthful Unification Framework for Packing Integer Programs with Choices  Upper Bounds on the Noise Threshold for FaultTolerant Quantum Computing  Finding Optimal Flows Efficiently  Optimal Quantum Adversary Lower Bounds for Ordered Search  Quantum SAT for a QutritCinquit Pair Is QMA 1Complete  Superpolynomial Speedups Based on Almost Any Quantum Circuit
 Control code
 272314715
 Dimensions
 unknown
 Extent
 1 online resource (896 pages).
 Form of item
 online
 Isbn
 9783540705741
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code

 c
 Other control number
 10.1007/9783540705758
 http://library.link/vocab/ext/overdrive/overdriveId
 9783540705741
 Specific material designation
 remote
 System control number
 (OCoLC)272314715
 Label
 Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)
 Bibliography note
 Includes bibliographical references
 Carrier category
 online resource
 Carrier category code

 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code

 txt
 Content type MARC source
 rdacontent
 Contents
 Invited Lectures  Graph Structure and Monadic SecondOrder Logic: Language Theoretical Aspects  Internet Ad Auctions: Insights and Directions  Track A: Algorithms, Automata, Complexity, and Games  The Complexity of Boolean Formula Minimization  Optimal Cryptographic Hardness of Learning Monotone Functions  On Berge Multiplication for Monotone Boolean Dualization  Diagonal Circuit Identity Testing and Lower Bounds  CellProbe Proofs and Nondeterministic CellProbe Complexity  Constructing Efficient Dictionaries in Close to Sorting Time  On List Update with Locality of Reference  A New Combinatorial Approach for Sparse Graph Problems  How to Explore a FastChanging World (Cover Time of a Simple Random Walk on Evolving Graphs)  Networks Become Navigable as Nodes Move and Forget  Fast Distributed Computation of Cuts Via Random Circulations  Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time  Function Evaluation Via Linear Programming in the Priced Information Model  Improved Approximation Algorithms for Budgeted Allocations  The Travelling Salesman Problem in Bounded Degree Graphs  Treewidth Computation and Extremal Combinatorics  Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines  Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2  A PTAS for Static Priority RealTime Scheduling with Resource Augmentation  Optimal Monotone Encodings  PolynomialTime Construction of Linear Network Coding  Complexity of Decoding PositiveRate ReedSolomon Codes  Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)  The Randomized Coloring Procedure with SymmetryBreaking  The Local Nature of List Colorings for Graphs of High Girth  Approximating ListColoring on a Fixed Surface  Asymptotically Optimal Hitting Sets Against Polynomials  The Smoothed Complexity of Edit Distance  Randomized Selfassembly for Approximate Shapes  Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)  Competitive Weighted Matching in Transversal Matroids  Scheduling for Speed Bounded Processors  Faster Algorithms for Incremental Topological Ordering  Dynamic Normal Forms and Dynamic Characteristic Polynomial  Algorithms for?Approximations of Terrains  An Approximation Algorithm for Binary Searching in Trees  Algorithms for 2Route Cut Problems  The TwoEdge Connectivity Survivable Network Problem in Planar Graphs  Efficiently Testing Sparse GF(2) Polynomials  Testing Properties of Sets of Points in Metric Spaces  An Expansion Tester for Bounded Degree Graphs  Property Testing on kVertexConnectivity of Graphs  Almost 2SAT Is FixedParameter Tractable (Extended Abstract)  On Problems without Polynomial Kernels (Extended Abstract)  Faster Algebraic Algorithms for Path and Packing Problems  Understanding the Complexity of Induced Subgraph Isomorphisms  Spanners in Sparse Graphs  Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error  AllPairs Shortest Paths with a Sublinear Additive Error  Simpler LinearTime Modular Decomposition Via Recursive Factorizing Permutations  The Complexity of the Counting Constraint Satisfaction Problem  On the Hardness of Losing Weight  Product Theorems Via Semidefinite Programming  Sound 3Query PCPPs Are Long  Approximative Methods for Monotone Systems of MinMaxPolynomial Equations  Recursive Stochastic Games with Positive Rewards  Complementation, Disambiguation, and Determinization of Büchi Automata Unified  Tree Projections: Hypergraph Games and Minimality  Explicit Nonadaptive Combinatorial Group Testing Schemes  Tight Lower Bounds for Multipass Stream Computation Via Pass Elimination  Impossibility of a Quantum SpeedUp with a Faulty Oracle  Superpolynomial Speedups Based on Almost Any Quantum Circuit  The Speed of Convergence in Congestion Games under BestResponse Dynamics  Uniform Budgets and the EnvyFree Pricing Problem  Bayesian Combinatorial Auctions  Truthful Unification Framework for Packing Integer Programs with Choices  Upper Bounds on the Noise Threshold for FaultTolerant Quantum Computing  Finding Optimal Flows Efficiently  Optimal Quantum Adversary Lower Bounds for Ordered Search  Quantum SAT for a QutritCinquit Pair Is QMA 1Complete  Superpolynomial Speedups Based on Almost Any Quantum Circuit
 Control code
 272314715
 Dimensions
 unknown
 Extent
 1 online resource (896 pages).
 Form of item
 online
 Isbn
 9783540705741
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code

 c
 Other control number
 10.1007/9783540705758
 http://library.link/vocab/ext/overdrive/overdriveId
 9783540705741
 Specific material designation
 remote
 System control number
 (OCoLC)272314715
Subject
 Computer programming
 Computer programming
 Computer programming
 Computer programming  Congresses
 Computer science
 Conference papers and proceedings
 Conference papers and proceedings
 Data Structures, Cryptology and Information Theory
 Data structures
 Discrete Mathematics in Computer Science
 Formal languages
 Formal languages
 Formal languages
 Formal languages  Congresses
 Informatique
 Machine theory
 Machine theory
 Machine theory
 Machine theory  Congresses
 Numeric Computing
 Software Engineering/Programming and Operating Systems
 Theory of Computation
Genre
Member of
Library Links
Embed
Settings
Select options that apply then copy and paste the RDF/HTML data fragment to include in your application
Embed this data in a secure (HTTPS) page:
Layout options:
Include data citation:
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.library.missouri.edu/portal/Automatalanguagesandprogramming35th/zOjGSq3ygoI/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.library.missouri.edu/portal/Automatalanguagesandprogramming35th/zOjGSq3ygoI/">Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.library.missouri.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.library.missouri.edu/">University of Missouri Libraries</a></span></span></span></span></div>
Note: Adjust the width and height settings defined in the RDF/HTML code fragment to best match your requirements
Preview
Cite Data  Experimental
Data Citation of the Item Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)
Copy and paste the following RDF/HTML data fragment to cite this resource
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.library.missouri.edu/portal/Automatalanguagesandprogramming35th/zOjGSq3ygoI/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.library.missouri.edu/portal/Automatalanguagesandprogramming35th/zOjGSq3ygoI/">Automata, languages and programming : 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 711, 2008 ; proceedings, Part I, Luca Aceto [and others] (eds.)</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.library.missouri.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.library.missouri.edu/">University of Missouri Libraries</a></span></span></span></span></div>