Developments in Language Theory, DLT 2007
Eleventh International Conference
DEVELOPMENTS IN LANGUAGE THEORY
July 3–6, 2007, Turku, Finland
The conference is under the auscpices of the European Association for Theoretical Computer Science (EATCS).

Program

Registration: Monday 19:00 – 21:00 and Tuesday 8:00 – 9:00
Opening: Tuesday 8:45 – 9:00

Tuesday Wednesday Thursday Friday
9:00-10:00 Information Distance and Applications
Ming Li
Descriptional Complexity of Nondeterministic Finite Automata
Kai Salomaa
Quantitative Generalizations of Languages
Thomas Henzinger
Finite Automata and the Writing of Numbers
Jacques Sakarovitch
10:00-10:30 Coffee Coffee Coffee Coffee
10:30-11:00 Commutation of Binary Factorial Languages
Anna Frid
What Do We Know about Language Equations?
Michal Kunc
On First-Order Fragments for Words and Mazurkiewicz Traces
Volker Diekert, Manfred Kufleitner
Reduced languages as ω-generators
Sandrine Julia, Vinh Duc Tran
11:00-11:30 State Complexity of Union and Intersection of Finite Languages
Yo-Sub Han, Kai Salomaa
Descriptional Complexity of Bounded Context-Free Languages
Andreas Malcher, Giovanni Pighizzini
11:30-12:00 Conjunctive grammars can generate non-regular unary languages
Artur Jeż
The dynamics of cellular automata in shift-invariant topologies
Laurent Bienvenu, Mathieu Sablik
From Determinism to Non-determinism in Recognizable Twodimensional Languages
Marcella Anselmo, Dora Giammarresi, Maria Madonia
Inapproximability of Nondeterministic State and Transition Complexity Assuming P≠NP
Hermann Gruber, Markus Holzer
12:00-13:30 Lunch Lunch Lunch Lunch
13:30-14:00 Two Element Unavoidable Sets of Partial Words
Francine Blanchet-Sadri, Naomi Brownstein, Justin Palumbo
Hairpin Finite Automata
Henning Bordihn, Markus Holzer, Martin Kutrib
Deterministic Blow-ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
Jozef Jirásek, Galina Jirásková, Alexander Szabari
2-Visibly Pushdown Automata
Dario Carotenuto, Aniello Murano, Adriano Peron
14:00-14:30 The Unambiguity of Segmented Morphisms
Dominik Freydenberger, Daniel Reidenbach
Coding Partitions: Regularity, Maximality and Global Ambiguity
Marie-Pierre Béal, Fabio Burderi, Antonio Restivo
Finite Automata on Unranked and Unordered DAGs
Lutz Priese
An Extension of Newton's Method to ω-Continuous Semirings
Javier Esparza, Stefan Kiefer, Michael Luttenberger
14:30-15:00 Avoiding Approximate Squares
Dalia Krieger, Pascal Ochem, Narad Rampersad, Jeffrey Shallit
An efficient computation of the equation K-automaton of a regular K-expression
Jean-Marc Champarnaud, Faissal Ouardi, Djelloul Ziadi
Fine Hierarchy of Regular Aperiodic ω-Languages
Victor Selivanov
On Transition Minimality of Bideterministic Automata
Hellis Tamm
15:00-15:30 Coffee Coffee   Coffee
15:30-16:00 Multi-letter Reversible and Quantum Finite Automata
Aleksandrs Belovs, Ansis Rosmanis, Juris Smotrovs
Duplication Roots
Peter Leupold
  Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids
Alberto Bertoni, Roberto Radicioni
16:00-16:30 Non-constructive Methods for Finite Probabilistic Automata
Rūsiņš Freivalds
On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
Yuri Pritykin
  A Star Operation for Star-Free Trace Languages
Edward Ochmański, Krystyna Stawikowska
16:30-17:00 Characterizing Reduction Graphs for Gene Assembly in Ciliates
Robert Brijder, Hendrik Jan Hoogeboom
A Local Balance Property of Episturmian Words
Gwénaël Richomme
  Bisimulation Minimisation for Weighted Tree Automata
Johanna Högberg, Andreas Maletti, Jonathan May
17:00-17:30 Complexity Theory for Splicing Systems
Remco Loos, Mitsunori Ogihara
Suffix Automata and Standard Sturmian Words
Marinella Sciortino, Luca Zamboni
  Definable Transductions and Weighted Logics for Texts
Christian Mathissen
  19:00 – 22:00 Welcome reception at Forum Marinum, Linnankatu 72 17:00 –23:00 Excursion to Kavalto Farm. The bus leaves from the ICT building at 5pm.  
Pictures