Please excuse if you receive multiple coppies of this anouncement! -------------------------------------------------------------------- Call for Participation FCT 2011 18th International Symposium on Fundamentals of Computer Theory August 22-25, 2011, Oslo, Norway http://fct11.ifi.uio.no/ Established in 1977, the biennial Symposium on Fundamentals of Computation Theory is an international forum for researchers interested in all aspects of theoretical computer science. -------------------------------------------------------------------- REGISTRATION OPEN Early registration deadline: July 31, 2011 A limited amount of student sponsorships are available on application. INVITED SPEAKERS: - Yuri Gurevich (Microsoft Research, Redmond USA) "Impugning Randomness, Convincingly" - Daniel Lokshtanov (University of California, USA) "Kernelization; an Overview" - Jose Meseguer (University of Illinois at Urbana-Champaign, USA) "The Rewriting Logic Semantics Project: A Progress Report" - Andrew P. Black (Portland State University, USA) TBA The accepted papers are listed below. They are arranged in sessions covering ---------------------------------------------- o Complexity theory o Parametrized algorithms o Computation models o Calculi and programs o Graph algorithms o Fundamentals of Computing ---------------------------------------------- For the schedule of the program, see the FCT web-site. 1. A.N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word 2. Annabell Berger and Matthias Mueller-Hannemann. Dag Realizations of Directed Degree Sequences 3. Bart M. P. Jansen and Stefan Kratsch. Data Reduction for Graph Coloring Problems 4. Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. Computational Randomness from Generalized Hardcore Sets 5. Elliot Fairweather, Maribel Fernandez and Murdoch Gabbay. Principal types for nominal theories 6. Fabien Givors and Gregory Lafitte. Sub-Computabilities 7. Ferdinando Cicalese, Martin Milanic and Ugo Vaccaro. Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs 8. Florian Corzilius and Erika Abraham. Virtual Substitution for SMT Solving 9. Giorgio Ausiello, Nicolas Boria, Aristotelis Giannakos, Giorgio Lucarelli and Vangelis Paschos. Online maximum k-coverage 10. Gregory Gutin, Mark Jones and Anders Yeo. A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application 11. Guillaume Malod. Succinct algebraic branching programs characterizing non-uniform complexity classes 12. Jacques Bahi, Jean-Francois Couchot, Christophe Guyeux and Adrien Richard. On the Link Between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems 13. Jos Baeten, Bas Luttik and Paul Van Tilburg. Reactive Turing Machines 14. Klaus Meer. Almost transparent short proofs for NP over the reals 15. Krishnendu Chatterjee, Laurent Doyen and Rohit Singh. On Memoryless Quantitative Objectives 16. Ludwig Staiger. Constructive dimension and Hausdorff dimension: the case of exact dimension 17. Mamadou Moustapha Kante, Vincent Limouzy, Arnaud Mary and Lhouari Nourine. Enumeration of Minimal Dominating Sets and Variants 18. Marius Zimand. On the optimal compression of sets in PSPACE 19. Martin Ebbesen, Paul Fischer and Carsten Witt. Edge-matching Problems with Rotations 20. Mila Dalla Preda and Cinzia Di Giusto. Hunting distributed malware with the k-calculus 21. Nathaniel Charlton and Bernhard Reus. Specification patterns and proofs for recursion through the store 22. Paul Hunter. LIFO-search on digraphs: A searching game for cycle-rank 23. Petr Golovach, Daniel Paulusma and Jian Song. Coloring graphs without short cycles and long induced paths 24. Pinar Heggernes, Pim Van 'T Hof, Bart Jansen, Stefan Kratsch and Yngve Villanger. Parameterized Complexity of Vertex Deletion into Perfect Graph Classes 25. Robert Bredereck, Andre Nichterlein, Rolf Niedermeier and Geevarghese Philip. The Effect of Homogeneity on the Complexity of k-Anonymity 26. Sergey Goncharov and Lutz Schroeder. A Coinductive Calculus for Asynchronous Side-effecting Processes 27. Stephen Fenner. Functions that preserve p-randomness 28. Stephane Bessy and Anthony Perez. Polynomial kernels for Proper Interval Completion and related problems EVENTS * FCT is part of the program related to the scientific opening of the new "Ole-Johan Dahl building" of the Department of Informatics. This part takes the morning of Monday 22nd. It will include invited talks and discussion panel on mainly theory and future of programming languages. * The social dinner takes place in the Gamle Logen, the place where the King of Norway hands each year the Abel Prize for life-long achievements in Mathematics. * An excursion is organized in the second afternoon of the conference. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]