DLT 2024: Developments in Language Theory

Scientific Programme

DLT 2024

This version of the program of DLT 2024 is not final, and can still be updated at the request of the contributors.

Monday 12.8.2024

9:00 - 19:00 NCMA Workshop

Tuesday 13.8.2024

9:00 - 11:00 NCMA Workshop

11:00 - 11:20 Coffee break, Registration DLT 2024

11:20 - 11:30 Opening DLT 2024

11:30 - 12:30 Invited Talk (Unifying DLT & NCMA): Martin Kutrib. Cellular Automata: From Black-and-White to High Gloss Color (Chair: Giovanni Pighizzini)

12:30 - 14:00 Lunch Break

14:00 - 15:30 Highlights of Language Theory (Chair: Henning Fernau)
- C. Aiswarya, Amaldev Manuel and Saina Sunny. Edit Distance of Finite State Transducers (based on a paper presented at ICALP 2024)
- Stefan Göller and Nathan Grosshans. The AC0-Complexity Of Visibly Pushdown Languages (based on a paper presented at STACS 2024)

15:30 - 16:00 Coffee break

16:00 - 18:00 DLT Contributed Talks (4 talks, Chair: Stefan Göller)
- Marco Sälzer, Eric Alsmann, Florian Bruse and Martin Lange. Verifying And Interpreting Neural Networks using Finite Automata
- Michele Chiari. Software Model Checking and Operator Precedence Languages
- Amazigh Amrane, Hugo Bazille, Emily Clement, Uli Fahrenberg and Krzysztof Ziemianski. Presenting Interval Pomsets with Interfaces: Extended Abstract
- Marco B. Caminati. O_2 is a multiple context-free grammar: an implementation-, formalisation-friendly proof

19:00: Evening Lecture in the Historic Observatory. Speakers:
- Axel Wittmann. The Historic Observatory.
- Anke Holler, Hedde Zeijlstra. Current Topics in Linguistics at Göttingen

Wednesday 14.8.2024

9:00 - 11:00 DLT Contributed Talks (4 talks, Chair: Robert Mercas)
- Yusuke Inoue, Kenji Hashimoto and Hiroyuki Seki. Semidirect Product Decompositions for Periodic Regular Languages
- Amazigh Amrane, Hugo Bazille, Uli Fahrenberg and Marie Fortin. Logic and Languages of Higher-Dimensional Automata
- C Aiswarya, Saina Sunny and Amaldev Manuel. Deciding Conjugacy of a Rational Relation
- Ingyu Baek, Joonghyuk Hahn, Yo-Sub Han and Kai Salomaa. Universal Rewriting Rules for the Parikh Matrix Injectivity Problem

11:00 - 11:30 Coffee Break

11:30 - 12:30 Invited Talk: Sandra Kiefer. Polyregular Functions — Characterisations and Refutations (Chair: Mikołaj Bojańczyk)

12:30 - 14:00 Lunch Break

14:00 - 15:30 Salomaa Award: Award Ceremony and Invited Talk by the Awardee Mikołaj Bojańczyk (Chair: Jürgen Dassow)

15:30 - 16:00 Coffee break

16:00 - 17:30 Highlights of Language Theory (Chair: Sebastian Maneth)
- Markus Lohrey, Markus L. Schmid: Enumeration for MSO-Queries on Compressed Trees (two talks based on a paper presented at PODS 2024)

18:30 Social Event in the Alte Mensa.

Thursday 15.8.2024

9:00 - 11:00 DLT Contributed Talks (4 talks, Chair: Henning Bordihn)
- Benedek Nagy and Friedrich Otto. Finite Automata with Sets of Translucent Words
- Oscar Ibarra and Ian McQuillan. Techniques for Showing the Decidability of the Boundedness Problem of Language Acceptors
- Philomena Moek. Network Topologies for Parallel Communicating Finite Automata: Token-Ring and Token-Bus
- Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Priscilla Raucci and Matthias Wendlandt. Deterministic Pushdown Automata with Translucent Input Letters

11:00 - 11:30 Coffee Break

11:30 - 12:30 Invited Talk: Laura Ciobanu. Word equations, constraints and formal languages (Chair: Volker Diekert)

12:30 - 14:00 Lunch Break

14:00 - 15:30 Highlights of Language Theory (Chair: Markus Lohrey)
- Paul Gallot, Sebastian Maneth, Keisuke Nakano and Charles Peyrat. Deciding Linear Height and Linear Size-to-Height Increase of Macro Tree Transducers (based on a paper presented at ICALP 2024)
- Irmak Sağlam, Moses Ganardi and Georg Zetzsche. Directed Regular and Context-Free Languages (based on a paper presented at STACS 2024)

15:30 - 16:00 Coffee break

16:00 - 17:30 DLT Contributed Talks (3 talks, Chair: Paweł Gawrychowski)
- James Currie, Lucas Mol and Jarkko Peltomaki. The repetition threshold for ternary rich words
- Ferdinando Cicalese and Francesca Ugazio. On the complexity and approximability of Bounded access Lempel Ziv coding
- Travis Gagie. How to Find Long Maximal Exact Matches and Ignore Short Ones

17:30 - 17:45 Short break

17:45 - 18:45 DLT Contributed Talks (2 talks, Chair: Florin Manea)
- Sungmin Kim and Yo-Sub Han. Approximate Cartesian Tree Pattern Matching
- Peter Peresini, Nathaniel Brown, Travis Gagie and Benjamin Langmead. MIOV: Reordering MOVI for even better locality

Friday 16.8.2024

9:00 - 11:00 DLT Contributed Talks (4 talks, Chair: Markus L. Schmid)
- Jakub Ruszil. Careful Synchronization of One-Cluster Automata
- Hermann Gruber, Markus Holzer and Christian Rauch. The Pumping Lemma for Context-Free Languages is Undecidable
- Michele Chiari, Dino Mandrioli and Matteo Pradella. Cyclic Operator Precedence Grammars for Improved Parallel Parsing
- Yinfeng Zhu. Around Don's conjecture for binary completely reachable automata

11:00 - 11:30 Coffee Break

11:30 - 12:30 Invited Talk: Paweł Gawrychowski. Algorithms and combinatorics on two-dimensional strings (Chair: Florin Manea)

12:30 - 13:00 Announcements and Closing Remarks

13:00 - 14:00 Lunch Break

14:00 - 15:30 Mentoring Workshop: Panel Discussion

15:30 - 16:00 Coffee break

16:00 - 19:00 Mentoring Workshop: Group Discussions