Descriptional Complexity of Formal Systems
From Wikipedia, the free encyclopedia
DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an is an annual academic conference in the field of computer science held under the auspices of the International Federation for Information Processing Working Group 1.2 on Descriptional Complexity. Selected Proceedings are regularly published in the international journals Journal of Automata, Languages and Combinatorics and Theoretical Computer Science. In 2002 DCFS was the result of the merger of DCAGRS (Descriptional Complexity of Automata, Grammars and Related Structures) and FDSR (Formal Descriptions and Software Reliability). The workshop often collocated with international conferences in related fields, such as ICALP, DLT and CIAA.
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
[edit] History of the Workshop
- 10th DCFS 2008 in Charlottetown, Canada
- 9th DCFS 2007 in High Tatras, Slovakia
- Special Issue: International Journal of Foundations of Computer Science, to appear.
- 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 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
- 1st DCAGRS 1999 in Magdeburg, Germany.
- 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
