DLT 2012

Program (updated 8/16/2012)
Monday, August 13th Barry Lam Hall, Dept. of Electrical Engineering, National Taiwan University 16:00 – 18:00: Registration Tuesday, August 14th Room BL-101, Barry Lam Hall 8:00 – 9:00: Registration 9:00 – 9:30: Opening Session Welcome Speech – Hsu-Chun Yen and Oscar Ibarra Opening Speech – Juhani Karhumäki, Chair of the DLT Steering Committee Session Chair: Oscar Ibarra 9:30 – 10:30: (Invited Talk) The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012 (Andrew Szilard) 10:30 – 11:00: Coffee break Session Chair: Juraj Hromkovic 11:00 – 11:30: Quotient Complexities of Atoms of Regular Languages (Janusz Brzozowski and Hellis Tamm) 11:30 – 12:00: Decidability of Geometricity of Regular Languages (Marie-Pierre Béal, Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne and Sylvain Lombardy) 12:00 – 12:30: Inside the Class of REGEX Languages (Markus L. Schmid) 12:30 – 13:30: Lunch Session Chair: Andrew Szilard 13:30 – 14:30: (Invited Talk) P and dP Automata: Unconventional versus Classical Automata (Erzsebet Csuhaj-Varju) Session Chair: Volker Diekert 14:30 – 14:40: Remembering Manfred Kudlek (Nils Erik Flick) 14:40 – 15:00: (SHORT) A Hierarchy of Languages with Catenation and Shuffle (Nils Erik Flick and Manfred Kudlek) 15:00 – 15:30: Computing the Edit-distance Between a Regular Language and a Context-free Language (Yo-Sub Han, Sang-Ki Ko and Kai Salomaa) 15:30 – 16:00: Semigroups with a Context-free Word Problem (Michael Hoffmann, Derek Holt, Matt Owens and Rick Thomas) 16:00 – 16:30: Coffee break Session Chair: Zoltan Esik 16:30 – 17:00: General Derivations with Synchronized Context-Free Grammars (Markus Holzer, Sebastian Jakobi and Ian McQuillan) 17:00 – 17:30: Non-erasing Variants of the Chomsky--Schützenberger Theorem (Alexander Okhotin) 17:30 – 18:00: Regular and Context-Free Pattern Languages Over Small Alphabets (Daniel Reidenbach and Markus L. Schmid) 18:00 – 18:20: (SHORT) Characterizing Languages by Normalization and Termination in String Rewriting (Jeroen Ketema and Jakob Grue Simonsen) 18:40 – 20:30: Welcome reception Wednesday, August 15th Room BL-101 Session Chair: Erzsebet Csuhaj-Varju 8:30 – 9:30: (Invited Talk) Recovering Strings in Oracles: Quantum and Classic (Kazuo Iwama) Session Chair: Janusz Brzozowski 9:30 – 10:00: On Context-free Languages of Scattered Words (Zoltan Esik and Satoshi Okawa) 10:00 – 10:30: Homomorphisms Preserving Deterministic Context-free Languages (Tommi Lehtinen and Alexander Okhotin) 10:30 – 11:00: Coffee break Session Chair: Marie-Pierre Béal 11:00 – 11:30: Unary Coded NP-Complete Languages in ASPACE(loglog n) (Viliam Geffert and Dana Pardubska) 11:30 – 12:00: Dense Completeness (Andreas Krebs and Klaus-Joern Lange) 12:00 – 12:30: From Equivalence to Almost-Equivalence, and Beyond---Minimizing Automata With Errors (Markus Holzer and Sebastian Jakobi) 12:30 – 13:30: Lunch Session Chair: Markus Holzer 13:30 – 14:00: Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata (Christos Kapoutsis and Nans Lefebvre) 14:00 – 14:30: States and Heads Do Count For Unary Multi-Head Finite Automata (Martin Kutrib, Andreas Malcher and Matthias Wendlandt) 14:30 – 15:00: Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness (Mathieu Caralp, Pierre-Alain Reynier and Jean-Marc Talbot) 15:00 – 15:30: Unambiguous Constrained Automata (Michaël Cadilhac, Alain Finkel and Pierre Mckenzie) 15:30 – 16:00: Coffee break Session Chair: Kazuo Iwama 16:00 – 16:30: Two-dimensional Sgraffito Automata (Daniel Prusa and Frantisek Mraz) 16:30 – 17:00: Two-way Transducers with a Two-way Output Tape (Olivier Carton) 17:00 – 17:30: Learning Rational Functions (Adrien Boiret, Aurélien Lemay and Joachim Niehren.) 17:30 – 18:00: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (Giovanna Lavado, Giovanni Pighizzini and Shinnosuke Seki) Thursday, August 16th Room BL-101 Session Chair: Hsu-Chun Yen 8:30 – 9:30: (Invited Talk) Determinism vs. Nondeterminism for Two-Way Automata (Juraj Hromkovic) Session Chair: Giovanni Pighizzini 9:30 – 10:00: Fine and Wilf's Theorem for $k$-Abelian Periods (Juhani Karhumäki, Svetlana Puzynina and Aleksi Saarela) 10:00 – 10:30: Pseudoperiodic Words (Alexandre Blondin Massé, Sébastien Gaboury and Sylvain Hallé) 10:30 – 11:00: Coffee break Session Chair: Bow-Yaw Wang 11:00–11:30: Acceptance Conditions for $\omega$-Languages (Alberto Dennunzio, Enrico Formenti and Julien Provillard) 11:30 – 12:00: Checking Determinism of Regular Expressions with Counting (Haiming Chen and Ping Lu) 12:00 – 12:30: Biautomata for k-Piecewise Testable Languages (Ondrej Klima and Libor Polak) 12:30 – 13:30: Lunch 13:30 – 18:00: Excursion 18:30 – ??: Dinner Friday, August 17th Room BL-101 Session Chair: Juhani Karhumäki 8:30 – 9:30: (Invited Talk) Universal Pattern Generation by Cellular Automata (Jarkko Kari) Session Chair: Martin Kutrib 9: 30 – 10:00: Squares in Binary Partial Words (Francine Blanchet-Sadri, Yang Jiao and John Machacek) 10:00 – 10:30: Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars (Matthias Büchse, Andreas Maletti and Heiko Vogler) 10:30 – 11:00: Coffee break Session Chair: Giancarlo Mauri 11:00 – 11:30: On State Complexity of Finite Word and Tree Languages (Aniruddh Gandhi, Bakhadyr Khoussainov and Jiamou Liu) 11:30 – 12:00: The State Complexity of Star-complement-star (Galina Jiraskova and Jeffrey Shallit) 12:00 – 12:30: On Centralized PC Grammar Systems with Context-Sensitive Components (Friedrich Otto) 12:30 – 13:30: Lunch Session Chair: Jarkko Kari 13:30 – 14:00: The Avoidability of Cubes under Permutations (Florin Manea, Mike Müller and Dirk Nowotka) 14:00 – 14:30: Hairpin Completion with Bounded Stem-loop (Szilard Zsolt Fazekas, Robert Mercas and Kayoko Shikishima-Tsuji) 14:30 – 15:00: Morphic Primitivity and Alphabet Reductions (Hossein Nevisi and Daniel Reidenbach) 15:00 – 15:20: (SHORT) Geometry and Dynamics of the Besicovitch and Weyl Spaces (Ilkka Törmä and Ville Salo) 15:20 – 15:40: (SHORT) A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay (Laura Giambruno, Sabrina Mantaci, Jean Néraud and Carla Selmi) 15:40 – 16:10: Coffee break 16:10 – 17:00: Closing Session, chaired by Juhani Karhumäki

