International Workshop on Descriptional Complexity of Formal Systems
# International Workshop on Descriptional Complexity of Formal Systems

La conférence International Workshop on Descriptional Complexity of Formal Systems (abrégé en DCFS) est une conférence scientifique annuelle dans le domaine de l'informatique théorique, plus particulièrement en théorie des automates et langages formels.

Les contributions proposées sont évaluées par les pairs, comme il est d'usage dans ces conférences; les communications acceptées sont publiées, depuis 2011, dans la série des Lecture Notes in Computer Science (en) de Springer. Dès les premières conférences, des versions détaillées de certaines contributions paraissent dans des journaux scientifiques spécialisés, comme International Journal of Foundations of Computer Science, Journal of Automata, Languages and Combinatorics, Theoretical Computer Science ou encore Information and Computation.

Dans sa forme actuelle, la conférence DCFS résulte de la fusion, en 2002, de deux autres workshop, à savoir DCAGRS (Descriptional Complexity of Automata, Grammars and Related Structures) et FDSR (Formal Descriptions and Software Reliability). Le workshop DCFS se tient fréquemment aux mêmes lieux et dates que d'autres conférences internationales sur les mêmes thèmes, comme ICALP, DLT ou CIAA.

## Thèmes des conférences

Les sujets abordés concernent notamment :

* Mesures de complexité descriptive des automates finis, de grammaires et de langages, et de systèmes reliés.
* Compromis entre complexité descriptive et les modes opératoires.
* Complexité des circuits (en) des fonctions booléennes et mesures similaires.
* Concision de description d'objets finis.
* Complexité d'états d'automates finis.
* Complexité de description dans des environnements à ressources ou structures limitées.
* Complexité structurelle (en).
* Complexité descriptive de systèmes formels en pratique, comme fiabilité des logiciels, test de logiciel et matériel, modélisation de langues naturelles.
* Aspects de complexité descriptive d'architectures motivées par la biologie et des modèles de calculs non conventionnels.
* Complexité de Kolmogorov et complexité descriptive.

Les sujets de la conférence recouvrent ceux énumérés par le Working Group 1.2 du International Federation for Information Processing sur la complexité descriptive.

## Historique du workshop

Les premières conférences (DCAGRS et FSDR) sont les suivantes :

### DCAGRS

* 1er DCAGRS 1999, Magdeburg (Allemagne)
* 2e DCAGRS 2000, London (Ontario)
* 3e DCAGRS 2001, Vienne (Autriche)

### FSDR

* 1er FSDR 1998 Paderborn (Allemagne)
* 2e FSDR 1999 Boca Raton (Floride)
* 3e FSDR 2000 San José (Californie)

Depuis 2002, les conférences ont lieu sous leur nouveau nom :

### DCFS

* 4e DCFS 2002 London (Ontario)
* 5e DCFS 2003 Budapest (Hongrie)
* 6e DCFS 2004 London (Ontario)
* 7e DCFS 2005 Côme (Italie)
* 8e DCFS 2006 Las Cruces (Nouveau-Mexique)
* 9e DCFS 2007 High Tatras, Slovakia
* 10e DCFS 2008 Charlottetown (Canada)
* 11e DCFS 2009 Magdeburg (Allemagne)
* 12e DCFS 2010 Saskatoon (Saskatchewan)
* 13e DCFS 2011 Giessen (Allemagne)
* 14e DCFS 2012 Braga (Portugal)
* 15e DCFS 2013 London (Ontario)
* 16e DCFS 2014 Turku (Finlande)
* 17e DCFS 2015 Waterloo (Ontario)
* 18e DCFS 2016 Bucarest (Roumanie)
* 19e DCFS 2017 Milan (Italie)

Depuis 2006, le Steering Committee de DCFS est présidé par Giovanni Pighizzini.

## Impact

À titre d’exemple, le workshop DCFS 2016 comportait quatre conférences invités et 13 articles réguliers. Il a eu 21 propositions de communications, soumises par 47 auteurs de 15 pays différents. Le taux d’acceptation est de 60 % environ.

