Information for Authors

 

Programme of DLT'2015

 

 

Monday, 27 July, 2015

8:00-8:50

Registration & Morning Coffee

8:50-9:00

Opening

9:00-10:00

Invited Talk: Wolfgang Thomas (RWTH Aachen)

Finite Automata and Transitive Closure Logic

10:00-10:20

Coffee Break

10:20-10:45

Olivier Carton and Luc Boasson.

Transfinite Lyndon words

10:45-11:10

Paul Bell, Daniel Reidenbach and Jeffrey Shallit.

Factorization in Formal Languages

11:10-11:35

Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Korkkoinen, Dominik Kempa, Marcin Piatkowski, Simon Puglisi and Shiho Sugimoto.

Diverse Palindromic Factorization is NP-Complete

11:35-12:00

Marie-Pierre Beal and Pavel Heller.

Deciding proper conjugacy of classes of one-sided finite-type-Dyck shifts

12:00-14:00

Lunch

14:00-14:25

Tomas Masopust and Michael Thomazo.

On the Complexity of k-Piecewise Testability and the Depth of Automata

14:25-14:50

Christian Brandl and Hans Simon.

Complexity Analysis: Finite Monoids and Communication Complexity

14:50-15:15

Timothy Ng, David Rappaport and Kai Salomaa.

State Complexity of Neighbourhoods and Approximate Pattern Matching

15:15-15:40

Francine Blanchet-Sadri and Abraham Rashin.

Squareable Words

15:40-16:00

Coffee Break

16:00-16:25

Jorge Almeida, Jana Bartonova, Ondrej Klima and Michal Kunc.

On decidability of intermediate levels of concatenation hierarchies

16:25-16:50

Zoltan Esik, Uli Fahrenberg and Axel Legay.

Star-Continuous Kleene Omega-Algebras

 

 

 

Tuesday, 28 July, 2015

8:00-9:00

Morning Coffee

9:00-10:00

Invited Talk: Patrick Dehornoy (Universite de Caen)

Garside and quadratic normalisation: a survey

10:00-10:20

Coffee Break

10:20-10:45

James Currie, Florin Manea and Dirk Nowotka.

Unary patterns under permutations

10:45-11:10

Sergey V. Avgustinovich, Anna Frid and Svetlana Puzynina.

Ergodic infinite permutations of minimal complexity

11:10-11:35

Francesco Dolce and Dominique Perrin.

Enumeration formula in neutral sets

11:35-12:00

Jozef Jirasek and Galina Jiraskova.

The Boundary of Prefix-Free Languages

12:00-14:00

Lunch

14:00-15:00

Invited Talk: Vesa Halava (University of Turku)

Proofs of Undecidability

15:00-15:25

Joey Eremondi, Oscar Ibarra and Ian McQuillan.

On the Density of Context-Free and Counter Languages

15:25-15:50

Dietmar Berwanger and Marie Van Den Bogaard.

Consensus Game Acceptors

15:50-16:10

Coffee Break

16:10-16:35

Michael Ludwig, Andreas Krebs and Klaus-Jorn Lange.

On Distinguishing NC1 and NL

16:35-17:00

Yo-Sub Han, Sang-Ki Ko and Kai Salomaa.

Generalizations of Code Languages with Marginal Errors

 

 

 

 

 

Wednesday, 29 July, 2015

8:00-9:00

Morning Coffee

9:00-10:00

Invited Talk: Mikołaj Bojańczyk (Warsaw University)

Recognisable Languages over Monads

10:00-10:20

Coffee Break

10:20-10:45

Markus Lohrey, Karin Quaas and Shiguang Feng.

Path Checking for MTL and TPTL

10:45-11:10

Vitaly Perevoshchikov.

Weight Assignment Logic

11:10-11:35

Christopher Czyba, Christopher Spinrath and Wolfgang Thomas.

Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change

11:35-12:00

Markus Holzer, Sebastian Jakobi and Martin Kutrib.

Minimal Reversible Deterministic Finite Automata

12:00-14:00

Lunch

14:00-14:25

Tomoyuki Yamakami.

Complexity Bounds of Constant-Space Quantum Computation

14:25-14:50

Aida Gainutdinova and Abuzer Yakaryilmaz.

Unary probabilistic and quantum automata on promise problems

14:50-15:15

Coffee

 

Social Program & Conference Dinner

 

 

 

 

Thursday, 30 July, 2015

8:00-9:00

Morning Coffee

9:00-10:00

Invited Talk: Markus Lohrey (Universitat Siegen)

Grammar-Based Tree Compression

10:00-10:20

Coffee Break

10:20-10:45

Ines Klimann, Matthieu Picantin and Dmytro Savchuk.

A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group

10:45-11:10

Ismael Jecker and Emmanuel Filiot.

Multi-Sequential Word Relations

11:10-11:35

Friedrich Otto and Kent Kwee.

Deterministic ordered restarting automata that compute functions

11:35-12:00

Maria Paola Bianchi, Juraj Hromkovic and Ivan Kovac.

Two-way Automata: Determinism vs. Nondeterminism

12:00-14:00

Lunch

14:00-14:25

Presentation of DLT 2016

14:25-14:50

Victor Marsault. Surminimisation of automata

14:50-15:15

Zuzana Masakova, Edita Pelantova and Stepan Starosta.

Interval Exchange Words and the Question of Hof, Knill, and Simon

15:15-15:40

Srecko Brlek, Nadia Lafrenere and Xavier Provencal.

Palindromic complexity of tree-like graphs

15:40-16:00

Coffee