Program (updated 8/16/2012)

Monday, August 13th
Barry Lam Hall, Dept. of Electrical Engineering, National Taiwan University

16:00 – 18:00: Registration

Tuesday, August 14th
Room BL-101, Barry Lam Hall

8:00 – 9:00: Registration
9:00 – 9:30: Opening Session
Welcome Speech – Hsu-Chun Yen and Oscar Ibarra
Opening Speech – Juhani Karhumäki, Chair of the DLT Steering Committee

Session Chair: Oscar Ibarra
9:30 – 10:30: (Invited Talk) The Kind Hearted Dragon Prof. Sheng Yu, 1950-2012 (Andrew Szilard)

10:30 – 11:00: Coffee break

Session Chair: Juraj Hromkovic
11:00 – 11:30: Quotient Complexities of Atoms of Regular Languages (Janusz Brzozowski and Hellis Tamm)
11:30 – 12:00: Decidability of Geometricity of Regular Languages (Marie-Pierre Béal, Jean-Marc Champarnaud, Jean-Philippe Dubernard, Hadrien Jeanne and Sylvain Lombardy)
12:00 – 12:30: Inside the Class of REGEX Languages (Markus L. Schmid)

12:30 – 13:30: Lunch

Session Chair: Andrew Szilard
13:30 – 14:30: (Invited Talk) P and dP Automata: Unconventional versus Classical Automata (Erzsebet Csuhaj-Varju)

