DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an annual
academic conference
An academic conference or scientific conference (also congress, symposium, workshop, or meeting) is an Convention (meeting), event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic jou ...
in the
field of
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
.
Beginning with the 2011 edition, the proceedings of the workshop appear in the series
Lecture Notes in Computer Science
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973.
Overview
The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials ...
. 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
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, and of
Information and Computation
''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , t ...
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
ICALP, the International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe. Like most theoret ...
,
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
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
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
The International Federation for Information Processing (IFIP) is a global organisation for researchers and professionals working in the field of computing to conduct research, develop standards and promote information sharing.
Established in 19 ...
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
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
This is a list of academic conferences in computer science. Only conferences with separate articles are included; within each field, the conferences are listed alphabetically by their short names.
General
* FCRC – Federated Computing Resear ...
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