Descriptional Complexity of Formal Systems

This volume presents key findings from the 23rd International Conference on Descriptional Complexity of Formal Systems, showcasing significant research in computational models.

The proceedings of the 23rd International Conference on Descriptional Complexity of Formal Systems, DCFS 2021, are presented in this book. Originally scheduled to take place in Seoul, South Korea, in June 2021, the conference was ultimately canceled due to the COVID-19 pandemic. Despite this setback, the volume includes 16 full papers that were meticulously reviewed and selected from a total of 21 submissions.

The focus of Descriptional Complexity of Formal Systems is on various aspects of descriptional complexity, exploring the costs associated with representing objects within different computational models. These models include Turing machines, pushdown automata, finite automata, and grammars, which are essential for understanding computational theory and complexity.

This collection of papers serves as a valuable resource for researchers and practitioners in the field, providing insights into recent advancements and ongoing challenges in descriptional complexity. The work presented reflects the innovative thinking and rigorous analysis typical of the conference, making it a significant contribution to the literature on formal systems.