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.

Descriptional Complexity of Formal Systems
AbbreviationDCFS
DisciplineAutomata theory and formal languages
Publication details
PublisherLecture Notes in Computer Science
History1999–
Frequencyannual

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

edit

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

edit

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

edit

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

edit

References

edit
  • Bianca Truthe: "Report on DCFS 2008." Bulletin of the EATCS 96:160-161, October 2008. Online edition[permanent dead link] 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
edit