Newsletter 123
September  1, 2009

* Past issues of the newsletter are available at
* Instructions for submitting an announcement to the newsletter
  can be found at
* To unsubscribe, send an email with "unsubscribe" in the
  subject line to

  Upcoming deadlines
  STACS 2010 - Call for Papers
  GREIFSWALD 2010 - Call for Papers
  FLOPS 2009 - Call for Papers
  LATA 2010 - Call for Papers
  ESORICS 2009 - Call for Participation
  STM 2009 - Call for Participation
  FM 2009 - Call for Participation
  CAV 2009
  Research Position at the Humboldt-University Berlin
  2 Post-Doctoral Positions at the University of Oxford

* STACS 2010
* Logical Approaches to Barriers in Computing and Complexity
* FLOPS 2010
* LATA 2010

  MARCH 4-6, 2010, NANCY, FRANCE
* Scope : Typical areas include (but are not limited to)  Algorithms
  and data structures (including: parallel and distributed algorithms,
  computational geometry, cryptography, algorithmic learning theory);
  Automata and formal languages; Computational and structural
  complexity; Logic in computer science ( including: semantics,
  specification, and verification of programs, rewriting and deduction);
  Current challenges (for example: biological computing, quantum
  computing, mobile and net computing).
* Invited speakers:
  Mikolaj Bojanczyk, Warsaw University,
  Rolf Niedermeier, University of Jena,
  Jacques Stern, Ecole Normale Supérieure
* Important dates :
  - Deadline for submission: September 22, 2009
  - Notification to authors: November 26, 2009
  - Final version: December 18, 2009
* Detailed information can be found on the webpage :

Logical Approaches to Barriers in Computing and Complexity
  Greifswald, 17-20 February 2010
  Call for Papers
