27th Edition

International Conference on
Descriptional Complexity of Formal Systems

Advancing research in the descriptional complexity of formal systems and structures through collaboration between academia and industry

Dates
August 9-11, 2026
Location
Queen's University
City
Kingston, Ontario, Canada
View Program Learn More
Scroll to explore
Welcome

About DCFS 2026

The premier international conference on descriptional complexity of formal systems and structures

DCFS 2026 will be held in Kingston, Ontario, Canada, on August 9-11, 2026. The conference is organized jointly by the School of Computing at Queen's University and by the IFIP Working Group 1.02 "Descriptional Complexity".

The International Conference on Descriptional Complexity of Formal Systems (DCFS) is a premier venue for research on the descriptional complexity of formal systems and structures, with applications across theoretical computer science and related fields.

🤝 Joint Organization

IFIP

This conference is a collaboration between Queen's University's School of Computing and the IFIP Working Group 1.02 "Descriptional Complexity", bringing together leading researchers in formal systems and descriptional complexity.

📚 Publication

Springer LNCS

Conference proceedings will be published by Springer-Verlag in the renowned Lecture Notes in Computer Science (LNCS) series.

Extended versions of selected papers from the conference will be invited for consideration in a special issue of International Journal of Foundations of Computer Science.

Co-located with CIAA 2026 (August 5-8, 2026)

Timeline

Important Dates

March 13, 2026 → March 20, 2026
Paper Submission Deadline
April 17, 2026 → April 24, 2026
Author Notification
May 1, 2026
Camera-Ready Deadline
August 9-11, 2026
Conference
Program

Schedule of Talks

All conference sessions will be held in Room 2109, Biosciences Complex, Queen's University (116 Barrie Street)

Download Schedule (PDF) Conference Poster (PDF) Conference Proceedings (Springer)

Sunday, August 9

Time Event
9:30am – 10:30am Registration / Breakfast (weekend late start)
10:30am – 11:00am Conference Opening
11:00am – 12:00pm Invited Talk 1
Michaël Cadilhac
"Formal Language Theory and Transformers"
12:00pm – 1:30pm Lunch
1:30pm – 2:30pm Session 1
Samuel German
"Exact Accepting-State Spectrum for Reversal of Permutation Automata"
John Alajaji and Kai Salomaa
"Largest Finite Optimal Existential and Universal Widths of unary AFAs"
2:30pm – 3:00pm Coffee Break
3:00pm – 4:00pm Session 2
Guilherme Duarte, Markus Holzer, Nelma Moreira and Rogério Reis
"On the Average State Complexity of Shuffle Ideals"
Jozef Jirásek and Galina Jirásková
"The Boundary of Closed and Ideal Languages"
4:00pm – 4:15pm Business Meeting

Monday, August 10

Time Event
8:00am – 9:30am Registration / Breakfast
9:30am – 10:30am Invited Talk 2
Sandra Zilles
"Representing Concepts with Small Teaching Sets"
10:30am – 11:00am Coffee Break
11:00am – 12:00pm Session 3
Henning Fernau
"Generalized word-representable graphs" (informal talk)
Duncan Adamson, Amanita Dietz, Pamela Fleischmann, Annika Huch and Silas Cato Sacher
"2-word-π-representable Graphs"
12:00pm – 1:30pm Lunch
1:30pm – 2:30pm Session 4
Samuel German
"A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata"
Nelma Moreira, Gonçalo Teixeira and Rogério Reis
"On the Complexity of Multi-entry DFAs"
2:30pm – 3:00pm Coffee Break
Evening Excursion and Dinner

Tuesday, August 11

Time Event
8:00am – 9:30am Registration / Breakfast
9:30am – 10:30am Invited Talk 3
Michael Blondin
"The Power and Limits of Population Protocols"
10:30am – 11:00am Coffee Break
11:00am – 12:00pm Session 5
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi Raman
"Quantifying Distance From Simplicity"
Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman and Silas Cato Sacher
"Some Descriptional Complexity Results for Context-Conditional Grammars"
12:00pm – 1:30pm Lunch
1:30pm – 2:30pm Session 6
Martin Kutrib, Ian McQuillan, Priscilla Raucci and Matthias Wendlandt
"State-Limited Inductive Inference of Cellular Automata"
Mohammad Zakzok and Kai Salomaa
"Determinizing k-path input-driven PDAs"
2:30pm – 3:00pm Coffee Break
3:00pm – 4:00pm Session 7
Anuran Maity
"Bounds on the number of θ-palindromes in θ-conjugates"
Delaram Moradi, Pierre Popoli, Jeffrey Shallit and Ingrid Vukusic
"State Complexity of Shifts of the Fibonacci Word"
4:00pm Conference Closing
Papers

Accepted Papers