Session Chair: Volker Diekert
14:30 – 14:40: Remembering Manfred Kudlek (Nils Erik Flick)
14:40 – 15:00: (SHORT) A Hierarchy of Languages with Catenation and Shuffle (Nils Erik Flick and Manfred Kudlek)
15:00 – 15:30: Computing the Edit-distance Between a Regular Language and a Context-free Language (Yo-Sub Han, Sang-Ki Ko and Kai Salomaa)
15:30 – 16:00: Semigroups with a Context-free Word Problem (Michael Hoffmann, Derek Holt, Matt Owens and Rick Thomas)

16:00 – 16:30: Coffee break

Session Chair: Zoltan Esik
16:30 – 17:00: General Derivations with Synchronized Context-Free Grammars (Markus Holzer, Sebastian Jakobi and Ian McQuillan)
17:00 – 17:30: Non-erasing Variants of the Chomsky--Schützenberger Theorem (Alexander Okhotin)
17:30 – 18:00: Regular and Context-Free Pattern Languages Over Small Alphabets (Daniel Reidenbach and Markus L. Schmid)
18:00 – 18:20: (SHORT) Characterizing Languages by Normalization and Termination in String Rewriting (Jeroen Ketema and Jakob Grue Simonsen)

18:40 – 20:30: Welcome reception

Wednesday, August 15th
Room BL-101

Session Chair: Erzsebet Csuhaj-Varju
8:30 – 9:30: (Invited Talk) Recovering Strings in Oracles: Quantum and Classic (Kazuo Iwama)

Session Chair: Janusz Brzozowski
9:30 – 10:00: On Context-free Languages of Scattered Words (Zoltan Esik and Satoshi Okawa)
10:00 – 10:30: Homomorphisms Preserving Deterministic Context-free Languages (Tommi Lehtinen and Alexander Okhotin)

10:30 – 11:00: Coffee break

Session Chair: Marie-Pierre Béal
11:00 – 11:30: Unary Coded NP-Complete Languages in ASPACE(loglog n) (Viliam Geffert and Dana Pardubska)
11:30 – 12:00: Dense Completeness (Andreas Krebs and Klaus-Joern Lange)
12:00 – 12:30: From Equivalence to Almost-Equivalence, and Beyond---Minimizing Automata With Errors (Markus Holzer and Sebastian Jakobi)

12:30 – 13:30: Lunch

