Steering Committee 

Past Editions


Special Issues

Descriptional Complexity of
Formal Systems (DCFS)

DCFS 2020 collected papers - Call for Papers

  • 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.
  • The volume will be published in the series Lecture Notes in Computer Science.
  • If interested the authors of accepted papers have the option of giving a short presentation during DCFS 2021.




  • Paper submission deadline: June 29, 2020 (extended)
  • Author notification: August 18, 2020 (extended)
  • Final version: September 3, 2020 (extended)


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.
  • Universality and reversibility.
  • Nature-motivated (bio-inspired) architectures and unconventional models of computing.
  • Blum Static (Kolmogorov/Chaitin) complexity, algorithmic information.


  • Cezar Câmpeanu, University of Prince Edward Island, Canada
  • Pawel Gawrychowski, University of Wrocław, Poland
  • Dora Giammarresi, Università di Roma, Italy
  • Galina Jirásková, Slovak Academy of Sciences, Košice, Slovakia, co-chair
  • Martin Kutrib, University of Giessen, Germany
  • Florin Manea, University of Göttingen, Germany
  • František Mráz, Charles University in Prague, Czech Republic
  • Dana Pardubská, Comenius University, Bratislava, Slovak Republic
  • Andrei Păun, University of Bucharest, Romania
  • Giovanni Pighizzini, University of Milan, Italy, co-chair
  • Rogério Reis, Universidade do Porto, Portugal
  • Michel Rigo, University of Liège, Belgium
  • Marinella Sciortino, University of Palermo, Italy
  • Shinnosuke Seki, The University of Electro-Communications, Chofu, Japan
  • Klaus Sutner, Carnegie Mellon University, USA
  • Bianca Truthe, University of Giessen, Germany
  • György Vaszil, University of Debrecen, Hungary


  • Authors are invited to submit papers of no more than 12 pages in LNCS style, and including bibliography in BibTeX using bibliography style splncs04.bst.
  • Proofs omitted due to space constraints may be put into an appendix to be read by the reviewers at their discretion.
  • Moreover, to make the work of reviewers easier, relevant papers needed for a better understanding of the submitted paper should be appended at the end, too.
  • Simultaneous submissions to other conferences or workshops with published proceedings and submitting previously published papers are not allowed.
  • Papers should be submitted electronically as a PDF document via EasyChair at the following link:

Andreas Malcher, 12.11.2020