Fundamentals of Computation Theory

1. Front Matter

   Pages I-XIX

   PDF

2. Invited talks

   1. Front Matter

      Pages 1-1

      PDF

   2. Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

      • Marek Karpinski

      Pages 3-11

   3. On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS

      • Antonín Kučera

      Pages 12-24

3. Geometry, Combinatorics, Text Algorithms

   1. Front Matter

      Pages 25-25

      PDF

   2. Longest \(\alpha \)-Gapped Repeat and Palindrome

      • Paweł Gawrychowski, Florin Manea

      Pages 27-40

   3. On the Enumeration of Permutominoes

      • Ana Paula Tomás

      Pages 41-52

   4. Stabbing Segments with Rectilinear Objects

      • Mercè Claverol, Delia Garijo, Matias Korman, Carlos Seara, Rodrigo I. Silveira

      Pages 53-64

   5. \(\beta \)-skeletons for a Set of Line Segments in \(R^2 \)

      • Mirosław Kowaluk, Gabriela Majewska

      Pages 65-78

4. Complexity and Boolean Functions

   1. Front Matter

      Pages 79-79

      PDF

   2. Depth, Highness and DNR Degrees

      • Philippe Moser, Frank Stephan

      Pages 81-94

   3. On the Expressive Power of Read-Once Determinants

      • N. R. Aravind, Pushkar S. Joglekar

      Pages 95-105

   4. Constructive Relationships Between Algebraic Thickness and Normality

      • Joan Boyar, Magnus Gausdal Find

      Pages 106-117

   5. On the Structure of Solution-Graphs for Boolean Formulas

      • Patrick Scharpfenecker

      Pages 118-130

5. Languages

   1. Front Matter

      Pages 131-131

      PDF

   2. Interprocedural Reachability for Flat Integer Programs

      • Pierre Ganty, Radu Iosif

      Pages 133-145

   3. Complexity of Suffix-Free Regular Languages

      • Janusz Brzozowski, Marek Szykuła

      Pages 146-159

   4. Alternation Hierarchies of First Order Logic with Regular Predicates

      • Luc Dartois, Charles Paperman

      Pages 160-172

   5. A Note on Decidable Separability by Piecewise Testable Languages

      • Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen, Marc Zeitoun

      Pages 173-185

6. Set Algorithms, Covering, and Traversal

   1. Front Matter

      Pages 187-187

      PDF

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.

• Algorithm design
• Approximation
• Automata and formal languages
• Cloud computing
• Combinatorics
• Computational biology
• Computational complexity
• Computational geometry
• Distributed computing
• Evolving systems
• Formal methods
• Hybrid systems
• Logics
• Model checking
• Online algorithms
• Optimization
• Parallel computing
• Quantum computing
• Ubiquitous systems
• Verification

• Université Paris Diderot, Paris, France

  Adrian Kosowski

• Université Bordeaux 1, Talence, France

  Igor Walukiewicz

Policies and ethics