About DCFS

DCFS 2010, Descriptional Complexity of Formal Systems, will be held in Saskatoon, Saskatchewan, Canada, from August 8 – 10, 2010.

DCFS 2010 will be jointly organized by the IFIP Working Group 1.2 on Descriptional Complexity and by the Department of Computer Science at the University of Saskatchewan.

DCFS 2010 takes place immediately before:

Thus, one can attend all of DCFS, CIAA and DLT within a two week period.


Topics include, but are not limited to:

  • various measures of descriptional complexity of automata, grammars, languages, and of related systems
  • trade-offs between different formal systems and/or different modes of operation (e.g., determinism and nondeterminism) with respect to descriptional complexity
  • 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 complexity and its relation to descriptional complexity