Mathematical Foundations of Computer Science 2009 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings / [electronic resource] :
edited by Rastislav Královič, Damian Niwiński.
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2009.
- XV, 760 p. online resource.
- Lecture Notes in Computer Science, 5734 0302-9743 ; .
- Lecture Notes in Computer Science, 5734 .
Invited Papers -- Four Subareas of the Theory of Constraints, and Their Links -- Synchronization of Regular Automata -- Stochastic Process Creation -- Stochastic Games with Finitary Objectives -- Stochastic Data Streams -- Recent Advances in Population Protocols -- How to Sort a Train -- Contributed Papers -- Arithmetic Circuits, Monomial Algebras and Finite Automata -- An Improved Approximation Bound for Spanning Star Forest and Color Saving -- Energy-Efficient Communication in Multi-interface Wireless Networks -- Private Capacities in Mechanism Design -- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules -- Sampling Edge Covers in 3-Regular Graphs -- Balanced Paths in Colored Graphs -- Few Product Gates But Many Zeros -- Branching Programs for Tree Evaluation -- A Dichotomy Theorem for Polynomial Evaluation -- DP-Complete Problems Derived from Extremal NP-Complete Properties -- The Synchronization Problem for Locally Strongly Transitive Automata -- Constructing Brambles -- Self-indexed Text Compression Using Straight-Line Programs -- Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants -- Parameterized Complexity Classes under Logical Reductions -- The Communication Complexity of Non-signaling Distributions -- How to Use Spanning Trees to Navigate in Graphs -- Representing Groups on Graphs -- Admissible Strategies in Infinite Games over Graphs -- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems -- Future-Looking Logics on Data Words and Trees -- A By-Level Analysis of Multiplicative Exponential Linear Logic -- Hyper-minimisation Made Efficient -- Regular Expressions with Counting: Weak versus Strong Determinism -- Choosability of P 5-Free Graphs -- Time-Bounded Kolmogorov Complexity and Solovay Functions -- The Longest Path Problem Is Polynomial on Interval Graphs -- Synthesis for Structure Rewriting Systems -- On the Hybrid Extension of CTL and CTL?+? -- Bounds on Non-surjective Cellular Automata -- FO Model Checking on Nested Pushdown Trees -- The Prismoid of Resources -- A Dynamic Algorithm for Reachability Games Played on Trees -- An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable -- Graph Decomposition for Improving Memoryless Periodic Exploration -- On FO 2 Quantifier Alternation over Words -- On the Recognizability of Self-generating Sets -- The Isomorphism Problem for k-Trees Is Complete for Logspace -- Snake-Deterministic Tiling Systems -- Query Automata for Nested Words -- A General Class of Models of -- The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I -- Colouring Non-sparse Random Intersection Graphs -- On the Structure of Optimal Greedy Computation (for Job Scheduling) -- A Probabilistic PTAS for Shortest Common Superstring -- The Cost of Stability in Network Flow Games -- (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata -- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm -- From Parity and Payoff Games to Linear Programming -- Partial Randomness and Dimension of Recursively Enumerable Reals -- Partial Solution and Entropy -- On Pebble Automata for Data Languages with Decidable Emptiness Problem -- Size and Energy of Threshold Circuits Computing Mod Functions -- Points on Computable Curves of Computable Lengths -- The Expressive Power of Binary Submodular Functions.
9783642038167
10.1007/978-3-642-03816-7 doi
Computer science.
Data structures (Computer science).
Computer software.
Logic design.
Computer Science.
Algorithm Analysis and Problem Complexity.
Computation by Abstract Devices.
Logics and Meanings of Programs.
Mathematical Logic and Formal Languages.
Mathematics of Computing.
Data Structures.
QA76.9.A43
005.1
Invited Papers -- Four Subareas of the Theory of Constraints, and Their Links -- Synchronization of Regular Automata -- Stochastic Process Creation -- Stochastic Games with Finitary Objectives -- Stochastic Data Streams -- Recent Advances in Population Protocols -- How to Sort a Train -- Contributed Papers -- Arithmetic Circuits, Monomial Algebras and Finite Automata -- An Improved Approximation Bound for Spanning Star Forest and Color Saving -- Energy-Efficient Communication in Multi-interface Wireless Networks -- Private Capacities in Mechanism Design -- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules -- Sampling Edge Covers in 3-Regular Graphs -- Balanced Paths in Colored Graphs -- Few Product Gates But Many Zeros -- Branching Programs for Tree Evaluation -- A Dichotomy Theorem for Polynomial Evaluation -- DP-Complete Problems Derived from Extremal NP-Complete Properties -- The Synchronization Problem for Locally Strongly Transitive Automata -- Constructing Brambles -- Self-indexed Text Compression Using Straight-Line Programs -- Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants -- Parameterized Complexity Classes under Logical Reductions -- The Communication Complexity of Non-signaling Distributions -- How to Use Spanning Trees to Navigate in Graphs -- Representing Groups on Graphs -- Admissible Strategies in Infinite Games over Graphs -- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems -- Future-Looking Logics on Data Words and Trees -- A By-Level Analysis of Multiplicative Exponential Linear Logic -- Hyper-minimisation Made Efficient -- Regular Expressions with Counting: Weak versus Strong Determinism -- Choosability of P 5-Free Graphs -- Time-Bounded Kolmogorov Complexity and Solovay Functions -- The Longest Path Problem Is Polynomial on Interval Graphs -- Synthesis for Structure Rewriting Systems -- On the Hybrid Extension of CTL and CTL?+? -- Bounds on Non-surjective Cellular Automata -- FO Model Checking on Nested Pushdown Trees -- The Prismoid of Resources -- A Dynamic Algorithm for Reachability Games Played on Trees -- An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable -- Graph Decomposition for Improving Memoryless Periodic Exploration -- On FO 2 Quantifier Alternation over Words -- On the Recognizability of Self-generating Sets -- The Isomorphism Problem for k-Trees Is Complete for Logspace -- Snake-Deterministic Tiling Systems -- Query Automata for Nested Words -- A General Class of Models of -- The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I -- Colouring Non-sparse Random Intersection Graphs -- On the Structure of Optimal Greedy Computation (for Job Scheduling) -- A Probabilistic PTAS for Shortest Common Superstring -- The Cost of Stability in Network Flow Games -- (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata -- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm -- From Parity and Payoff Games to Linear Programming -- Partial Randomness and Dimension of Recursively Enumerable Reals -- Partial Solution and Entropy -- On Pebble Automata for Data Languages with Decidable Emptiness Problem -- Size and Energy of Threshold Circuits Computing Mod Functions -- Points on Computable Curves of Computable Lengths -- The Expressive Power of Binary Submodular Functions.
9783642038167
10.1007/978-3-642-03816-7 doi
Computer science.
Data structures (Computer science).
Computer software.
Logic design.
Computer Science.
Algorithm Analysis and Problem Complexity.
Computation by Abstract Devices.
Logics and Meanings of Programs.
Mathematical Logic and Formal Languages.
Mathematics of Computing.
Data Structures.
QA76.9.A43
005.1