Fundamentals of Computation Theory: 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings

Front Matter....Pages I-XIX
Front Matter....Pages 1-1
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies....Pages 3-11
On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS....Pages 12-24
Front Matter....Pages 25-25
On the Enumeration of Permutominoes....Pages 27-40
Stabbing Segments with Rectilinear Objects....Pages 41-52
Front Matter....Pages 53-64
Depth, Highness and DNR Degrees....Pages 65-78
On the Expressive Power of Read-Once Determinants....Pages 79-79
Constructive Relationships Between Algebraic Thickness and Normality....Pages 81-94
On the Structure of Solution-Graphs for Boolean Formulas....Pages 95-105
Front Matter....Pages 106-117
Interprocedural Reachability for Flat Integer Programs....Pages 118-130
Complexity of Suffix-Free Regular Languages....Pages 131-131
Alternation Hierarchies of First Order Logic with Regular Predicates....Pages 133-145
A Note on Decidable Separability by Piecewise Testable Languages....Pages 146-159
Front Matter....Pages 160-172
Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations....Pages 173-185
Incremental Complexity of a Bi-objective Hypergraph Transversal Problem....Pages 187-187
Pairs Covered by a Sequence of Sets....Pages 189-201
Recurring Comparison Faults: Sorting and Finding the Minimum....Pages 202-213
Front Matter....Pages 214-226
Minimal Disconnected Cuts in Planar Graphs....Pages 227-239
Front Matter....Pages 241-241
Derandomized Construction of Combinatorial Batch Codes....Pages 243-254
On the Mathematics of Data Centre Network Topologies....Pages 255-268
Front Matter....Pages 241-241
Privacy in Elections: k-Anonymizing Preference Orders....Pages 269-282
On Equivalences, Metrics, and Polynomial Time....Pages 283-295
Front Matter....Pages 297-297
Conjunctive Visibly-Pushdown Path Queries....Pages 299-310
On the Power of Color Refinement....Pages 311-323
Block Representation of Reversible Causal Graph Dynamics....Pages 325-325
Front Matter....Pages 327-338
Reasoning with Global Assumptions in Arithmetic Modal Logics....Pages 339-350
Nearest Fixed Points and Concurrent Priority Games....Pages 351-363
Back Matter....Pages 365-365
....Pages 367-380