Mathematical Foundations of Computer Science 2011

Name: Mathematical Foundations of Computer Science 2011 | 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011, Proceedings

Filip Murlak Piotr Sankowski(Herausgeber*in)

Springer (Verlag)

Erschienen am 9. August 2011

XV, 618 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22993-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken