Descriptional Complexity of Formal Systems

Descriptional Complexity of Formal Systems
Descriptional Complexity of Formal Systems
Abbreviation DCFS
Discipline Automata theory and formal languages
Publication details
Publisher Electronic Proceedings in Theoretical Computer Science (International)
History 1999–
Frequency annual

DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an is an annual academic conference in the field of computer science.

Starting with the 2009 edition, the proceedings of the workshop appear in the series Electronic Proceedings in Theoretical Computer Science, an open access series. 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, and of Theoretical Computer Science. 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.

Contents

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

Special Issue: International Journal of Foundations of Computer Science, announced (as of August 2010)[1]
Special Issue: Journal of Automata, Languages and Combinatorics, announced (as of January 2009)
Special Issue: Theoretical Computer Science 410(35), 2009.
Special Issue: International Journal of Foundations of Computer Science 19(4), 2008.
Special Issue: Theoretical Computer Science 387(2), 2007
Special Issue: Journal of Automata, Languages and Combinatorics 12(1/2), 2007
Special Issue: International Journal of Foundations of Computer Science 16(5), 2005
Special Issue: Theoretical Computer Science 330(2), 2005
Special Issue: Journal of Automata, Languages and Combinatorics 9(2/3), 2004

DCAGRS (predecessor of DCFS)

  • 3rd DCAGRS 2001 in Vienna
Special Issue: Journal of Automata, Languages and Combinatorics 7(4), 2002
  • 2nd DCAGRS 2000 in London (Ontario), Canada.
Special Issue: Journal of Automata, Languages and Combinatorics 6(4), 2001
Special Issue: Journal of Automata, Languages and Combinatorics 5(3), 2000

FSDR (other predecessor of DCFS)

  • 3rd FSDR 2000 San Jose (California), USA
  • 2nd FSDR 1999 Boca Raton (Florida), USA
  • 1st FSDR 1998 Paderborn, Germany

See also

Notes

  1. ^ McQuillan & Pighizzini (2010)

References

  • McQuillan, Ian; Pighizzini, Giovanni (2010), Preface, in McQuillan, Ian; Pighizzini, Giovanni, , Electronic Proceedings in Theoretical Computer Science, Electronic Proceedings in Theoretical Computer Science 31, arXiv:1008.1270, doi:10.4204/EPTCS.31 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List of computer science conferences — This is a list of academic conferences in computer science. Most of these academic conferences are annual or bi annual events.The order with which the conferences are listed in their respective fields corresponds to a rough and non authoritative… …   Wikipedia

  • DCFS — The following concepts can be abbreviated DCFS Department of Children Family Services, the name of a governmental agency in some states in the United States Descriptional Complexity of Formal Systems, a computer science conference See also… …   Wikipedia

  • Äquivalenzproblem — Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Definitionen von zwei Sprachen L1 und L2 äquivalent sind, also L1 = L2 gilt. So können die Sprachen durch Grammatiken, oder… …   Deutsch Wikipedia

  • Didactics of Informatics — Didactics of computer science (didactics of informatics) is a sub field of computer science (informatics). Since 1960 experts of higher education, the pioneers of didactics of computer science, are developing guidelines and curricula… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”