Fundamentals of Computation Theory

1. Front Matter

   PDF

2. Invited Lectures

   1. How to Guard the Guards Themselves

      • Moti Yung

      Pages 1-2

   2. Alternating Weighted Automata

      • Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger

      Pages 3-13

3. Contributions

   1. Maintaining Arrays of Contiguous Objects

      • Michael A. Bender, Sándor P. Fekete, Tom Kamphans, Nils Schweer

      Pages 14-25

   2. The k-Anonymity Problem Is Hard

      • Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi

      Pages 26-37

   3. Independence Results for n-Ary Recursion Theorems

      • John Case, Samuel E. Moelius III

      Pages 38-49

   4. Depletable Channels: Dynamics and Behaviour

      • Pietro Cenciarelli, Daniele Gorla, Ivano Salvo

      Pages 50-61

   5. Noise-Resilient Group Testing: Limitations and Constructions

      • Mahdi Cheraghchi

      Pages 62-73

   6. Martingales on Trees and the Empire Chromatic Number of Random Trees

      • Colin Cooper, Andrew R. A. McGrae, Michele Zito

      Pages 74-83

   7. Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity

      • Peter Damaschke, Azam Sheikh Muhammad

      Pages 84-95

   8. Combinatorial Queries and Updates on Partial Words

      • Adrian Diaconu, Florin Manea, Cătălin Tiseanu

      Pages 96-108

   9. The Longest Haplotype Reconstruction Problem Revisited

      • Riccardo Dondi

      Pages 109-120

   10. Earliest Query Answering for Deterministic Nested Word Automata

       • Olivier Gauwin, Joachim Niehren, Sophie Tison

       Pages 121-132

   11. Multiway In-Place Merging

       • Viliam Geffert, Jozef Gajdoš

       Pages 133-144

   12. On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs

       • Subhas Kumar Ghosh, Koushik Sinha

       Pages 145-156

   13. On Random Betweenness Constraints

       • Andreas Goerdt

       Pages 157-168

   14. Directed Graphs of Entanglement Two

       • Erich Grädel, Łukasz Kaiser, Roman Rabinovich

       Pages 169-180

   15. Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies

       • Paul Hänsch, Michaela Slaats, Wolfgang Thomas

       Pages 181-192

   16. Computing Role Assignments of Chordal Graphs

       • Pim van ’t Hof, Daniël Paulusma, Johan M. M. van Rooij

       Pages 193-204

   17. Three-Valued Abstractions of Markov Chains: Completeness for a Sizeable Fragment of PCTL

       • Michael Huth, Nir Piterman, Daniel Wagner

       Pages 205-216

This book constitutes the refereed proceedings of the 17th International Symposium Fundamentals of Computation Theory, FCT 2009, held in Wroclaw, Poland in August 2009. The 29 revised full papers were carefully reviewed and selected from 67 submissions. The papers address all current topics in computation theory such as automata and formal languages, design and analysis of algorithms, computational and structural complexity, semantics, logic, algebra and categories in computer science, circuits and networks, learning theory, specification and verification, parallel and distributed systems, concurrency theory, cryptography and cryptograhic protocols, approximation and randomized algorithms, computational geometry, quantum computation and information, bio-inspired computation.

• algorithms
• automata
• automata theory
• category theory
• complexity
• complexity theory
• computational geometry
• fundamentals
• game theory
• graph theory
• logic
• np-hard
• theoretical computer science
• turing machine
• vertex cover
• algorithm analysis and problem complexity

• Institute of Mathematics and Computer Science, Wrocław University of Technology, Wrocław, Poland

  Mirosław Kutyłowski, Maciej Gębala

• Institute of Computer Science, University of Wrocław, Wrocław, Poland

  Witold Charatonik

Policies and ethics