Descriptional Complexity of
Formal Systems

About DCFS Important Dates Invited Speakers Committees Submissions Registration Accepted Papers Program (pdf) DCFS campus map (pdf) Electronic Proceedings at EPTCS

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:

• CIAA - Conference on Implementation and Application of Automata, August 12-15, 2010, in Winnipeg, Canada
• DLT - Developments in Language Theory, August 17-20, 2010, in London, Canada

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

Topics

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