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 , and or Theoretical Computer Science . In 2002 DCFs were 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 of or in collocated with international conferences in related fields, zoals ICALP , DLT and CIAA .

Topics of the workshop

Typical topics include:

  • verschillende maatregelen or descriptional complexity or automata, grammars, languages and or related systems
  • trade-offs tussen descriptional complexity and mode of operation
  • circuit complexity or Boolean functions and related maatregelen
  • succinctness or description of (finite) objects
  • descriptional complexity in resource-bounded or structure-bounded environments
  • structural complexity
  • descriptional complexity or formal systems for applications (eg software reliability, software and hardware testing, modeling of natural languages)
  • descriptional complexity aspects of nature-Motivated (bio-inspired) architectures and unconventional models of computing
  • Kolmogorov-Chaitin complexity and descriptional complexity

As industry leaders, 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) states that ‘since morethan a decade the Workshop on “Descriptional Complexity of Formal Systems (DCFs), […] has Contributed Substantially to the development of [zijn] field of research. ” In a talk on the occasion of the 10th anniversary of the workshop, Dassow (2009) showing an overview about trends and directions in research papers presented at DCFs.

History of the workshop

  • 18th DCFs 2015 18th DCFs 2016 Bucharest, Romania
  • 17th DCFs 2015 in Waterloo, Ontario, Canada.
Proceedings: Lecture Notes in Computer Science, vol. 9118
  • 16th DCFs 2014 in Turku, Finland.
Proceedings: Lecture Notes in Computer Science, vol. 8614
Special Issue: Theoretical Computer Science, ACM Press.
  • 15th DCFs 2013 in London, Ontario, Canada.
Proceedings: Lecture Notes in Computer Science, vol. 8031
  • 14th DCFs 2012 in Braga, Portugal
Proceedings: Lecture Notes in Computer Science, vol. 7386
Special Issue: Journal of Automata, Languages ​​and Combinatorics, ACM Press.
  • 13th DCFs 2011 in Giessen, Germany
Proceedings: Lecture Notes in Computer Science, vol. 6808
Special Issue: Theoretical Computer Science, 449, 2012
  • 12th DCFs 2010 in Saskatoon (Saskatchewan), Canada
Special Issue: International Journal of Foundations of Computer Science, 23 (1), 2012.
  • 11th DCFs 2009 in Magdeburg, Germany
Special Issue: Journal of Automata, Languages ​​and Combinatorics, 15 (1-2), 2010.
  • 10th DCFs 2008 in Charlottetown, Canada
Special Issue: Theoretical Computer Science 410 (35), 2009.
  • 9th DCFs 2007 in High Tatras, Slovakia
Special Issue: International Journal of Foundations of Computer Science 19 (4), 2008.
  • 8th DCFs 2006 in Las Cruces, New Mexico, USA
Special Issue: Theoretical Computer Science 387 (2), 2007
  • 7th DCFs 2005 in Como, Italy
Special Issue: Journal of Automata, Languages ​​and Combinatorics 12 (1/2), 2007
  • 6th DCFs 2004 London (Ontario), Canada
Special Issue: International Journal of Foundations of Computer Science 16 (5), 2005
  • 5th DCFs 2003 in Budapest, Hungary
Special Issue: Theoretical Computer Science 330 (2), 2005
  • 4th DCFs 2002 in London (Ontario), Canada
Special Issue: Journal of Automata, Languages ​​and Combinatorics 9 (2/3), 2004

DCAGRS (predecessor of DCFs)

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

FSDR (other predecessor or DCFs)

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

References

  • Bianca Truthe: “Report on DCFs 2008.” Bulletin of the EATCS 96 : 160-161, October 2008. Online edition Accessed February 9, 2009.
  • Jürgen Dassow: “10 Years DCFs.” Talk hero 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, Mark; Kutrib, Martin (2010), “Descriptional Complexity – An Introductory Survey” (PDF) , in Martin-Vide, Carlos, Scientific Applications of Language Methods , Mathematics, Computing, Language, and Life: Frontiers in Computational Linguistics and Language Theory, 2 Imperial College Press, pp. 1-58, ISBN  978-1-84816-544-1 , retrieved March 16, 2011
  • McQuillan, Ian; Pighizzini, Giovanni (2010), McQuillan, Ian; Pighizzini, Giovanni, eds., “Preface”, Electronic Proceedings in Theoretical Computer Science , Electronic Proceedings in Theoretical Computer Science, 31 , arXiv : 1008.1270Freely accessible , doi : 10.4204 / EPTCS.31
  • Andreas Malcher: “Report on DCFs 2012.” Bulletin of the EATCS 108 : 168-169, October 2012. Online edition .