Duncan Adamson, Amanita Dietz, Pamela Fleischmann, Annika Huch and Silas Cato Sacher. 2-word-π-representable Graphs
John Alajaji and Kai Salomaa. Largest Finite Optimal Existential and Universal Widths of unary AFAs
Guilherme Duarte, Markus Holzer, Nelma Moreira and Rogério Reis. On the Average State Complexity of Shuffle Ideals
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi Raman. Quantifying Distance From Simplicity
Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman and Silas Cato Sacher. Some Descriptional Complexity Results for Context-Conditional Grammars
Samuel German. Exact Accepting-State Spectrum for Reversal of Permutation Automata
Samuel German. A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
Jozef Jirasek and Galina Jiraskova. The Boundary of Closed and Ideal Languages
Martin Kutrib, Ian McQuillan, Priscilla Raucci and Matthias Wendlandt. State-Limited Inductive Inference of Cellular Automata
Anuran Maity. Bounds on the number of θ-palindromes in θ-conjugates
Delaram Moradi, Pierre Popoli, Jeffrey Shallit and Ingrid Vukusic. State Complexity of Shifts of the Fibonacci Word
Nelma Moreira, Gonçalo Teixeira and Rogério Reis. On the Complexity of Multi-entry DFAs
Mohammad Zakzok and Kai Salomaa. Determinizing k-path input-driven PDAs
Research Areas

Principal Topics

Submissions concerning the descriptional complexity of formal systems and structures (and its applications) are invited for DCFS 2026. 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 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.
Keynotes

Invited Speakers

Michael Blondin
Michael Blondin
Université de Sherbrooke
"The Power and Limits of Population Protocols"
Visit Website →
Michaël Cadilhac
Michaël Cadilhac
DePaul University
"Formal Language Theory and Transformers"
Visit Website →
Sandra Zilles
Sandra Zilles
University of Regina
"Representing Concepts with Small Teaching Sets"
Visit Website →
Organization

Committees

Program Committee

Co-Chair
Cezar Campeanu
Canada
Co-Chair
Luca Prigioniero
UK
Co-Chair
Taylor J. Smith
Canada
Marie-Pierre Beal
France
Pamela Fleischmann
Germany
Dora Giammarresi
Italy
Yo-Sub Han
South Korea
Markus Holzer
Germany
Galina Jiraskova
Slovakia
Stavros Konstantinidis
Canada
Martin Kutrib
Germany
Andreas Malcher
Germany
Ian McQuillan
Canada
Nelma Moreira
Portugal
Rogerio Reis
Portugal
Kai Salomaa
Canada
Shinnosuke Seki
Japan
Gyorgy Vaszil
Hungary

Organizing Committee

Chair
Salimur Choudhury
Canada
Tasnim Ahmed
Canada
Attend

Registration

Registration is now open through the official Queen's University event system.

Register Now

DCFS 2026 Fees

Category Early Rate (by July 1, 2026) Late Rate (after July 1, 2026)
Regular CA$500 CA$650
Student CA$400 CA$550

Joint CIAA + DCFS 2026 Fees

Attending both CIAA 2026 and DCFS 2026? Register jointly at a combined rate.

Category Early Rate (by July 1, 2026) Late Rate (after July 1, 2026)
Regular CA$900 CA$1,200
Student CA$700 CA$1,000
Location & Travel

Venue, Travel & Accommodation

🏛️

Queen's University

School of Computing

Conference Venue: Biosciences Complex, Room 2109

116 Barrie Street, Kingston, ON K7L 3N6

+1 613-533-2000  |  queensu.ca

Getting to Kingston

✈️
By Air

The closest airport is Kingston Airport (YGK), approximately 10 km from campus. For more flight options, attendees may fly into:

  • Toronto Pearson International (YYZ)
  • Ottawa Macdonald-Cartier International (YOW)
  • Montréal-Trudeau International (YUL)

Attendees taking Air Canada may book the Air Canada landline bus service from Toronto to Kingston as a flight connection.

🚍
By Bus
From Carrier Duration
Toronto (Union Stn) Megabus / FlixBus 3h 15m – 3h 20m
Toronto Airport (YYZ) Megabus / FlixBus 3h 35m – 3h 40m
Ottawa, ON Megabus / FlixBus 2h 15m – 2h 20m
Montréal, QC Megabus 3h 20m

Megabus Canada  |  FlixBus

🚆
By Train (Via Rail)
Route Duration
Toronto – Kingston 2h 21m
Ottawa – Kingston 2h 03m
Montréal – Kingston 2h 00m

Via Rail Canada

🚗
By Car

Kingston is located along Highway 401:

  • ~272 km east of Toronto Pearson Airport (~3 hours)
  • ~200 km southwest of Ottawa (~2 hours)

Accommodation

Queen's University Residences

156 Albert Street, Kingston, ON K7L 3V2

Phone: 613-533-3183 (May–August)  |  queensu.ca/eventservices/accommodations

CA$140 / night (excl. taxes & fees)
Special Rate Deadline: July 10, 2026

Room: Endaayaan Tkanonsote 2 Bedroom Unit

  • 2 double beds  ·  private bath  ·  sleeps up to 4
  • Desk and chair, wardrobe, mini-fridge, flat-screen TV
  • In-unit climate control
  • Floor lounges with kitchen facilities (microwave, stove-top, fridge)
  • Regular housekeeping, 24-hour front desk, elevator access

Note: Only two-bedroom units are available. Participants wishing to split the cost must arrange sharing details independently.

Book Now — Group Code 144715

Join Us at DCFS 2026

Register now and be part of the advancement of descriptional complexity research

Register Now Contact Organizers
Get in Touch

Contact Us

Have questions? We're here to help

✉️

Email

dcfs2026@cs.queensu.ca

For all inquiries regarding paper submissions, registration, venue, or general questions about DCFS 2026