Descriptional Complexity of Formal Systems
DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an annual academic conference in the
field of computer science.
Beginning with the 2011 edition, the proceedings of the workshop appear in the series Lecture Notes in Computer Science. Already since the very beginning, extended versions of selected papers are published as special issues of the International Journal of Foundations of Computer Science, the Journal of Automata, Languages and Combinatorics, of Theoretical Computer Science, and of Information and Computation In 2002 DCFS was the result of the merger of the workshops DCAGRS and FDSR. The workshop is often collocated with international conferences in related fields, such as ICALP, DLT and CIAA.
Topics of the workshop
Typical topics include:- 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 objects
- state complexity of finite automata
- descriptional complexity in resource-bounded or structure-bounded environments
- structural complexity
- descriptional complexity of formal systems for applications
- descriptional complexity aspects of nature-motivated architectures and unconventional models of computing
- Kolmogorov–Chaitin complexity and descriptional complexity
Significance
In a survey on descriptional complexity, state that "since more than a decade the Workshop on 'Descriptional Complexity of Formal Systems', has contributed substantially to the development of field of research." In a talk on the occasion of the 10th anniversary of the workshop, gave an overview about trends and directions in research papers presented at DCFS.History of the workshop
Since 2006, the Chair of the Steering Committee of the DCFS workshop series is Giovanni Pighizzini.Basic information on each DCFS event, as well as on its precursors, DCAGRS and FSDR, is included in the following table.
| Event | Location | PC chairs | Proceedings | Special issue |
| Magdeburg, Germany | Jürgen Dassow Detlef Wotschke | Journal of Automata, Languages and Combinatorics 5, 2000 | ||
| 2nd DCAGRS 2000 | London, Ontario, Canada | Helmut Jürgensen | Journal of Automata, Languages and Combinatorics 6, 2001 | |
| 3rd DCAGRS 2001 | Vienna, Austria | Jürgen Dassow Detlef Wotschke | Journal of Automata, Languages and Combinatorics 7, 2002 | |
| 1st FSDR 1998 | Paderborn, Germany | |||
| 2nd FSDR 1999 | Boca Raton, Florida, USA | |||
| 3rd FSDR 2000 | San Jose, California, USA | |||
| London, Ontario, Canada | Jürgen Dassow Helmut Jürgensen Detlef Wotschke | Journal of Automata, Languages and Combinatorics 9, 2004 | ||
| Budapest, Hungary | Erzsébet Csuhaj-Varjú Chandra Kintala Detlef Wotschke | Theoretical Computer Science 330, 2005 | ||
| London, Ontario, Canada | Lucian Ilie Detlef Wotschke | International Journal of Foundations of Computer Science 16, 2005 | ||
| Como, Italy | Giovanni Pighizzini Detlef Wotschke | Journal of Automata, Languages and Combinatorics 12, 2007 | ||
| Las Cruces, New Mexico, USA | Hing Leung Giovanni Pighizzini | Theoretical Computer Science 387, 2007 | ||
| High Tatras, Slovakia | Viliam Geffert Giovanni Pighizzini | International Journal of Foundations of Computer Science 19, 2008 | ||
| Charlottetown, Canada | Cezar Câmpeanu Giovanni Pighizzini | Theoretical Computer Science 410, 2009. | ||
| Magdeburg, Germany | Jürgen Dassow Giovanni Pighizzini | Journal of Automata, Languages and Combinatorics, 15, 2010 | ||
| Saskatoon, Saskatchewan, Canada | Ian McQuillan Giovanni Pighizzini | International Journal of Foundations of Computer Science, 23, 2012 | ||
| Giessen, Germany | Markus Holzer Martin Kutrib Giovanni Pighizzini | LNCS 6808 | Theoretical Computer Science, 449, 2012 | |
| Braga, Portugal | Martin Kutrib Nelma Moreira Rogério Reis | LNCS 7386 | Journal of Automata, Languages and Combinatorics, 17, 2012 | |
| London, Ontario, Canada | Helmut Jürgensen Rogério Reis | LNCS 8031 | International Journal of Foundations of Computer Science, 25, 2014 | |
| Turku, Finland | Helmut Jürgensen Juhani Karhumäki Alexander Okhotin | LNCS 8614 | Theoretical Computer Science, 610, 2016 | |
| Waterloo, Ontario, Canada. | Alexander Okhotin Jeffrey O. Shallit | LNCS 9118 | Information and Computation, to appear | |
| Bucharest, Romania | Cezar Câmpeanu Jeffrey O. Shallit | LNCS 9777 | Journal of Automata, Languages and Combinatorics, to appear | |
| Milan, Italy | Cezar Câmpeanu Giovanni Pighizzini |