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
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity c ...
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
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity c ...
.
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
tsfield 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.
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 editionaccessed Feb 9, 2009.
* 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 editionaccessed Nov 24, 2009.
* Electronic Proceedings in Theoretical Computer Science
official website
*
*
* 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
{{Authority control
Theoretical computer science conferences
Formal languages