Descriptional Complexity of Formal Systems

Descriptional Complexity of Formal Systems
Abbreviation	DCFS
Discipline	Automata theory and formal languages
Publication details
Publisher	Lecture Notes in Computer Science
History	1999–
Frequency	annual

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, Holzer & Kutrib (2010) 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, Dassow (2009) 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:

Period	Chair
1999 - 2005	Detlef Wotschke
2006 - 2017	Giovanni Pighizzini
2017 -	Martin Kutrib

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 Archived 2016-03-03 at the Wayback Machine	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 Archived 2017-11-13 at the Wayback Machine	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 Archived 2016-03-05 at the Wayback Machine	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

• The list of computer science conferences contains other academic conferences in computer science.

References

• Bianca Truthe: "Report on DCFS 2008." Bulletin of the EATCS 96:160-161, October 2008. Online edition accessed Feb 9, 2009.
• Dassow, Jürgen (2009). "10 Years DCFS" (PDF). Talk held at the 11th DCFS in Magdeburg, Germany, July 6–9, 2009.
• Ian McQuillan: "Report on DCFS 2009." Bulletin of the EATCS 99:185-187, October 2009. Online edition accessed Nov 24, 2009.
• Electronic Proceedings in Theoretical Computer Science, official website.
• Holzer, Markus; Kutrib, Martin (2010), "Descriptional Complexity — An Introductory Survey", in Martín-Vide, Carlos (ed.), Scientific Applications of Language Methods, Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, vol. 2, Imperial College Press, pp. 1–58, ISBN 978-1-84816-544-1, archived from the original (PDF) on March 25, 2012, retrieved March 16, 2011

• McQuillan, Ian; Pighizzini, Giovanni (2010), McQuillan, Ian; Pighizzini, Giovanni (eds.), "Preface", Electronic Proceedings in Theoretical Computer Science, 31, arXiv:1008.1270, doi:10.4204/EPTCS.31, S2CID 24469647
• Andreas Malcher: "Report on DCFS 2012." Bulletin of the EATCS 108:168-169, October 2012. Online edition.

External links

• Descriptional Complexity of Formal Systems: official website