DCFS 2006 - Descriptional Complexity of Formal Systems will be held in Las Cruces, New Mexico, June 21-23, 2006.

DCFS and its predecessors DCAGRS (Descriptional Complexity of Automata, Grammars and Related Structures) and FDSR (Formal Descriptions and Software Reliability) were previously held in Paderborn (1998); Magdeburg (1999); Boca Raton (1999); London, Ontario, (2000); San Jose (2000); Vienna (2001); London, Ontario, (2002); Budapest (2003); London, Ontario, (2004); and Como, Italy (2005).

DCFS 2006 will be jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and by the Department of Computer Science of New Mexico State University. The workshop is sponsored by the Department of Computer Science of University of Texas at El Paso.

It will take place immediately before

DLT 2006 - Tenth International Conference on Developements in Language Theory, Santa Barbara, California, USA, June 26-29, 2006.

Submissions concerning the descriptional complexity of formal systems and structures (and its applications) are invited for DCFS 2006.

Topics include, but are not limited to:

• various measures of descriptional complexity of automata, grammars, languages and of related systems
• trade-offs between descriptional complexity and mode of operation
• circuit complexity of Boolean functions and related measures
• succinctness of description of (finite) objects
• descriptional complexity in resource-bounded or structure-bounded environments
• structural complexity
• descriptional complexity of formal systems for applications (e.g. software reliability, software and hardware testing, modelling of natural languages)
• descriptional complexity aspects of nature-motivated (bio-inspired) architectures and unconventional models of computing
• Kolmogorov complexity and descriptional complexity

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.

Authors are asked to submit their contributions as two separate attachments:

1. an information page with:
• the title of the paper
• the name(s) of the author(s)
• their (his/her) affiliation, address, e-mail address
2. the article with the title, but without the name(s) and the affiliation(s) of the author(s).

The paper (without the information page) should not exceed 12 pages (appendix included), using 11-point font with ample margins, 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 7, 2006 (NEW submission deadline) to dcfs2006@cs.nmsu.edu.

Lane Hemaspaandra, Luc Longpre, Andreas Malcher, Jeff Shallit.

Cristian Calude                (Auckland, New Zealand)
Jean-Marc Champarnaud          (Rouen, France)
Erzsebet Csuhaj-Varju          (Budapest, Hungary)
Juergen Dassow                 (Magdeburg, Germany)
Viliam Geffert                 (Kosice, Slovakia)
Jonathan Goldstine             (State College, USA)
Juraj Hromkovic                (Zurich, Switzerland)
Oscar Ibarra                   (Santa Barbara, USA)
Lila Kari                      (London, Canada)
Orna Kupferman                 (Jerusalem, Israel)
Hing Leung          (Co-Chair) (Las Cruces, USA)
Victor Mitrana                 (Tarragona, Spain)
Giovanni Pighizzini (Co-Chair) (Milano, Italy)
Bala Ravikumar                 (Sonoma, USA)
Arto Salomaa                   (Turku, Finland)
Detlef Wotschke                (Frankfurt/Main, Germany)
Sheng Yu                       (London, Canada)

Hing Leung                     (Las Cruces)
Desh Ranjan                    (Las Cruces)
Brian Cloteaux                 (Las Cruces)

All accepted and invited papers will appear in the Proceedings, which will be available at the conference. Selected papers will appear in a special issue of the Theoretical Computer Science.

Deadline for submissions:	April 7, 2006 (NEW)
Notification of acceptance or rejection:	May 10, 2006
Final copy for the preproceedings:	June 1, 2006
Workshop:	June 21-23, 2006