Session Chair: Markus Holzer
13:30 – 14:00: Analogs of Fagin's Theorem for Small Nondeterministic Finite Automata (Christos Kapoutsis and Nans Lefebvre)
14:00 – 14:30: States and Heads Do Count For Unary Multi-Head Finite Automata (Martin Kutrib, Andreas Malcher and Matthias Wendlandt)
14:30 – 15:00: Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness (Mathieu Caralp, Pierre-Alain Reynier and Jean-Marc Talbot)
15:00 – 15:30: Unambiguous Constrained Automata (Michaël Cadilhac, Alain Finkel and Pierre Mckenzie)

15:30 – 16:00: Coffee break

Session Chair: Kazuo Iwama
16:00 – 16:30: Two-dimensional Sgraffito Automata (Daniel Prusa and Frantisek Mraz)
16:30 – 17:00: Two-way Transducers with a Two-way Output Tape (Olivier Carton)
17:00 – 17:30: Learning Rational Functions (Adrien Boiret, Aurélien Lemay and Joachim Niehren.)
17:30 – 18:00: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (Giovanna Lavado, Giovanni Pighizzini and Shinnosuke Seki)

Thursday, August 16th
Room BL-101

Session Chair: Hsu-Chun Yen
8:30 – 9:30: (Invited Talk) Determinism vs. Nondeterminism for Two-Way Automata (Juraj Hromkovic)

Session Chair: Giovanni Pighizzini
9:30 – 10:00: Fine and Wilf's Theorem for $k$-Abelian Periods (Juhani Karhumäki, Svetlana Puzynina and Aleksi Saarela)
10:00 – 10:30: Pseudoperiodic Words (Alexandre Blondin Massé, Sébastien Gaboury and Sylvain Hallé)

10:30 – 11:00: Coffee break

Session Chair: Bow-Yaw Wang
11:00–11:30: Acceptance Conditions for $\omega$-Languages (Alberto Dennunzio, Enrico Formenti and Julien Provillard)
11:30 – 12:00: Checking Determinism of Regular Expressions with Counting (Haiming Chen and Ping Lu)
12:00 – 12:30: Biautomata for k-Piecewise Testable Languages (Ondrej Klima and Libor Polak)

12:30 – 13:30: Lunch

13:30 – 18:00: Excursion

18:30 – ??: Dinner

Friday, August 17th
Room BL-101

Session Chair: Juhani Karhumäki
8:30 – 9:30: (Invited Talk) Universal Pattern Generation by Cellular Automata (Jarkko Kari)

Session Chair: Martin Kutrib
9: 30 – 10:00: Squares in Binary Partial Words (Francine Blanchet-Sadri, Yang Jiao and John Machacek)
10:00 – 10:30: Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars (Matthias Büchse, Andreas Maletti and Heiko Vogler)

10:30 – 11:00: Coffee break

Session Chair: Giancarlo Mauri
11:00 – 11:30: On State Complexity of Finite Word and Tree Languages (Aniruddh Gandhi, Bakhadyr Khoussainov and Jiamou Liu)
11:30 – 12:00: The State Complexity of Star-complement-star (Galina Jiraskova and Jeffrey Shallit)
12:00 – 12:30: On Centralized PC Grammar Systems with Context-Sensitive Components (Friedrich Otto)

12:30 – 13:30: Lunch

Session Chair: Jarkko Kari
13:30 – 14:00: The Avoidability of Cubes under Permutations (Florin Manea, Mike Müller and Dirk Nowotka)
14:00 – 14:30: Hairpin Completion with Bounded Stem-loop (Szilard Zsolt Fazekas, Robert Mercas and Kayoko Shikishima-Tsuji)
14:30 – 15:00: Morphic Primitivity and Alphabet Reductions (Hossein Nevisi and Daniel Reidenbach)
15:00 – 15:20: (SHORT) Geometry and Dynamics of the Besicovitch and Weyl Spaces (Ilkka Törmä and Ville Salo)
15:20 – 15:40: (SHORT) A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay (Laura Giambruno, Sabrina Mantaci, Jean Néraud and Carla Selmi)

15:40 – 16:10: Coffee break
16:10 – 17:00: Closing Session, chaired by Juhani Karhumäki