Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings (Lecture Notes in Computer Science Book 10185)

This book constitutes the refereed proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, held in Bern, Switzerland, in April 2017. The 45 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 103 submissions. The main themes of TAMC 2017 have been computability, computer science logic, complexity, algorithms, and models of computation and systems theory. Front Matter....Pages I-XXVI Front Matter....Pages 1-1 Cognitive Reasoning and Trust in Human-Robot Interactions....Pages 3-11 On Choice Rules in Dependent Type Theory....Pages 12-23 Natural Language Processing, Moving from Rules to Data....Pages 24-38 An All-or-Nothing Flavor to the Church-Turing Hypothesis....Pages 39-56 Front Matter....Pages 57-57 Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis....Pages 59-70 Multi-interval Pairwise Compatibility Graphs....Pages 71-84 A Note on Effective Categoricity for Linear Orderings....Pages 85-96 On the Shortest Common Superstring of NGS Reads....Pages 97-111 On the Cost of Simulating a Parallel Boolean Automata Network by a Block-Sequential One....Pages 112-128 On Resource-Bounded Versions of the van Lambalgen Theorem....Pages 129-143 Scheduling Fully Parallel Jobs with Integer Parallel Units....Pages 144-157 Continuous Firefighting on Infinite Square Grids....Pages 158-171 Mediated Population Protocols: Leader Election and Applications....Pages 172-186 Parikh Images of Matrix Ins-Del Systems....Pages 187-200 Algorithmic Aspects of the Maximum Colorful Arborescence Problem....Pages 201-215 Incompleteness Theorems, Large Cardinals, and Automata over Finite Words....Pages 216-230 Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity....Pages 231-246 The Strength of the SCT Criterion....Pages 247-259 Covering Polygons with Rectangles....Pages 260-273 Front Matter....Pages 274-288 The Complexity of Perfect Packings in Dense Graphs....Pages 57-57 On the Maximum Weight Minimal Separator....Pages 289-303 Pebble Games over Ordered Structural Abstractions....Pages 304-318 Counting Minimal Dominating Sets....Pages 319-332 On the Computational Complexity of Variants of Combinatorial Voter Control in Elections....Pages 333-347 On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas....Pages 348-361 Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution....Pages 362-372 Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model....Pages 373-388 Bounding the Dimension of Points on a Line....Pages 389-400 Büchi Automata Recognizing Sets of Reals Definable in First-Order Logic with Addition and Order....Pages 401-411 Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions....Pages 412-424 A Density Theorem for Hierarchies of Limit Spaces over Separable Metric Spaces....Pages 425-439 On the Conjecture of the Smallest 3-Cop-Win Planar Graph....Pages 440-454 On Complexity of Total Vertex Cover on Subcubic Graphs....Pages 455-469 Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)....Pages 470-483 The Smoothed Number of Pareto-Optimal Solutions in Non-integer Bicriteria Optimization....Pages 484-498 From Nonstandard Analysis to Various Flavours of Computability Theory....Pages 499-514 Front Matter....Pages 515-528 Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs....Pages 529-542 A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds....Pages 543-555 On the Complexity of Breaking Pseudoentropy....Pages 556-570 Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems....Pages 57-57 Parameterized Complexity of Fair Deletion Problems....Pages 571-585 Degrees of Word Problem for Algebras Without Finitely Presented Expansions....Pages 586-599 Kernelization and Parameterized Algorithms for 3-Path Vertex Cover....Pages 600-613 Fast Searching on Cartesian Products of Graphs....Pages 614-627 Sequentialization Using Timestamps....Pages 628-642 Back Matter....Pages 643-653 ....Pages 654-668