Mathematical Foundations of Computer Science 2015

1. Front Matter

   Pages I-XXVI

   PDF

2. Invited Contributions

   1. Front Matter

      Pages 1-1

      PDF

   2. Minimal and Monotone Minimal Perfect Hash Functions

      • Paolo Boldi

      Pages 3-17

      PDF

   3. Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview

      • Zoltán Ésik

      Pages 18-37

      PDF

   4. Reversible and Irreversible Computations of Deterministic Finite-State Devices

      • Martin Kutrib

      Pages 38-52

      PDF

   5. Robust Inference and Local Algorithms

      • Yishay Mansour

      Pages 53-60

      PDF

3. Logic, Semantics, Automata and Theory of Programming

   1. Front Matter

      Pages 61-61

      PDF

   2. Uniform Generation in Trace Monoids

      • Samy Abbes, Jean Mairesse

      Pages 63-75

      PDF

   3. When Are Prime Formulae Characteristic?

      • L. Aceto, D. Della Monica, I. Fábregas, A. Ingólfsdóttir

      Pages 76-88

      PDF

   4. Stochastization of Weighted Automata

      • Guy Avni, Orna Kupferman

      Pages 89-102

      PDF

   5. Algebraic Synchronization Criterion and Computing Reset Words

      • Mikhail Berlinkov, Marek Szykuła

      Pages 103-115

      PDF

   6. Recurrence Function on Sturmian Words: A Probabilistic Study

      • Valérie Berthé, Eda Cesaratto, Pablo Rotondo, Brigitte Vallée, Alfredo Viola

      Pages 116-128

      PDF

   7. Exponential-Size Model Property for PDL with Separating Parallel Composition

      • Joseph Boudou

      Pages 129-140

      PDF

   8. A Circuit Complexity Approach to Transductions

      • Michaël Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman

      Pages 141-153

      PDF

   9. Locally Chain-Parsable Languages

      • Stefano Crespi Reghizzi, Violetta Lonati, Dino Mandrioli, Matteo Pradella

      Pages 154-166

      PDF

   10. Classes of Languages Generated by the Kleene Star of a Word

       • Laure Daviaud, Charles Paperman

       Pages 167-178

       PDF

   11. Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus

       • Cătălin Dima, Bastien Maubert, Sophie Pinchinat

       Pages 179-191

       PDF

   12. Weighted Automata and Logics on Graphs

       • Manfred Droste, Stefan Dück

       Pages 192-204

       PDF

   13. Longest Gapped Repeats and Palindromes

       • Marius Dumitran, Florin Manea

       Pages 205-217

       PDF

   14. Quasiperiodicity and Non-computability in Tilings

       • Bruno Durand, Andrei Romashchenko

       Pages 218-230

       PDF

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).

• algebra and categories in computer science
• algorithmic game theory
• algorithmic learning theory
• algorithms and data structures
• approximation algorithms
• automata-computational complexity
• concurrency theory
• cryptography and security
• databases and knowledge-based systems
• distributed computing
• formal specifications
• foundations of computing
• grammars and formal languages
• lambda-calculus
• linear programming
• logic-networks
• parallel computing
• program development
• quantum computing
• semantics and verification of programs
• algorithm analysis and problem complexity

• Università di Roma "Tor Vergata", Rome, Italy

  Giuseppe F Italiano

• Università degli Studi di Milano, Milan, Italy

  Giovanni Pighizzini

• University of Edinburgh, Edinburgh, United Kingdom

  Donald T. Sannella

Policies and ethics