Fundamentals of Computation Theory: 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings (Lecture Notes in Computer Science Book 9210)

This book constitutes the refereed proceedings of the 20th International Symposium on Fundamentals of Computation Theory, FCT 2015, held in Gdańsk, Poland, in August 2015. The 27 revised full papers presented were carefully reviewed and selected from 60 submissions. The papers cover topics in three main areas: algorithms, formal methods, and emerging fields and are organized in topical sections on geometry, combinatorics, text algorithms; complexity and Boolean functions; languages; set algorithms, covering, and traversal; graph algorithms and networking applications; anonymity and indistinguishability; graphs, automata, and dynamics; and logic and games. 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 This book constitutes the refereed proceedings of the 20th International Symposium on Fundamentals of Computation Theory, FCT 2015, held in Gda¿lsk, Poland, in August 2015. The 27 revised full papers presented were carefully reviewed and selected from 60 submissions. The papers cover topics in three main areas: algorithms, formal methods, and emerging fields and are organized in topical sections on geometry, combinatorics, text algorithms; complexity and Boolean functions; languages; set algorithms, covering, and traversal; graph algorithms and networking applications; anonymity and indistinguishability; graphs, automata, and dynamics; and logic and games This book constitutes the refereed proceedings of the 20th International Symposium on Fundamentals of Computation Theory, FCT 2015, held in Gdansk, Poland, in August 2015. The papers cover topics in three main areas: algorithms, formal methods, and emerging fields and are organized in topical sections on geometry, combinatorics, text algorithms;