Normal view MARC view ISBD view

Mathematical Foundations of Computer Science 2010 [electronic resource] : 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010, Proceedings / edited by Petr Hlineny, Antonin Kucera.

Contributor(s): Hlineny, Petr [editor.] | Kucera, Antonin [editor.] | SpringerLink (Online service).
Material type: materialTypeLabelBookSeries: Theoretical Computer Science and General Issues: 6281Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010Edition: 1st ed. 2010.Description: XVII, 714 p. 71 illus. online resource.Content type: text Media type: computer Carrier type: online resourceISBN: 9783642151552.Subject(s): Computer programming | Compilers (Computer programs) | Computer science | Algorithms | Computer science -- Mathematics | Discrete mathematics | Programming Techniques | Compilers and Interpreters | Theory of Computation | Algorithms | Discrete Mathematics in Computer ScienceAdditional physical formats: Printed edition:: No title; Printed edition:: No titleDDC classification: 005.11 Online resources: Click here to access online
Contents:
New Developments in Quantum Algorithms -- Persistent Homology under Non-uniform Error -- Information Complexity of Online Problems -- Algorithmic Lower Bounds for Problems on Decomposable Graphs -- Do We Really Understand the Crossing Numbers? -- Balanced Queries: Divide and Conquer -- Slowly Synchronizing Automata and Digraphs -- Weights of Exact Threshold Functions -- Proof Systems and Transformation Games -- Scheduling Real-Time Mixed-Criticality Jobs -- A dexptime-Complete Dolev-Yao Theory with Distributive Encryption -- On Problem Kernels for Possible Winner Determination under the k-Approval Protocol -- Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time -- Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree -- Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems -- Distance Constraint Satisfaction Problems -- Faster Algorithms on Branch and Clique Decompositions -- Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks -- Robust Computations with Dynamical Systems -- On Factor Universality in Symbolic Spaces -- Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity -- Resource Combinatory Algebras -- Randomness for Free -- Qualitative Analysis of Partially-Observable Markov Decision Processes -- All Symmetric Predicates in NSPACE(n 2) Are Stably Computable by the Mediated Population Protocol Model -- Online Clustering with Variable Sized Clusters -- Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains -- Counting Classes and the Fine Structure between NC 1 and L -- The Average Complexity of Moore's State Minimization Algorithm Is O( n loglogn) -- Connected Searching of Weighted Trees -- Iterated Regret Minimization inGame Graphs -- Properties of Visibly Pushdown Transducers -- Second-Order Algebraic Theories -- Frame Definability for Classes of Trees in the ?-calculus -- Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model -- Finding and Counting Vertex-Colored Subtrees -- Limiting Negations in Bounded Treewidth and Upward Planar Circuits -- On the Topological Complexity of MSO+U and Related Automata Models -- Least and Greatest Solutions of Equations over Sets of Integers -- Improved Simulation of Nondeterministic Turing Machines -- The Prize-Collecting Edge Dominating Set Problem in Trees -- The Multivariate Resultant Is NP-hard in Any Characteristic -- Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems -- Meta-Envy-Free Cake-Cutting Protocols -- Two Variables and Two Successors -- Harnessing ML F with the Power of System F -- Describing Average- and Longtime-Behavior by Weighted MSO Logics -- Solving minones-2-sat as Fast as vertex cover -- Unambiguous Finite Automata over a Unary Alphabet -- The Complexity of Finding Reset Words in Finite Automata -- Does Treewidth Help in Modal Satisfiability? -- Asynchronous Omega-Regular Games with Partial Information -- Parity Games with Partial Information Played on Graphs of Bounded Complexity -- Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets -- Enumeration of the Monomials of a Polynomial and Related Complexity Classes -- Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs -- Semi-linear Parikh Images of Regular Expressions via Reduction -- Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds -- Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences -- Counting Dependent and IndependentStrings -- Impossibility of Independence Amplification in Kolmogorov Complexity Theory.
In: Springer Nature eBook
    average rating: 0.0 (0 votes)
No physical items for this record

New Developments in Quantum Algorithms -- Persistent Homology under Non-uniform Error -- Information Complexity of Online Problems -- Algorithmic Lower Bounds for Problems on Decomposable Graphs -- Do We Really Understand the Crossing Numbers? -- Balanced Queries: Divide and Conquer -- Slowly Synchronizing Automata and Digraphs -- Weights of Exact Threshold Functions -- Proof Systems and Transformation Games -- Scheduling Real-Time Mixed-Criticality Jobs -- A dexptime-Complete Dolev-Yao Theory with Distributive Encryption -- On Problem Kernels for Possible Winner Determination under the k-Approval Protocol -- Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time -- Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree -- Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems -- Distance Constraint Satisfaction Problems -- Faster Algorithms on Branch and Clique Decompositions -- Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks -- Robust Computations with Dynamical Systems -- On Factor Universality in Symbolic Spaces -- Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity -- Resource Combinatory Algebras -- Randomness for Free -- Qualitative Analysis of Partially-Observable Markov Decision Processes -- All Symmetric Predicates in NSPACE(n 2) Are Stably Computable by the Mediated Population Protocol Model -- Online Clustering with Variable Sized Clusters -- Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains -- Counting Classes and the Fine Structure between NC 1 and L -- The Average Complexity of Moore's State Minimization Algorithm Is O( n loglogn) -- Connected Searching of Weighted Trees -- Iterated Regret Minimization inGame Graphs -- Properties of Visibly Pushdown Transducers -- Second-Order Algebraic Theories -- Frame Definability for Classes of Trees in the ?-calculus -- Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model -- Finding and Counting Vertex-Colored Subtrees -- Limiting Negations in Bounded Treewidth and Upward Planar Circuits -- On the Topological Complexity of MSO+U and Related Automata Models -- Least and Greatest Solutions of Equations over Sets of Integers -- Improved Simulation of Nondeterministic Turing Machines -- The Prize-Collecting Edge Dominating Set Problem in Trees -- The Multivariate Resultant Is NP-hard in Any Characteristic -- Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems -- Meta-Envy-Free Cake-Cutting Protocols -- Two Variables and Two Successors -- Harnessing ML F with the Power of System F -- Describing Average- and Longtime-Behavior by Weighted MSO Logics -- Solving minones-2-sat as Fast as vertex cover -- Unambiguous Finite Automata over a Unary Alphabet -- The Complexity of Finding Reset Words in Finite Automata -- Does Treewidth Help in Modal Satisfiability? -- Asynchronous Omega-Regular Games with Partial Information -- Parity Games with Partial Information Played on Graphs of Bounded Complexity -- Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets -- Enumeration of the Monomials of a Polynomial and Related Complexity Classes -- Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs -- Semi-linear Parikh Images of Regular Expressions via Reduction -- Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds -- Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences -- Counting Dependent and IndependentStrings -- Impossibility of Independence Amplification in Kolmogorov Complexity Theory.

There are no comments for this item.

Log in to your account to post a comment.