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.
- The Steering Committee is also considering the possibility of offering to
the authors of accepted papers the option of giving a short presentation
during DCFS 2021.
- Paper submission deadline: June 15, 2020
- Author notification: July 31, 2020
- Final version: August 15, 2020
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
- Complexity aspects related to the combinatorics of words.
- Descriptional complexity in resource-bounded or structure-bounded
- 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
- Dora Giammarresi, Università di Roma, Italy
- Pawel Gawrychowski, University of Wrocław, Poland
- 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
- 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
- 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: