Descriptional Complexity of Formal Systems explained
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 (Descriptional Complexity of Automata, Grammars and Related Structures) and FDSR (Formal Descriptions and Software Reliability). 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 (finite) objects
- state complexity of finite automata
- 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–Chaitin complexity and descriptional complexity
As such, the topics of the conference overlap with those of the International Federation for Information Processing Working Group 1.2 on descriptional complexity.
Significance
In a survey on descriptional complexity, state that "since more than a decade the Workshop on 'Descriptional Complexity of Formal Systems' (DCFS), [...] has contributed substantially to the development of [its] 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
Chairs of the Steering Committee of the DCFS workshop series:
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 |
|---|
| 1st DCAGRS 1999 | Magdeburg, Germany | Jürgen Dassow
Detlef Wotschke | | Journal of Automata, Languages and Combinatorics 5(3), 2000 |
| 2nd DCAGRS 2000 | London, Ontario, Canada | Helmut Jürgensen | | Journal of Automata, Languages and Combinatorics 6(4), 2001 |
| 3rd DCAGRS 2001 | Vienna, Austria | Jürgen Dassow
Detlef Wotschke | | Journal of Automata, Languages and Combinatorics 7(4), 2002 |
| 1st FSDR 1998 | Paderborn, Germany | | | |
| 2nd FSDR 1999 | Boca Raton, Florida, USA | | | |
| 3rd FSDR 2000 | San Jose, California, USA | | | |
| 4th DCFS 2002 | London, Ontario, Canada | Jürgen Dassow
Helmut Jürgensen
Detlef Wotschke | | Journal of Automata, Languages and Combinatorics 9(2/3), 2004 |
| 5th DCFS 2003 | Budapest, Hungary | Erzsébet Csuhaj-Varjú
Chandra Kintala
Detlef Wotschke | | Theoretical Computer Science 330(2), 2005 |
| 6th DCFS 2004 | London, Ontario, Canada | Lucian Ilie
Detlef Wotschke | | International Journal of Foundations of Computer Science 16(5), 2005 |
| 7th DCFS 2005 | Como, Italy | Giovanni Pighizzini
Detlef Wotschke | | Journal of Automata, Languages and Combinatorics 12(1/2), 2007 |
| 8th DCFS 2006 | Las Cruces, New Mexico, USA | Hing Leung
Giovanni Pighizzini | | Theoretical Computer Science 387(2), 2007 |
| 9th DCFS 2007 | High Tatras, Slovakia | Viliam Geffert
Giovanni Pighizzini | | International Journal of Foundations of Computer Science 19(4), 2008 |
| 10th DCFS 2008 | Charlottetown, Canada | Cezar Câmpeanu
Giovanni Pighizzini | | Theoretical Computer Science 410(35), 2009. |
| 11th DCFS 2009 | Magdeburg, Germany | Jürgen Dassow
Giovanni Pighizzini | EPTCS 3 | Journal of Automata, Languages and Combinatorics, 15(1-2), 2010 |
| 12th DCFS 2010 | Saskatoon, Saskatchewan, Canada | Ian McQuillan
Giovanni Pighizzini | EPTCS 31 | International Journal of Foundations of Computer Science, 23(1), 2012 |
| 13th DCFS 2011 | Giessen, Germany | Markus Holzer
Martin Kutrib
Giovanni Pighizzini | LNCS 6808 | Theoretical Computer Science, 449, 2012 |
| 14th DCFS 2012 | Braga, Portugal | Martin Kutrib
Nelma Moreira
Rogério Reis | LNCS 7386 | Journal of Automata, Languages and Combinatorics, 17(2-4), 2012 |
| 15th DCFS 2013 | London, Ontario, Canada | Helmut Jürgensen
Rogério Reis | LNCS 8031 | International Journal of Foundations of Computer Science, 25(7), 2014 |
| 16th DCFS 2014 | Turku, Finland | Helmut Jürgensen
Juhani Karhumäki
Alexander Okhotin | LNCS 8614 | Theoretical Computer Science, 610, 2016 |
| 17th DCFS 2015 | Waterloo, Ontario, Canada | Alexander Okhotin
Jeffrey O. Shallit | LNCS 9118 | Information and Computation, 259(2), 2018 |
| 18th DCFS 2016 | Bucharest, Romania | Cezar Câmpeanu
Jeffrey O. Shallit | LNCS 9777 | Journal of Automata, Languages and Combinatorics, 22(1-3), 2017 |
| 19th DCFS 2017 | Milan, Italy | Cezar Câmpeanu
Giovanni Pighizzini | LNCS 10316 | International Journal of Foundations of Computer Science, 30(6-7), 2019 |
| 20th DCFS 2018 | Halifax, NS, Canada | Stavros Konstantinidis
Giovanni Pighizzini | LNCS 10952 | Theoretical Computer Science, 798, 2019 |
| 21st DCFS 2019 | Košice, Slovakia | Galina Jirásková
Stavros Konstantinidis | LNCS 11612 | Information and Computation, to appear |
| 22nd DCFS 2020 | Vienna, Austria (cancelled) | Galina Jirásková
Giovanni Pighizzini | LNCS 12442
(collected papers) | Journal of Automata, Languages and Combinatorics, in progress | |
See also
References
External links
