The Workshop


DCFS 2009 – Descriptional Complexity of Formal Systems will be held in Magdeburg, Germany, July 6 – 9, 2009.

DCFS 2009 will be jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and by the Faculty of Computer Science of the Otto von Guericke University Magdeburg.

It will take place immediately after

DLT 2009 – 13th International Conference on Developements in Language Theory, Stuttgart, Germany, June 30 – July 3, 2009.
Thus, it will be easy to attend both DLT and DCFS.


Researchers are invited to submit papers concerning the descriptional complexity of formal systems and structures (and its applications) for DCFS 2009.

Topics include, but are not limited to:

In accordance with the spirit of a workshop, the program committee will try to accept as many papers as possible, provided that their scientific quality is high and merits acceptance. If the number of such papers exceeds the number of time slots for "regular" presentation, the program committee will try to accept some papers as "short" papers.

Additionally, we plan to provide one or two sessions for papers that stimulate discussions. You are also invited to submit such papers for this special part.


Authors are asked to prepare their contributions with the LaTeX documentclass file dcfs09.cls. An example file using this class file is dcfs09ex.tex. A documentation of this class can be found in the files dcfs08dc.pdf and dcfs08qk.pdf from last year.

Please submit your contribution as two separate attachments:

  1. an information page with:
  2. the article with the title, but without the name(s) and the affiliation(s) of the author(s).
The article not containing any confidential information can be obtained by compiling the LaTeX file with the documentclass option sub.
The paper (without the information page) should not exceed 12 pages (appendix included) and should provide sufficient detail to allow the program committee to evaluate its validity, quality, and relevance. If appropriate, detailed proofs should be attached as an appendix.
Please submit your contribution via e-mail as two files (information page and the article) in postscript or pdf format by April 20, 2009 to

Simultaneous submissions to any other conferences with published proceedings are not allowed.

Important Dates

Deadline for submissions:  April 20, 2009
Notification of acceptance or rejection:   May 30, 2009
Early registration deadline:June 6, 2009
Final copy for the proceedings: June 18, 2009
Workshop:  July 6 – 9, 2009

Proceedings, Special Journal Issue

All accepted and invited papers appeared in the Proceedings edited by the University of Magdeburg, which were available at the conference. In addition, full versions of selected papers are eligible for publication in a special issue of the Journal of Automata, Languages and Combinatorics (after the standard refereeing process).

Most contributions appeared in the series Electronic Proceedings in Theoretical Computer Science, volume 3, (

Discussion Session

We plan to organize a special session during the workshop for the presentation of half-done papers, open problems, ideas for future research and new applications as well as on the importance of the current fields of interest. Researchers are invited to submit abstracts for the discussions until June 15, 2009.

Invited Speakers

Christel Baier (Dresden, Germany)
Janusz A. (John) Brzozowski (Waterloo, Ontario, Canada)
Andrei Păun (Ruston, USA; Madrid, Spain)
Nicole Schweikardt (Frankfurt/Main, Germany)

Steering Committee

Erzsébet Csuhaj-Varjú (Budapest, Hungary)
Jürgen Dassow (Magdeburg, Germany)
Lucian Ilie (London, ON, Canada)
Helmut Jürgensen (London, ON, Canada and Potsdam, Germany)
Chandra Kintala (Bangalore, India)
Hing Leung (Las Cruces, NM, USA)
Giovanni Pighizzini (Milano, Italy)
Detlef Wotschke (Frankfurt/Main, Germany)

Program Committee

Cezar Câmpeanu (Charlottetown, PE, Canada)
Jean-Marc Champarnaud (Rouen, France)
Erzsébet Csuhaj-Varjú (Budapest, Hungary)
Jürgen Dassow  (Co-Chair) (Magdeburg, Germany)
Viliam Geffert (Košice, Slovakia)
Alexander Okhotin (Turku, Finland)
Giovanni Pighizzini  (Co-Chair) (Milano, Italy)
Jeffrey O. Shallit (Waterloo, ON, Canada)
Bianca Truthe (Magdeburg, Germany)
Detlef Wotschke (Frankfurt/Main, Germany)

Organization Committee

Jürgen Dassow (Chair) Address: lOtto-von-Guericke-Universität Magdeburg
lFakultät für Informatik
lUniversitätsplatz 2
l39106 Magdeburg
Ronny Harbich
Bernd Reichel
Bianca Truthe
Catharina Berner Secretary: l+49 (0) 391 67 18343

Ronny Harbich Bianca Truthe Jürgen Dassow Catharina Berner Bernd Reichel