The 22nd International Conference on Descriptional Complexity of Formal Systems (DCFS 2020) was expected to be organized by Rudolf Freund at the TU Wien as part of the Summer of Formal Languages 2020 in Wien, Austria, and by the IFIP Working Group 1.02 "Descriptional Complexity”.
Unfortunately, due to the development of the crisis caused by the Corona virus, the conference had to be canceled as an event with the participants meeting in person in Wien. However, in order to allow researchers in the area of descriptional complexity to still present their recent results in some form, the DCFS steering committee decided to prepare a volume, collecting papers which will be selected by a committee after a standard review process.
Call For Paper
Submissions concerning the descriptional complexity of formal systems and structures (and its applications) are invited for DCFS 2020 collected papers. Original papers are sought in all aspects of descriptional complexity, topics include, but are not limited to:
Automata, grammars, languages and other formal systems; various modes of operations and complexity measures.
Succinctness of description of objects, state-explosion-like phenomena.
Circuit complexity of Boolean functions and related measures.
Size complexity of formal systems.
Structural complexity of formal systems.
Trade-offs between computational models and mode of operation.
Applications of formal systems - for instance in software and hardware testing, in dialogue systems, in systems modelling or in modelling natural languages - and their complexity constraints.
Co-operating formal systems.
Size or structural complexity of formal systems for modelling natural languages.
Complexity aspects related to the combinatorics of words.
Descriptional complexity in resource-bounded or structure-bounded environments.
Structural complexity as related to descriptional complexity.
Frontiers between decidability and undecidability.