DCFS 2023: 25th International Conference on Descriptional Complexity of Formal Systems University of Potsdam Potsdam, Germany, July 4-6, 2023 |
Conference website | https://www.cs.uni-potsdam.de/dcfs2023/ |
Submission link | https://easychair.org/conferences/?conf=dcfs2023 |
Abstract registration deadline | March 10, 2023 |
Submission deadline | March 13, 2023 |
The workshop is organized by the Department of Computer Science of the University of Potsdam, Germany, and by the IFIP Working Group 1.02 "Descriptional Complexity". As long as sanitary conditions allow, the conference will take place on-site.
Invited Speakers
Pascal Caron (Université de Rouen, France): Operational state complexity revisited: the contribution of Monsters and Modifiers
Friedrich Otto (Univerity of Kassel, Germany): On the influence of the various parameters of the restarting automaton on its expressive capacity and descriptional complexity
Rogério Reis (Universidade do Porto, Portugal): Size matters, but let's have it on average
Jürgen Dassow (Otto-von-Guericke University of Magdeburg): Ceremonial address on the occasion of the 25th edition of DCFS
Submission Guidelines
Authors are invited to submit original research papers in electronic form. All submissions should be prepared according to the the details explained at the web-page of DCFS 2023 (https://www.cs.uni-potsdam.de/dcfs2023/) and will go through a usual review process. Simultaneous submissions to other conferences or workshops with published proceedings are not allowed.
List of Topics
Original research papers concerning the descriptional complexity of formal systems and structures(and its applications) are sought for DCFS 2023.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 modeling or in modeling natural languages -- and their complexity constraints.
- Co-operating formal systems.
- Size or structural complexity of formal systems for modeling 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.
Committees
Program Committee
- Henning Bordihn (University of Potsdam, Germany) - co-chair
- Szilárd Zsolt Fazekas (Akita University, Japan)
- Henning Fernau (University of Trier, Germany)
- Yo-Sub Han (Yonsei University, South Korea)
- Michal Hospodár (Slovak Academy of Sciences, Kosice, Slovakia)
- Szabolcs Iván (University of Szeged, Hungary)
- Galina Jirásková (Slovak Academy of Sciences, Košice, Slovakia)
- Stavros Konstantinidis (Saint Mary's University, Halifax, Canada)
- Orna Kupferman (Hebrew University, Israel)
- Sylvain Lombardy (University of Bordeaux, France)
- Andreas Malcher (Universität Giessen, Germany)
- Carlo Mereghetti (Università degli Studi di Milano, Italy)
- Nelma Moreira (Universidade do Porto, Portugal)
- Dana Pardubska (Comenius Unversity, Bratislava, Slovak Republic)
- Giovanni Pighizzini (University of Milan, Italy)
- Kai Salomaa (Queen's University, Canada)
- Shinnosuke Seki (The University of Electro-Communications, Chofu, Japan)
- Petr Sosik (Silesian University Opava, Czech Republic)
- Nicholas Tran (Santa Clara University, USA) - co-chair
- György Vaszil (University of Debrecen, Hungary) co-chair
Organizing committee
- Henning Bordihn (University of Potsdam, Germany)
- Tim Richter (University of Potsdam, Germany)
- Alexandra Roy (University of Potsdam, Germany)
Publication
DCFS 2023 proceedings will be published as a volume in the series Lecture Notes in Computer Science (LNCS), Springer-Verlag.
A special issue of the journal Information and Computation will be devoted to revised and extended versions of selected papers of the conference.
Venue
The conference will be held in Potsdam, Germany.
Contact
All questions about submissions should be emailed to Henning Bordihn <henning@cs.uni-potsdam.de>.