Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I (Lecture Notes in Computer Science Book 9234)

This two volume set LNCS 9234 and 9235 constitutes the refereed conference proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, held in Milan, Italy, in August 2015. The 82 revised full papers presented together with 5 invited talks were carefully selected from 201 submissions. The papers feature high-quality research in all branches of theoretical computer science. They have been organized in the following topical main sections: logic, semantics, automata, and theory of programming (volume 1) and algorithms, complexity, and games (volume 2). Front Matter....Pages I-XXVI Front Matter....Pages 1-1 Minimal and Monotone Minimal Perfect Hash Functions....Pages 3-17 Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview....Pages 18-37 Reversible and Irreversible Computations of Deterministic Finite-State Devices....Pages 38-52 Robust Inference and Local Algorithms....Pages 53-60 Front Matter....Pages 61-61 Uniform Generation in Trace Monoids....Pages 63-75 When Are Prime Formulae Characteristic?....Pages 76-88 Stochastization of Weighted Automata....Pages 89-102 Algebraic Synchronization Criterion and Computing Reset Words....Pages 103-115 Recurrence Function on Sturmian Words: A Probabilistic Study....Pages 116-128 Exponential-Size Model Property for PDL with Separating Parallel Composition....Pages 129-140 A Circuit Complexity Approach to Transductions....Pages 141-153 Locally Chain-Parsable Languages....Pages 154-166 Classes of Languages Generated by the Kleene Star of a Word....Pages 167-178 Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus....Pages 179-191 Weighted Automata and Logics on Graphs....Pages 192-204 Longest Gapped Repeats and Palindromes....Pages 205-217 Quasiperiodicity and Non-computability in Tilings....Pages 218-230 The Transitivity Problem of Turing Machines....Pages 231-242 Strong Inapproximability of the Shortest Reset Word....Pages 243-255 Finitary Semantics of Linear Logic and Higher-Order Model-Checking....Pages 256-268 Front Matter....Pages 61-61 Complexity of Propositional Independence and Inclusion Logic....Pages 269-280 Modal Inclusion Logic: Being Lax is Simpler than Being Strict....Pages 281-292 Differential Bisimulation for a Markovian Process Algebra....Pages 293-306 On the Hardness of Almost–Sure Termination....Pages 307-318 Graphs Identified by Logics with Counting....Pages 319-330 Synchronizing Automata with Extremal Properties....Pages 331-343 Ratio and Weight Quantiles....Pages 344-356 Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem....Pages 357-368 Definability by Weakly Deterministic Regular Expressions with Counters is Decidable....Pages 369-381 On the Complexity of Reconfiguration in Systems with Legacy Components....Pages 382-393 Eliminating Recursion from Monadic Datalog Programs on Trees....Pages 394-406 Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)....Pages 407-418 Emergence on Decreasing Sandpile Models....Pages 419-431 Lost in Self-Stabilization....Pages 432-443 Equations and Coequations for Weighted Automata....Pages 444-456 Back Matter....Pages 457-459