Mathematical Foundations of Computer Science 2011
36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011, Proceedings
Published on 9. August 2011
XV, 618 pages
978-3-642-22993-0 (ISBN)
Description
This volume constitutes the refereed proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, held in Warsaw, Poland, in August 2011. The 48 revised full papers presented together with 6 invited talks were carefully reviewed and selected from 129 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, grammars and formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, cryptography and security, databases and knowledge-based systems, formal specifications and program development, foundations of computing, logic in computer science, mobile computing, models of computation, networks, parallel and distributed computing, quantum computing, semantics and verification of programs, and theoretical issues in artificial intelligence.
More details
Other editions
Additional editions
Filip Murlak | Piotr Sankowski
Mathematical Foundations of Computer Science 2011
36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011, Proceedings
Book
08/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Contents
- Invited Papers
- Nearest Neighbor Search in High-Dimensional Spaces
- Invariantization of Listings
- Duality and Recognition
- Stone Duality
- Duality for Finite Distributive Lattices
- Duality for Bounded Distributive lattices
- Duality for Additional Operations
- Monoids and Recognition by Automata
- Recognisable Subsets of an Algebra and Profinite Completions
- Eilenberg-Reiterman: Sub vs. Quotient Duality
- References
- Some Variants of the Star Height Problem
- Introduction
- Preliminaries
- Notations, Rational Expressions, and Automata
- Distance Desert Automata
- Variants of the Star Height Problem
- The Proof of Theorem 3
- Limitedness and Substitutions
- On the Existence of a Solution
- String Expressions
- The Td,h(P,R)-Hierarchy
- The Collapse of the Td,h(P,R)-Hierarchy
- A Reduction to Limitedness
- References
- Generic Techniques to Round SDP Relaxations
- New Proofs in Graph Minors
- Contributed Papers
- The Least-Core of Threshold Network Flow Games
- Introduction
- Preliminaries
- The Least-Core in TNFGs
- Related Work and Conclusions
- References
- Adhesivity Is Not Enough: Local Church-Rosser Revisited
- Background
- DPO Rewriting
- Rewriting in Adhesive Categories and Local Confluence
- Quasi-adhesivity
- Church-Rosser for Left-Linear Rules
- Adhesive Case
- Quasi-adhesive Case
- Graph Rewriting for the Concurrent Semantics of
- Conclusions
- References
- Quantitative Refinement for Weighted Modal Transition Systems
- Introduction
- Weighted Modal Transition Systems
- Thorough and Modal Refinement Distances
- Relaxation
- Limitations of the Quantitative Approach
- Structural Composition and Quotient
- Conclusion and Further Work
- References
- Faster Coupon Collecting via Replication with Applications in Gossiping
- Introduction
- Previous Results
- Model and Our Results
- Relationship to Gossiping
- The Oblivious Model
- Upper Bound
- Lower Bound
- The Clairvoyant Model
- The Adaptive Model
- Number of Necessary Copies
- References
- Verifying Proofs in Constant Depth
- Introduction
- Definitions
- Languages with NC0 Proof Systems
- Lower Bounds
- Lower Bounds on Depth
- List Enumerations
- Proof Systems for Regular Languages
- Conclusion
- References
- The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
- Introduction
- Previous Results
- Our Results
- The Cover Polynomials
- Matching Polynomials
- Horizontal Reductions
- A Horizontal Reduction for Cfac
- A New Horizontal Reduction for Cgeo
- Proof of Thm. 1
- A Previous Approach
- Reducing Match to C(0,y)
- Proof of Thm. 2
- Positive Results
- References
- Model Checking Coverability Graphs of Vector Addition Systems
- Introduction
- Coverability Graphs
- CTL Logics for Coverability Graphs
- An Extension of CTL
- VAS Model Checking
- Eventually Increasing Formulæ
- The PrECTL(F) Fragment
- Small Model Properties
- Related Work
- References
- Hard Functions for Low-Degree Polynomials over Prime Fields
- Introduction
- Preliminaries
- Gowers Test
- Hardness Amplification
- Hardness of MODm
- References
- Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
- Introduction
- Graphs, Nested Traces, and Trees
- Temporal Logic
- Satisfiability: From Trees to Nested Traces
- Model Checking
- References
- The Reachability Problem for Vector Addition System with One Zero-Test
- Introduction
- Preliminaries
- Vector Addition Systems with One Zero-Test
- Transition Systems
- Vector Addition Systems
- Proof Structure
- Polytope, Lambert and Petri Sets
- Important Results from Leroux
- Production Relations
- Well-Orderings of Production Relations
- Polytopie of the Production Relation
- Decidability of Reachability
- References
- The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity
- Introduction
- Related Work
- Preliminaries
- Bounded Search Tree Algorithm
- Smoothed Analysis
- Pertubation of Closest String Instances
- Good Columns and Simple Instances
- Smoothed Height of the Bounded Search Tree
- References
- Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains
- Introduction
- Related Work and Discussions
- Computable Analysis
- Main Result
- Necessary Condition: Poly-boundedness
- Sufficient Condition: Our Main Result
- Extension
- On Analytic Functions
- From the Function to the Taylor Series
- From the Taylor Series to the Function
- Proof of Main Result
- The Special Case of Integration
- On Lipschitz Constants
- Proof of Theorem 3
- Conclusion
- References
- Pattern-Guided Data Anonymization and Clustering
- Introduction
- Preliminaries and Basic Model
- Intractability Results
- TractableCases
- Conclusion
- References
- Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete
- Introduction
- Definitions
- NL -Completeness of Equivalence of ROCA
- Polynomially Long Distinguishing Witnesses Suffice
- The Underlying DFA and Incompatible Configurations
- Partitioning the 3D Space into Initial Space, Belt Space and Background Space
- Bounding the Minimal Witness
- Regularity is NL -Complete
- Conclusion
- References
- Energy and Mean-Payoff Parity Markov Decision Processes
- Introduction
- Definitions
- MDPs with Energy Parity Objectives
- MDPs with Mean-Payoff Parity Objectives
- References
- The Role of Polymorphism in the Characterisation of Complexity by Soft Types
- Introduction
- Presentation of Systems
- Presentation of the Problem
- Undecidability of Type Related Problems with Polymorphism
- Characterisation of Complexity in Monomorphic Systems
- Final Remarks
- References
- An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
- Introduction
- Valued Constraint Satisfaction Problems
- Weighted Relational Clones
- Weighted Clones
- Proof of Theorems 3 and 4
- Conclusions
- References
- On the Use of Guards for Logics with Data
- Introduction
- Data Monoids
- Rigidly Guarded Logics
- From the Logic to Data Monoids
- From Data Monoids to the Logic
- Logics for Finite Memory Automata
- Conclusion and Future Work
- References
- An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- Introduction
- General Setting
- Known Lower Bounds
- A 3n-o(n) Lower Bound
- Further Directions
- References
- On the Complexity of the l-diversity Problem
- Introduction
- Preliminary Definitions
- Approximation Complexity
- Inapproximability of l-diversity and Tuple Minimization
- APX-Hardness of l-diversity with l=4 and m=3
- An Approximation Algorithm for Bounded |s|
- Parameterized Complexity of l-diversity
- W[1]-Hardness of l-diversity
- Bounding |max| and m
- References
- Infinite Synchronizing Words for Probabilistic Automata
- Introduction
- Automata and Synchronizing Words
- The Emptiness Problem is PSPACE-Complete
- The Universality Problem is PSPACE-Complete
- Discussion
- References
- Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
- Introduction
- Preliminaries and Groundwork
- The Beauty of Trees
- Monadic Second Order Logics
- The Logic EF and EF-Bisimulation
- The Topological Complexity of Tree Languages
- Main Result
- Eliminating Recursion from -Formulae on Transitive Structures
- References
- Parity Games on Graphs with Medium Tree-Width
- Introduction
- Parity Games
- McNaughton's Algorithm for Parity Games
- Tree Width
- Our Algorithm
- Computing the Tree Decomposition
- References
- Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidable
- Introduction
- Main Theorem
- Algorithm
- Degree of a Continuous Function
- Zeros of Analytic Functions
- Degree and Robustness
- Proof of the Main Theorem
- Possible Generalizations
- Conclusion
- References
- On Minimising Automata with Errors
- Introduction
- Preliminaries
- Efficient k-minimisation
- k-similarity and k-minimisation
- Distance Forests
- Finite Languages and Partial Transition Functions
- Hyper-equivalence and Hyper-minimisation
- Error-Bounded k-minimisation
- References
- Contracting a Chordal Graph to a Split Graph or a Tree
- Introduction
- Preliminaries
- Contracting to Split Graphs
- Contracting to Trees
- Induced Minors and Extensions of Subgraphs
- References
- Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
- Introduction
- Monoids and Varieties
- Completely Positive Maps
- Automata Models
- Linear Inequalities
- Construction of DH-PRA and MM-QFA for R1 Languages
- ``Forbidden Constructions
- Conclusion
- References
- A Universally Defined Undecidable Unimodal Logic
- Introduction
- Preliminaries
- Main Result
- Relation with Previous Work
- Proof of the Main Result
- Global Satisfiability in the Grid Model
- Expressing the Grid: Universal First-Order Aspects
- Properties of Abstracted Frames
- Expressing the Grid: Modal Aspects
- coRE-hardness of Global Satisfiability
- Removing Globalness
- Conclusion
- References
- On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
- Introduction
- Preliminaries
- Hardness of Min-TCO When the Number of Users Interested in a Common Topic Is a Constant
- Hardness of Min-TCO When the Number of Connections of a User Is Constant
- A Polynomial-Time Algorithm for Min-TCO with Bounded Number of Topics
- Conclusion
- References
- Can Everybody Sit Closer to Their Friends Than Their Enemies?
- Introduction
- Problem Statement
- Graphs without Valid Drawing
- Drawing Signed Graphs in the Line
- Related Work
- Open Problems
- References
- Submodularity on a Tree: Unifying L -Convex and Bisubmodular Functions
- Introduction
- Related Work
- Steepest Descent Algorithm
- L-Convex Case
- General Case
- Translation Submodularity
- Weakly Tree-Submodular Functions
- Conclusions and Discussion
- References
- Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions
- Introduction
- Definitions and Preliminaries
- Equivalence with Errors
- A Randomness-Efficient Streaming Algorithm for Hamming Distance
- Accepting Dyck2 with Errors
- Lower Bound
- References
- Size and Computation of Injective Tree Automatic Presentations
- Introduction
- Preliminaries
- Trees
- Tree Automata
- An Upper Bound
- Shadow
- Final Steps
- Application to Tree Automatic Structures
- A Lower Bound
- State Complexity of Complementation Revisited
- A Tree Automatic Structure
- Transfer to Word Automatic Structures
- References
- Symmetric Functions Capture General Functions
- Introduction
- Symmetric Functions-Hard or Easy?
- Our Results and Techniques
- Preliminaries
- Results for the Elementary Symmetrization
- The Basic Idea
- Proof of Theorem 4
- Results for the Second Symmetrization
- Functions over Finite Fields
- Functions over Reals
- References
- CompressedWord Problems for Inverse Monoids
- Introduction
- Preliminaries
- Inverse Monoids
- Straight-Line Programs
- Compressed Word Problem for FIM()
- Compressed Word Problems for FIM()/P
- Rational Subset Membership Problems
- References
- Pushing for Weighted Tree Automata
- Introduction
- Preliminaries
- Efficient Computation of Signs of Life
- Pushing
- Minimization
- Testing Equivalence
- References
- Periodicity Algorithms for Partial Words
- Introduction
- Testing the Periodicity of Partial Words
- From Full Words to Periodic Partial Words
- Solution of Problem 3
- The Main Problem
- References
- State Complexity of Operations on Input-Driven Pushdown Automata
- Introduction
- Definitions
- Reversal
- Concatenation
- Kleene Star
- Conclusion
- References
- Conflict Packing Yields Linear Vertex-Kernels for k-FAST, k-dense RTI and a Related Problem
- Introduction
- Linear Vertex-Kernel for k-FAST
- Linear Vertex-Kernel for k-dense RTI
- Linear Vertex-Kernel for k-BIT
- References
- Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence
- Introduction
- Avalanches and Transducer
- Previous Results about Avalanches
- Successive Avalanches
- Transducer
- From Words to Waves
- Conclusion
- References
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Introduction
- Preliminaries and Notation
- Notation
- Treewidth and Pathwidth
- The Model of Logic
- The Inner Logic
- The Outer Logic
- Tractability of Problems Expressible in ECML
- Adding Connectivity Requirements
- The Necessity of Acyclicity
- Conclusions and Open Problems
- References
- Distributed Synthesis for Regular and Contextfree Specifications
- Introduction
- Preliminaries
- Global Specifications
- Local Specifications
- Decidability
- Undecidability
- Characterization
- References
- Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
- Introduction
- Background
- Related Work
- Our Contribution
- The Article Organisation
- Preliminaries
- Definitions of the Models
- Greedy Routing Protocol
- Geographic Routing in Gr(n,p)
- Geographic Routing in Gr(n,m,d)
- Concluding Remarks
- References
- Untimed Language Preservation in Timed Systems
- Introduction
- Preliminaries
- Timed Automata
- Restrictions on Timed Automata
- Robustness
- Main Result
- Properties of the Semantics under Enlargement
- Some Combinatorial Tools
- A Ramsey-Like Theorem for Directed Paths
- Ultimately Universal Languages
- Proof of the Theorem
- References
- Lower Bounds for Linear Decision Trees via an Energy Complexity Argument
- Introduction
- Definitions
- Linear Decision Trees
- Threshold Circuits
- Communication Complexity
- Lower Bounds for Linear Decision Trees
- Proof of Lemma 4
- Lower Bounds for Threshold Circuits of Depth (1)
- Conclusion
- References
- Weak Cost Monadic Logic over Infinite Trees
- Introduction
- Motivation
- Contributions
- Organisation
- Cost Monadic Logic
- Trees
- Cost Monadic Logic
- Cost Functions
- Cost Games
- Objectives
- Cost Games
- Cost Automata
- Weak Cost Automata
- Weak Cost Automata
- Closure Properties
- Equivalence with Logic
- Shape of Strategies
- Results
- Conclusion
- References
- Linear Problem Kernels for Planar Graph Problems with Small Distance Property
- Introduction
- A Simple Vertex Partition for Analysis of Kernels
- Connected Vertex Cover
- Edge Dominating Set
- Maximum Triangle Packing
- Conclusion
- References
- New Parameterized Algorithms for the Edge Dominating Set Problem
- Introduction
- Enumeration-Based Algorithms
- Branching Rules
- A Simple Algorithm
- Analysis
- An Improvement
- Analysis of Algorithm EDS1
- Kernelization
- References
- Author Index