* The workshop is jointly organized by the "Deutsche Vereinigung fuer
  Mathematische Logik und fuer Grundlagen der Exakten Wissenschaften"
  (DVMLG), the "Polskie Towarzystwo Logiki i Filozofii Nauki"
  (PTLiFN), the "Association Computability in Europe" (ACiE) and the
  "European Association for Computer Science Logic" (EACSL).  The
  workshop is sponsored by the Stiftung Alfried Krupp Kolleg
  Greifswald and the Deutsche Forschungsgemeinschaft (DFG), and takes
  place at the Alfried Krupp Wissenschaftskolleg in Greifswald,
  - Submission of extended abstracts: 15 October 2009
  - Notification of authors: 1 December 2009
  - Deadline for final revisions: 5 Januar 2010
  We have funds to offer financial support to authors of accepted
  papers.  In individual cases refunds can range up to full
  reimbursement of travel and accommodation costs.  Further detail
  will be announced on the webpage.
  Computability theory and complexity theory have their origins in
  logic. Famous names such as Goedel, Turing, Cook, and Kolmogorov
  connect these areas of computer science to foundations of
  mathematics. The fundamental goal of this area is to understand the
  limits of computability (that is analysing which problems can be
  solved on nowadays and future computers in principle) and efficient
  computability (that is understanding the class of problems which can
  be solved quickly and with restricted resources) where the most
  famous open problem is the P=NP-problem. Logic provides a
  multifarious toolbox of techniques to analyse questions like this,
  some of which promise to provide a deep insight in the structure of
  limit of computation.
  In our workshop, we shall focus on the following aspects: logical
  descriptions of complexity (e.g., descriptive complexity, bounded
  arithmetic), complexity classes of abstract, algebraic and infinite
  structures, barriers in proving complexity results, and Kolmogorov
  complexity and randomness.
  Zofia Adamowicz (Warsaw)          Alessandra Carbone (Paris)
  Franz Baader (Dresden)            Lance Fortnow (Evanston, IL)
  Arnold Beckmann (chair; Swansea)  Erich Graedel (Aachen)
  Sam Buss (La Jolla CA)            Pascal Koiran (Lyon)
  Manfred Droste (Leipzig)          Leszek Kolodziejczyk (Warsaw)
  Christine Gassner (Greifswald)    Antonina Kolokolova (St.John's, NL)
  Peter Koepke (Bonn)
  Benedikt Loewe (Amsterdam)      * SPECIAL SESSION on "Complexity in
  Johann Makowsky (Haifa),          Arbitrary Structures", organised by
  Elvira Mayordomo (Zaragoza)       Christine Gassner (Greifswald) and
  Damian Niwinski (Warsaw)          Martin Ziegler (Paderborn)
  Wolfgang Thomas (Aachen)
  Martin Ziegler (Paderborn)
  The Programme Committee cordially invites all researchers in the
  area of the workshop to submit their extended abstracts (in
  PDF-format, at most 4 pages) for presentation at the workshop.
  Further details about submission can be found on our website
  Accepted abstracts will be printed in an abstract booklet which will
  be distributed to the participants of the workshop.  We emphatically
  encourage submissions by female authors, as women are
  underrepresented in mathematics and computer science.
  Submission of abstracts of published and presented work is also
  possible, since the abstract booklet is non-archival.  Quality and
  quantity of submissions permitting, we plan to invite the authors of
  unpublished papers to submit a full version to a post-proceedings
  volume after the workshop.

   Second Call for Papers
   April 19-21, 2010
   Sendai, Japan
   Submission deadline: October 16, 2009
* FLOPS is a forum for research on all issues concerning declarative
  programming, including functional programming and logic programming,
  and aims to promote cross-fertilization and integration between the
  two paradigms.  Previous FLOPS meetings were held in Fuji Susono
  (1995), Shonan Village (1996), Kyoto (1998), Tsukuba (1999), Tokyo
  (2001), Aizu (2002), Nara (2004), Fuji Susono (2006), and Ise
   FLOPS solicits original papers in all areas of functional and logic
   programming, including (but not limited to):
   - Declarative Pearls: new and excellent declarative programs with
     illustrative applications.
   - Language issues: language design and constructs, programming
     methodology, integration of paradigms, interfacing with other
     languages, type systems, constraints, concurrency and distributed
   - Foundations: logic and semantics, rewrite systems and narrowing,
     type theory, proof systems.
   - Implementation issues: compilation techniques, memory management,
     program analysis and transformation, partial evaluation,
   - Applications: case studies, real-world applications, graphical
     user interfaces, Internet applications, XML, databases, formal
     methods and model checking.
*The proceedings will be published as an LNCS volume. The proceedings
  of the previous meeting (FLOPS 2008) were published as LNCS 4989.
  Matthias Blume (TTI, Chicago, USA)
  German Vidal (Technical University of Valencia, Spain)
  Naoki Kobayashi (Tohoku University, Sendai, Japan)
  - Nick Benton (Microsoft Research, Cambridge, UK)
  - Manuel Chakravarty (University of New South Wales, Australia)
  - Michael Codish (Ben-Gurion University of the Negev, Israel)
  - Bart Demoen (Katholieke Universiteit Leuven, Belgium)
  - Agostino Dovier (University of Udine, Italy)
  - John P. Gallagher (Roskilde University, Denmark)
  - Maria Garcia de la Banda (Monash University, Australia)
  - Michael Hanus (University of Kiel, Germany)
  - Atsushi Igarashi (Kyoto University, Japan)
  - Patricia Johann (Rutgers University, USA)
  - Shin-ya Katsumata (Kyoto University, Japan)
  - Michael Leuschel (University of Dusseldorf, Germany)
  - Francisco Lopez-Fraguas (Complutense University of Madrid, Spain)
  - Paqui Lucio (University of the Basque Country, Spain)
  - Yasuhiko Minamide (University of Tsukuba, Japan)
  - Frank Pfenning (Carnegie Mellon University, USA)
  - Francois Pottier (INRIA, France)
  - Tom Schrijvers (Katholieke Universiteit Leuven, Belgium)
  - Chung-chieh "Ken" Shan (Rutgers University, USA)
  - Zhong Shao (Yale University, USA)
  - Jan-Georg Smaus (University of Freiburg, Germany)
  - Nobuko Yoshida (Imperial College London, UK)
  Eijiro Sumii (Tohoku University, Sendai, Japan)
  Submissions must be unpublished and not submitted for publication
  elsewhere. Work that already appeared in unpublished or informally
  published workshops proceedings may be submitted. Submissions should
  fall into one of the following categories:
  - Regular research papers: they should describe new results and will
    be judged on originality, correctness, and significance.
  - System descriptions: they should contain a link to a working
    system and will be judged on originality, usefulness, and design.
   All submissions must be written in English and can be up to 15
   proceedings pages long. Authors are strongly encouraged to use
   LaTeX2e and the Springer llncs class file, available at
  Submission deadlines:
     - Abstract: October 16, 2009
     - Paper:    October 23, 2009
   Author notification: December 21, 2009
   Camera-ready copy: January 24, 2010
   Conference: April 19-21, 2010

   1st Call for Papers
   Trier, Germany, May 24-28, 2010
* LATA is a yearly conference in theoretical computer science and its
  applications. As linked to the International PhD School in Formal
  Languages and Applications that was developed at Rovira i Virgili
  University (the host of the previous three editions and co-organizer
  of this one) in the period 2002-2006, LATA 2010 will reserve
  significant room for young scholars at the beginning of their
  career. It will aim at attracting contributions from both classical
  theory fields and application areas (bioinformatics, systems biology,
  language technology, artificial intelligence, etc.).
  Topics of either theoretical or applied interest include, but are
  not limited to:
  - algebraic language theory
  - algorithms on automata and words
  - automata and logic
  - automata for system analysis and programme verification
  - automata, concurrency and Petri nets
  - cellular automata
  - combinatorics on words
  - computability
  - computational complexity
  - computer linguistics
  - data and image compression
  - decidability questions on words and languages
  - descriptional complexity
  - DNA and other models of bio-inspired computing
  - document engineering
  - foundations of finite state technology
  - fuzzy and rough languages
  - grammars (Chomsky hierarchy, contextual, multidimensional,
    unification, categorial, etc.)
  - grammars and automata architectures
  - grammatical inference and algorithmic learning
  - graphs and graph transformation
  - language varieties and semigroups
  - language-based cryptography
  - language-theoretic foundations of artificial intelligence and
    artificial life
  - neural networks
  - parallel and regulated rewriting
  - parsing
  - pattern matching and pattern recognition
  - patterns and codes
  - power series
  - quantum, chemical and optical computing
  - semantics
  - string and combinatorial issues in computational biology and bioinformatics
  - symbolic dynamics
  - term rewriting
  - text algorithms
  - text retrieval
  - transducers
  - trees, tree languages and tree machines
  - weighted machines
  Alberto Apostolico (Atlanta)
  Thomas Bäck (Leiden)
  Stefania Bandini (Milano)
  Wolfgang Banzhaf (St. John's)
  Henning Bordihn (Potsdam)
  Kwang-Moo Choe (Daejeon)
  Andrea Corradini (Pisa)
  Christophe Costa Florencio (Leuven)
  Maxime Crochemore (Marne-la-Vallée)
  W. Bruce Croft (Amherst)
  Erzsébet Csuhaj-Varjú (Budapest)
  Jürgen Dassow (Magdeburg)
  Volker Diekert (Stuttgart)
  Rodney G. Downey (Wellington)
  Frank Drewes (Umea)
  Henning Fernau (Trier, co-chair)
  Rusins Freivalds (Riga)
  Rudolf Freund (Wien)
  Paul Gastin (Cachan)
  Edwin Hancock (York, UK)
  Markus Holzer (Giessen)
  Helmut Jürgensen (London, Canada)
  Juhani Karhumäki (Turku)
  Efim Kinber (Fairfield)
  Claude Kirchner (Bordeaux)
  Carlos Martín-Vide (Brussels, co-chair)
  Risto Miikkulainen (Austin)
  Victor Mitrana (Bucharest)
  Claudio Moraga (Mieres)
  Sven Naumann (Trier)
  Chrystopher Nehaniv (Hatfield)
  Maurice Nivat (Paris)
  Friedrich Otto (Kassel)
  Daniel Reidenbach (Loughborough)
  Klaus Reinhardt (Tübingen)
  Antonio Restivo (Palermo)
  Christophe Reutenauer (Montréal)
  Kai Salomaa (Kingston, Canada)
  Jeffrey Shallit (Waterloo)
  Eljas Soisalon-Soininen (Helsinki)
  Bernhard Steffen (Dortmund)
  Frank Stephan (Singapore)
  Wolfgang Thomas (Aachen)
  Marc Tommasi (Lille)
  Esko Ukkonen (Helsinki)
  Todd Wareham (St. John's)
  Osamu Watanabe (Tokyo)
  Bruce Watson (Pretoria)
  Thomas Wilke (Kiel)
  Slawomir Zadrozny (Warsaw)
  Binhai Zhu (Bozeman)
  Authors are invited to submit papers presenting original and
  unpublished research. Papers should not exceed 12 single-spaced pages
  and should be formatted according to the standard format for Springer
  Verlag's LNCS series (see
  Submissions have to be uploaded at:
  A volume of proceedings published by Springer in the LNCS series
  will be available by the time of the conference.
  At least one special issue of a major journal will be later
  published containing extended versions of the papers contributed to
  the conference.
  Submissions to the post-conference publications will be only by invitation.
  The period for registration will be open since September 1, 2009
  until May 24, 2010. The registration form can be found at the website
  of the conference:
  Paper submission: December 3, 2009
  Notification of paper acceptance or rejection: January 21, 2010
  Final version of the paper for the LNCS proceedings: February 3, 2010
  Early registration: February 15, 2010
  Late registration: May 14, 2010
  Starting of the conference: May 24, 2010
  Submission to the post-conference publications: August 27, 2010

ESORICS 2009 - 14th European Symposium on Research in Computer Security
   September 21-25, 2009, Saint-Malo, France
* ESORICS, the European Symposium on Research in Computer Security, is
  the leading research-oriented conference on the theory and practice of
  computer security in Europe. The aim of ESORICS is to further the
  progress of research in computer security by establishing a European
  forum for bringing together researchers in this area, by promoting the
  exchange of ideas with system developers and by encouraging links with
  researchers in related areas.
* Organized in a series of European countries, ESORICS is confirmed as
  the leading European research event in computer security.
* You are invited to join us at ESORICS and its collocated workshops
  (DPM'2009, SETOP'2009 and STM'2009) this September in the beautiful
  city of Saint-Malo in the French Brittany.
* The conference program is available here:
* Register online at:

STM 2009 - 5th International Workshop on Security and Trust Management
   Call for Participation
   September 24-25, 2009 - Saint Malo, France
* STM (Security and Trust Ma-nagement) is a established working group
  of ERCIM (European Research Consortium in Informatics and
* STM 2009 is the fifth workshop in this series and will be held in
   Saint Malo, France, in conjunction with ESORICS 2009 (14th European
   Symposium on Research in Computer Security).
* STM has the following aims:
  - to investigate the foundations and applications of security and
    trust in ICT;
  - to study the deep interplay between trust management and common
    security issues such as confidentiality, integrity, and
  - to identify and promote new areas of research connected with
    security management (e.g. dynamic and mobile coalition management,
    P2P, MANETs, Web/GRID services);
  - to identify and promote new areas of research connected with trust
    management (e.g., reputation, recommendation, and collaboration);
  - to provide a platform for presenting and discussing emerging ideas
    and trends.
* Registration information is available at
  Additional information about the conference can be found at

FM 2009 - 16th International Symposium on Formal Methods
  Call for Participation
  November 2--6, 2009, Eindhoven, the Netherlands
* FM2009 is the sixteenth symposium in a series of the Formal Methods Europe
  association (FME). The symposium will be organized as a world congress.
  Ten years after FM'99 in Toulouse, the first world congress, the formal
  methods communities from all over the world will again have the opportunity
  to meet. Therefore, FM2009 will be both an occasion to celebrate, and a
  platform for enthusiastic researchers and practitioners from a diversity
  of backgrounds and schools to exchange their ideas and share their
* Registration is open: Early registration until September 14
* Important dates:
   - September 14: Early registration deadline
   - October 19: Normal registration deadline
* Invited Speakers:
  - Wan Fokkink, Vrije Universiteit Amsterdam, The Netherlands
  - Carroll Morgan, University of New South Wales, Sidney, Australia
  - Colin O'Halloran, QinetiQ, Malvern, United Kingdom
  - Sriram Rajamani, Microsoft Research India, Bangalore, India
  - Jeannette Wing, Carnegie Mellon University, Pittsburg PA, USA
* Detailed information can be found on the webpage.

* The annual award, which recognizes a specific fundamental
  contribution or series of outstanding contributions to the CAV field,
  was given to
  - Conor F. Madigan, Kateeva, Inc.;
  - Sharad Malik, Princeton University, USA;
  - Joao P. Marques-Silva, University College Dublin, Ireland;
  - Matthew W. Moskewicz, University of California, Berkeley, USA;
  - Karem A. Sakallah, University of Michigan, USA;
  - Lintao Zhang, Microsoft Research
  - Ying Zhao, Wuxi Capital Group.
* The award includes a $10,000 prize and was presented with the
  citation: "For fundamental contributions to the development of
  high-performance Boolean satisfiability solvers. "
* Contact: Randal E. Bryant, Carnegie Mellon University

* Applications are invited for a three year research position in Theoretical
  Computer Science at the Humboldt-University Berlin. The position is within
  the research project "Descriptive Complexity of Small Complexity
* Candidates are expected to have excellent knowldege in mathematical logic
  and theoretical computer science. They should preferably have a PhD in
  Mathematics or Computer Science, but strong candidates without a PhD will
  also be considered, and they will have the opportunity to work towards a PhD
  on this position.
* Application deadline is October 10, 2009.
* Further details can be found at
* Informal inquieries may be addressed to Martin Grohe

* The Oxford University Computing Laboratory is looking to recruit two
  Grade 7 Postdoctoral Research Assistants to work on the EPSRC-funded
  project "Automated Verification of Probabilistic Programs", under the
  direction of Joel Ouaknine, Andrzej Murawski, and James Worrell.
* Applicants should have (or shortly expect to receive) a PhD in Computer
  Science or a closely related field, and ** EITHER ** strong programming
  skills, some experience of tool construction, and basic knowledge of
  program analysis, ** OR ** a strong background in theoretical computer
  science or mathematics and exposure to topics in system or program
* The work will take place within the Verification group in Oxford
  University Computing Laboratory, which comprises, in addition to the three
  investigators, world-leading experts in probabilistic verification and
  model checking such as Marta Kwiatkowska, Daniel Kroening, Gavin Lowe, Tom
  Melham, Luke Ong, and Bill Roscoe.
* The posts are for fixed term appointments of up to 18 months, will have a
  salary on the University grade 7 scale (currently 28,839 to 35,469 UK
  pounds per annum; includes membership of USS; will have an annual leave
  entitlement of 38 days per year inclusive of all public holidays and
  university closed periods), and are available from 1st November 2009.
* Further particulars, including details of how to apply, are available
  or by email request to:
* Potential applicants are also very welcome to send informal inquiries to
  any of the investigators:
  - Joel Ouaknine (
  - Andrzej Murawski (
  - James Worrell (
* The closing date for applications is Sunday 20th September 2009.

Back to the LICS web page.