9th International Conference

DEVELOPMENTS IN LANGUAGE THEORY

July 4-8, 2005  -  Hotel La Torre, Mondello
Palermo, ITALY
 

 

  

 



Home


Call for Papers


Program Committee


Invited Speakers


Organizing Committee


Participants


Photo gallery


Program   html   pdf


Registration


Accomodation


Travel Information

   Monday, July 4th -  Welcome and Registration

17:30 Registration.

19:00 Welcome Cocktail.

Tuesday, July 5th

08:45 Conference Opening.

09:00-10:00 Invited lecture:

Central Sturmian Words: Recent Developments.
Arturo Carpi, Aldo de Luca.

10:00-10:30 Selected Contributions:
  • Bidimensional Sturmian Sequences and Substitutions (slides).
    • Thomas Fernique.
10:30-11:00 Coffee Break.

11:00-12:30 Selected Contributions:
  • Sturmian words: dynamical systems and derivated words (slides).
    • Isabel M. Araújo and Véronique Bruyère.
  • On Hairpin-Free Words and Languages (slides).
    • L. Kari, S. Konstantinidis, P. Sosík, G. Thierrin.
  • On the Frequency of Letters in Pure Binary Morphic Sequences.
    • Kalle Saari.
12:30-15:00 Lunch Break.

15:00-16:00 Invited lecture:

Codes in Symbolic Systems (slides)
Marie-Pierre Bèal, Dominique Perrin.

16:00-16:30 Selected Contributions:
  • A Kleene Theorem for Languages of Words Indexed by Linear Orderings.
    • Alexis Bès and Olivier Carton.
10:30-11:00 Coffee Break.

17:00-18:30 Selected Contributions:
  • Schützenberger and Eilenberg theorems for words on linear orderings (slides)
    • Nicolas Bedon and Chloé Rispal.
  • The inclusion problem for unambiguous rational trace languages (slides).
    • Paolo Massazza.
  • LR parsing for Boolean grammars (slides).
    • Alexander Okhotin.
Wednesday, July 6th

09:00-10:00 Invited lecture:

Inexpressibility Results for Regular Languages in Nonregular Settings (slides).
Howard Straubing.

10:00-10:30 Selected Contributions:
  • Membership and finiteness problems for recognizable subsets of regular languages (slides).
    • Sergey Afonin and Elena Hazova.
10:30-11:00 Coffee Break.

11:00-12:30 Selected Contributions:
  • On Language Inequalities $XK \subseteq LX$ (slides).
    • Michal Kunc.
  • On the Reachability of Invertible Diagonal Matrices (slides).
    • Paul Bell and Igor Potapov.
  • Polynomial Generators of Recursively Enumerable Languages (slides).
    • Juha Kortelainen.
12:30-15:00 Lunch Break.

15:00-16:00 Invited lecture:

Restricted towers of Hanoi and morphisms (slides).
Jean-Paul Allouche and Amir Sapir.

16:00-16:30 Selected Contributions:
  • Voronoi cells of beta-integers (slides).
    • Avi Elkharrat and Christiane Frougny.
16:30-17:00 Coffee Break.

17:00-18:30 Selected Contributions:
  • The Power of Tree Series Transducers of Type I and II (slides).
    • Andreas Maletti.
  • Unambiguous Morphic Images of Strings (slides).
    • Dominik D. Freydenberger, Daniel Reidenbach, Johannes C. Schneider.
  • A note on a result of Daurat and Nivat.
    • Srecko Brlek, Gilbert Labelle, Annie Lacasse.
Thursday, July 7th

09:00-10:00 Invited lecture:

Locally Consistent Parsing and Applications to Approximate String Comparisons.
Tuğkan Batu and Cenk Sahinalp.

10:00-10:30 Selected Contributions:
  • Languages with mismatches and an application to approximate indexing (slides).
    • C. Epifanio, A. Gabriele and F. Mignosi
10:30-11:00 Coffee Break.

11:00-13:00 Selected Contributions:
  • Complementing Two-Way Finite Automata.
    • Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini.
  • Monotone Deterministic RL-Automata Don't Need Auxiliary Symbols (slides).
    • T. Jurdzinksi, F. Mráz, F. Otto, M. Plátek.
  • Revolving-Input Finite Automata.
    • Henning Bordihn, Markus Holzer, Martin Kutrib.
13:00-15:00 Lunch Break.

15:00-23:00 Social tour and dinner.

Friday, July 8th

09:00-10:00 Invited lecture:

Collapsing Words: A Progress Report (slides).
D.S. Ananichev, I.V. Petrov and Michael V. Volkov.

10:00-10:30 Selected Contributions:
  • On palindromic factors of billiard words.
    • J-P. Borel and C. Reutenauer.
10:30-11:00 Coffee Break.

11:00-12:30 Selected Contributions:
  • Palindromes in Sturmian Words (slides).
    • Aldo de Luca and Alessandro De Luca.
  • The Mortality Threshold for Partially Monotonic Automata (slides).
    • D.S. Ananichev.
  • On Some Properties of the Language of 2-Collapsing Words (slides).
    • E.V. Pribavkina.
12:30-15:00 Lunch Break.

15:00-16:00 Invited lecture:

Reversible cellular automata.
Jarkko Kari.

16:00-16:30 Selected Contributions:
  • Complexity of Quantum Uniform and Nonuniform Automata.
    • Farid Ablayev, Aida Gainutdinova.
16:30-17:00 Coffee Break.

17:00-18:30 Selected Contributions:
  • On Timed Automata with Discrete Time--Structural and Language Theoretical Characterization.
    • H. Gruber, M. Holzer, A. Kiehn and B. König.
  • Tissue P Systems with Antiport Rules and Small Numbers of Symbols and Cells (slides).
    • Artiom Alhazov, Rudolf Freund, Marion Oswald.
  • Semi-Rational Sets of DAGs.
    Lutz Priese    .