[TYPES/announce] Early registration deadline approaching for FCT 2011 - Fundamentals of Computation Theory in Oslo

Wed Jul 27 08:05:27 EDT 2011

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.