Mathematical Foundations of Computer Science 2014

1. Front Matter

   PDF

2. Invited Contributions

   1. Partial-Observation Stochastic Reachability and Parity Games

      • Krishnendu Chatterjee

      Pages 1-4

   2. Random Deterministic Automata

      • Cyril Nicaud

      Pages 5-23

   3. Communication Complexity Theory: Thirty-Five Years of Set Disjointness

      • Alexander A. Sherstov

      Pages 24-43

   4. What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?

      • Christian Sohler

      Pages 44-49

3. Logic, Semantics, Automata and Theory of Programming

   1. Choiceless Polynomial Time on Structures with Small Abelian Colour Classes

      • F. Abu Zaid, E. Grädel, M. Grohe, W. Pakusa

      Pages 50-62

   2. Sofic-Dyck Shifts

      • Marie-Pierre Béal, Michel Blockelet, Cătălin Dima

      Pages 63-74

   3. A Logical Characterization of Timed (non-)Regular Languages

      • Marcello M. Bersani, Matteo Rossi, Pierluigi San Pietro

      Pages 75-86

   4. Asymptotic Monadic Second-Order Logic

      • Achim Blumensath, Olivier Carton, Thomas Colcombet

      Pages 87-98

   5. Towards Efficient Reasoning Under Guarded-Based Disjunctive Existential Rules

      • Pierre Bourhis, Michael Morak, Andreas Pieris

      Pages 99-110

   6. Alternating Parity Krivine Automata

      • Florian Bruse

      Pages 111-122

   7. Advances in Parametric Real-Time Reasoning

      • Daniel Bundala, Joël Ouaknine

      Pages 123-134

   8. Universal Lyndon Words

      • Arturo Carpi, Gabriele Fici, Štěpán Holub, Jakub Opršal, Marinella Sciortino

      Pages 135-146

   9. Subword Complexity and Decomposition of the Set of Factors

      • Julien Cassaigne, Anna E. Frid, Svetlana Puzynina, Luca Q. Zamboni

      Pages 147-158

   10. Cyclic Complexity of Words

       • Julien Cassaigne, Gabriele Fici, Marinella Sciortino, Luca Q. Zamboni

       Pages 159-170

   11. Classifying Recognizable Infinitary Trace Languages Using Word Automata

       • Namit Chaturvedi, Marcus Gelderie

       Pages 171-182

   12. Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch’s Theorem

       • Yijia Chen, Moritz Müller

       Pages 183-195

   13. An Algebraic Characterization of Unary Two-Way Transducers

       • Christian Choffrut, Bruno Guillon

       Pages 196-207

   14. Size-Change Abstraction and Max-Plus Automata

       • Thomas Colcombet, Laure Daviaud, Florian Zuleger

       Pages 208-219

   15. Alternating Vector Addition Systems with States

       • Jean-Baptiste Courtois, Sylvain Schmitz

       Pages 220-231

This two volume set LNCS 8634 and LNCS 8635 constitutes the refereed conference proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, held in Budapest, Hungary, in August 2014. The 95 revised full papers presented together with 6 invited talks were carefully selected from 270 submissions. The focus of the conference was on following topics: Logic, Semantics, Automata, Theory of Programming, Algorithms, Complexity, Parallel and Distributed Computing, Quantum Computing, Automata, Grammars and Formal Languages, Combinatorics on Words, Trees and Games.

• 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
• formal specifications and program development
• foundations of computing
• grammars and formal languages
• lambda-calculus
• linear programming
• linear programming
• logic
• networks
• parallel and distributed computing
• quantum computing
• algorithm analysis and problem complexity

• Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary

  Erzsébet Csuhaj-Varjú

• Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, Ilmenau, Germany

  Martin Dietzfelbinger

• Institute of Informatics, Szeged University, Szeged, Hungary

  Zoltán Ésik

Policies and ethics