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
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.