Descriptional Complexity of Formal Systems
Description
This book constitutes the refereed proceedings of the 27th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2026, held in Kingston, ON, Canada, during August 9-11, 2026.
The 13 full papers included in this book were carefully reviewed and selected from 14 submissions. They focus on the Descriptional Complexity of Automata, Grammars, and Related Structures, Formal Descriptions and Software Reliability.
More details
Content
.- Invited Talks.
.- The Power and Limits of Population Protocols.
.- Formal Language Theory and Transformers.
.- Representing Concepts with Small Teaching Sets.
.- Contributed Papers.
.- 2-word-p-representable Graphs.
.- Largest Finite Optimal Existential and Universal Widths of unary AFAs.
.- On the Average State Complexity of Shuffle Ideals.
.- Quantifying Distance From Simplicity.
.- Some Descriptional Complexity Results for Context-Conditional Grammars.
.- Exact Accepting-State Spectrum for Reversal of Permutation Automata.
.- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata.
.- The Boundary of Closed and Ideal Languages.
.- State-Limited Inductive Inference of Cellular Automata.
.- Bounds on the number of ?-palindromes in ?-conjugates.
.- State Complexity of Shifts of the Fibonacci Word.
.- On the Complexity of Multi-entry DFAs.
.- Determinizing k-path input-driven PDAs.