Fundamentals of Computation Theory

Name: Fundamentals of Computation Theory | 20th International Symposium, FCT 2015, Gdansk, Poland, August 17-19, 2015, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

20th International Symposium, FCT 2015, Gdansk, Poland, August 17-19, 2015, Proceedings

Adrian Kosowski Igor Walukiewicz(Herausgeber*in)

Springer (Verlag)

Erschienen am 3. August 2015

XIX, 395 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-22177-9 (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

Intro
Preface
Conference Organization
Invited Talks
It is Better to be Vaguely Right Than Exactly Wrong
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS
Contents
Invited talks
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
1 Introduction
2 Underlying Idea
3 TSP and Related Problems
4 Bounded Occurrence Optimization Problems
5 Bi-wheel Amplifier Graphs
6 Preparation Lemma
7 Instances of Metric TSP
8 Instances of Asymmetric TSP (ATSP)
9 A Role of Weights
10 Graphic TSP
11 Some Applications
12 Summary of Main Results
13 Further Research
References
On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS
1 Introduction
2 Preliminaries
2.1 Probabilistic Vector Addition Systems with States
2.2 Patterns and Pattern Frequencies
3 Pattern Frequency in One-Counter pVASS
3.1 Approximating [pq] and [p]
3.2 Approximating E Rs and E#t rs
4 Pattern Frequency in Two-Counter pVASS
5 Future Research
References
Geometry, Combinatorics, Text Algorithms
Longest -Gapped Repeat and Palindrome
1 Introduction
2 Preliminaries
3 Our Solution
References
On the Enumeration of Permutominoes
1 Introduction
2 Preliminaries
3 The Inflate-Paste Technique
4 Direct Enumeration of Permutominoes
5 Tailoring the Algorithm to Specific Subclasses
5.1 Convex Permutominoes
5.2 Row-Convex Permutominoes
6 Conclusion
References
Stabbing Segments with Rectilinear Objects
1 Introduction
2 Stabbing with One or Two Halfplanes
2.1 Stabbing Halfplane
2.2 Stabbing Strips
2.3 Stabbing Quadrants
3 Stabbing with Three Halfplanes
3.1 Number of Different Stabbing 3-Rectangles
3.2 Algorithm
4 Stabbing Rectangles
References
ß-skeletons for a Set of Line Segments in R2
1 Introduction
2 Preliminaries
3 Algorithm for Computing ß-skeletons for 0 & ß & 1
4 Finding ß-skeletons for 1 = ß
5 Computing Gabriel Graph for Segments
6 Conclusions
References
Complexity and Boolean Functions
Depth, Highness and DNR Degrees
1 Introduction
2 Preliminaries
3 C-Depth
3.1 MLR is not Order-deepC
3.2 The SGL Fails for C-depth
3.3 Depth Implies Highness or DNR
4 K-Depth
4.1 Highness and Depth Coincide
4.2 Depth Implies Highness or DNR
4.3 A Low Deep Set
4.4 No K-Trivial is O(1)-deepK
5 Infinitely Often Depth and Conditional Depth
6 Conclusion
References
On the Expressive Power of Read-Once Determinants
1 Introduction
2 Basic Observations
3 Elementary Symmetric Polynomials and Permanent
3.1 Elementary Symmetric Polynomials
3.2 Non-expressibility of Permanent as ROD
4 Non-expressible Monomial Sets
5 Discussion and Open Problems
References
Constructive Relationships Between Algebraic Thickness and Normality
1 Introduction and Known Results
2 Preliminaries and Known Results
3 Majority Has High Algebraic Thickness
4 Algebraic Thickness and Normality
4.1 Normal Functions with Low Sparsity
References
On the Structure of Solution-Graphs for Boolean Formulas
1 Introduction
2 Preliminaries
3 Structure of CPSS-Formulas
4 Structure of General Schaefer-Formulas
5 Improved Algorithms for Connectivity and st-connectivity
6 Conclusions and Open Problems
References
Languages
Interprocedural Reachability for Flat Integer Programs
1 Introduction
2 Preliminaries
3 Interprocedural Flat Octogonal Reachability
4 Index-Bounded Depth-First Derivations
5 A Decision Procedure for REACHfo(P,b)
6 Related Work
References
Complexity of Suffix-Free Regular Languages
1 Introduction
2 Suffix-Free Transformations
3 Witnesses with Transition Semigroups in T5(n)
4 Witnesses with Semigroups in T6(n)
5 Conclusions
References
Alternation Hierarchies of First Order Logic with Regular Predicates
1 Introduction
2 Preliminaries
3 Main Results
4 The Delay Question
5 The Infinitely Testable Property
References
A Note on Decidable Separability by Piecewise Testable Languages
1 Introduction
2 Preliminaries
3 Common Patterns
4 The Algorithm for Separability
5 Decidable Classes
6 Concluding Remarks
References
Set Algorithms, Covering, and Traversal
Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations
1 Introduction
1.1 Definition of the Problem
1.2 Application and Related Work
1.3 Parameterizations
1.4 Our Results
2 First Remarks and Kernels
3 Parameterizing According to ?B
4 Parameterizing According to ?p
4.1 Positive Result for n=2
4.2 Negative Results for n = 3
5 Conclusion
References
Incremental Complexity of a Bi-objective Hypergraph Transversal Problem
1 Introduction
2 The Bi-objective Transversal Problem
2.1 The Problem
2.2 Another Enumeration Problem
3 Situations in Which the Problems Remain Hard
3.1 Bounded Degree
3.2 B of Bounded Dimension
4 Bounding the Dimension of A
References
Pairs Covered by a Sequence of Sets
1 Introduction
1.1 Motivation and Aim
1.2 Overview of Contributions
2 Finding Minimal New Sets
2.1 Transversals for Small Complementary Degree
2.2 Enumerating the Minimal New Sets in a Sequence
3 A Heuristic for Minimal New Pairs
3.1 Below the Worst-Case Quadratic Time
3.2 The Twin Graph
3.3 Greedy Partial Set Cover of Pairs
4 Supplementary Results
4.1 Sampling Large Intersections
4.2 Building Larger Bags
5 Approximations if a Few Bags Cover All Pairs
5.1 Setup and Preparations
5.2 Illustration: Some Approximation Guarantees
References
Recurring Comparison Faults: Sorting and Finding the Minimum
1 Introduction
2 Sorting
2.1 Compatible Solutions
2.2 Score Solutions
2.3 Quality of Compatible Solutions and Score Solutions
3 Finding a Minimum Element
4 Conclusion
References
Graph Algorithms and Networking Applications
Minimal Disconnected Cuts in Planar Graphs
1 Introduction
2 The Algorithm
3 Hardness
4 Conclusions
References
E -Almost Selectors and Their Applications
1 The Communication Model
2 Combinatorial Tools
3 Hypergraphs and Covers
4 Constructing -almost (k,m, n)-Selectors via Partial Coverings
4.1 Improvements
References
Derandomized Construction of Combinatorial Batch Codes
1 Introduction
1.1 Background
2 Proof of Theorem 2
3 Concluding Remarks
References
On the Mathematics of Data Centre Network Topologies
1 Introduction
2 Basic Concepts
3 The 3-Step Construction and Its Extensions
4 Constructions of Paths
5 Conclusion
References
Anonymity and Indistinguishability
Privacy in Elections: k-Anonymizing Preference Orders
1 Introduction
1.1 Related Work
2 Preliminaries
2.1 Elections and Distances
2.2 Anonymization
2.3 Parameterized Complexity
2.4 Main Problem and Overview of Our Results
3 Results
4 Conclusion
References
On Equivalences, Metrics, and Polynomial Time
1 Introduction
2 Characterizing Probabilistic Polynomial Time
3 Equivalences
3.1 Trace Equivalence
3.2 Some Words on Applicative Bisimulation
4 From Equivalences to Metrics
5 Computational Indistinguishability
5.1 Higher-Order Computational Indistinguishability?
6 Conclusions
References
Graphs, Automata, and Dynamics
Conjunctive Visibly-Pushdown Path Queries
1 Introduction
2 Preliminaries
3 The Complexity of Evaluating CPQ[VPL] Queries
4 The Complexity of Evaluating ECPQ[VPL] Queries
5 Query Containment
References
On the Power of Color Refinement
1 Introduction
2 Basic Definitions and Facts
3 Local Structure of Amenable Graphs
4 Global Structure of Amenable Graphs
5 Examples and Applications
References
Block Representation of Reversible Causal Graph Dynamics
1 Introduction
2 Pointed Graph Modulo, Paths, and Operations
3 Reversible Causal Graph Dynamics
4 Locality
5 Block Representation
6 Conclusion
References
Logic and Games
Reasoning with Global Assumptions in Arithmetic Modal Logics
1 Coalgebraic Logic
1.1 Presburger Modal Logic
1.2 Probabilistic Modal Logic with Polynomial Inequalities
2 One-Step Satisfiability
3 Type Elimination
4 Global Caching
5 Conclusions
References
Nearest Fixed Points and Concurrent Priority Games
1 Introduction
2 Concurrent Stochastic Priority Games
3 Interval Lattice and Nearest Fixed Point
3.1 Nested Nearest Fixed Points
4 Value of the Concurrent Priority Game as the Nested Nearest Fixed Point
4.1 Auxiliary One-Shot Game
4.2 Priority Games with One Non-absorbing State
4.3 General Priority Games
5 Algorithmic Issues
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken