The 10th edition of DLT will take place at the University of California, Santa Barbara, California, USA on June 26-29, 2006. Papers presenting original contributions in formal languages, automata theory, and related areas are being sought. Simultaneous submissions of papers to any other conference are not allowed.


TOPICS

Typical, but not exclusive, topics include: grammars, acceptors and transducers for strings, trees, graphs, arrays; efficient text algorithms; algebraic theories for automata and languages; combinatorial and algebraic properties of words and languages; variable-length codes; symbolic dynamics; decision problems; relations to complexity theory and logic; picture description and analysis; polyominoes and bidimensional patterns; cryptography; concurrency; bio-inspired computing; quantum computing.


PROCEEDINGS

The proceedings for DLT 2006 is now available online as LNCS 4036. One can access the online version at this Springer site.

INVITED SPEAKERS

      Rajeev Alur (Philadelphia, Pennsylvania, USA)

        Adding Nesting Structure to Words

      Yuri Gurevich (Redmond, Washington, USA)

        Can Abstract State Machines be Useful in Language Theory?

      Gheorghe Paun (Bucharest, Romania & Seville, Spain)

         Languages in Membrane Computing; Some Details for Spiking Neural P Systems

      Grzegorz Rozenberg (Leiden, The Netherlands)

         Computational Nature of Biochemical Reactions

     

PROGRAM COMMITTEE

      Jean Berstel (Marne-la-Vallée, France)
      Cristian Calude (Auckland, New Zealand)
      Erzsebet Csuhaj-Varju (Budapest, Hungary)
      Zhe Dang (Pullman, USA)
      Volker Diekert (Stuttgart, Germany)
      Omer Egecioglu (Santa Barbara, USA)
      Zoltan Esik (Szeged, Hungary & Tarragona, Spain)
      Juraj Hromkovic (Zurich, Switzerland)
      Oscar H. Ibarra, Chair (Santa Barbara, USA)
      Masami Ito (Kyoto, Japan)
      Natasha Jonoska (Tampa, USA)
      Juhani Karhumaki (Turku, Finland)
      Lila Kari (London, Canada)
      Werner Kuich (Vienna, Austria)
      Giancarlo Mauri (Milan, Italy)
      Jean-Eric Pin (Paris, France)
      Bala Ravikumar (Sonoma, USA)
      Antonio Restivo (Palermo, Italy)
      Kai Salomaa (Kingston, Canada)
      Jeffrey Shallit (Waterloo, Canada)
      Wolfgang Thomas (Aachen, Germany)
      Hsu-Chun Yen (Taipei, Taiwan)
      Sheng Yu (London, Canada)

ORGANIZING COMMITTEE

      Omer Egecioglu, Co-Chair (Santa Barbara, USA)
      Bee Jay Estalilla (Santa Barbara, USA)
      Cagdas Gerede (Santa Barbara, USA)
      Jan Holtzclaw (Santa Barbara, USA)
      Oscar H. Ibarra, Co-Chair (Santa Barbara, USA)
      Matthew Shayefar (Santa Barbara, USA)
      Jianwen Su (Santa Barbara, USA)
      Shelly Vizzolini (Santa Barbara, USA)
      Sara Woodworth (Santa Barbara, USA)
      Fang Yu (Santa Barbara, USA)

PROCEEDINGS COMMITTEE

      Zhe Dang (Pullman, USA)
      Oscar H. Ibarra (Santa Barbara, USA)

PUBLICITY COMMITTEE

      Kai Salomaa (Kingston, Canada)
      Sheng Yu (London, Canada)

STEERING COMMITTEE

      Jean Berstel (Marne-la-Vallée, France)
      Cristian Calude (Auckland, New Zealand)
      Volker Diekert (Stuttgart, Germany)
      Juraj Hromkovic (Zurich, Switzerland)
      Oscar H. Ibarra (Santa Barbara, USA)
      Masami Ito (Kyoto, Japan)
      Werner Kuich (Vienna, Austria)
      Gheorghe Paun (Bucharest, Romania & Seville, Spain)
      Antonio Restivo (Palermo, Italy)
      Grzegorz Rozenberg, Chair (Leiden, The Netherlands)
      Arto Salomaa (Turku, Finland)
      Sheng Yu (London, Canada)

SUBMISSION INSTRUCTIONS

Authors are requested to submit an electronic version (in PostScript or pdf form) by February 12, 2006. An extended abstract should start with the title, each author's name, affiliation, and e-mail address, and a one-paragraph summary of the results and ideas, and be submitted at the following url:

Submit Paper (Closed)

The extended abstract should provide sufficient detail to allow the Program Committee to evaluate its validity, quality, and relevance to the conference. The extended abstract should be at most ten (10) pages long using 11-point font with ample margins. If appropriate, proof details omitted in the paper may be added in an appendix.

Authors will be notified of acceptance or rejection by March 20, 2006.

Final copies of accepted papers must be submitted by April 2, 2006 for publication in a Springer-Verlag Lecture Notes in Computer Science Proceedings. (See for example, LNCS 3340 and LNCS 3572 for the proceedings of two previous conferences.)

Extended versions of selected papers from the proceedings of the conference series will be solicited for publication in a special issue of an international computer science journal.

IMPORTANT DATES

      Deadline for Submission: February 17, 2006
      Notification of Acceptance: By March 20, 2006
      Final Version: April 2, 2006
      Conference: June 26-29, 2006


CONTACT ADDRESS

      Oscar H. Ibarra
      Department of Computer Science
      University of California
      Santa Barbara, California 93106, USA
      Email: ibarra@cs.ucsb.edu


ACCEPTED PAPERS (Random Order)

      Yo-Sub Han, Kai Salomaa, Derick Wood

         Prime Decompositions of Regular Languages

      Natasha Jonoska, Lila Kari and Kalpana Mahalingam

         Involution Solid and Join Codes

      Adrian-Horia Dediu, Renate Klempien-Hinrichs, Hans-Jörg Kreowski, Benedek Nagy

         Contextual Hypergraph Grammars -- A New Approach to the Generation of Hypergraph Languages

      Dalia Krieger

         On Critical Exponents in Fixed Points of Non-Erasing Morphisms

      Nicolae Santean and Sheng Yu

         On Weakly Ambiguous Finite Transducers

      Manfred Kufleitner

         Polynomials, Fragments of Temporal Logic and the Variety DA over Traces

      Arseny M. Shur

         Factorial languages of low combinatorial complexity

      Carsten Fritz, Thomas Wilke

         Simulation Relations for Alternating Parity Automata and Parity Games

      D. S. Ananichev, M. V. Volkov, Yu. I. Zaks

         Synchronizing automata with a letter of deficiency 2

      Cedric Bastien, Jurek Czyzowicz, Wojciech Fraczak, and Wojciech Rytter

         Equivalence of Functions Represented by Simple Context-Free Grammars with Output

      Balasubramanian Ravikumar

         On Some Variations of Two-Way Probabilistic Finite Automata

      Christian Glasser, Stephen Travers, and Klaus W. Wagner

         Perfect Correspondences

      Hermann Gruber and Markus Holzer

         Finding Lower Bounds for Nondeterministic State Complexity is Hard

      Andreas Maletti

         Hierarchies of Tree Series Transformations Revisited

      Alexander Okhotin and Oksana Yakimova

         On language equations with complementation

      Paul Bell and Igor Potapov

         Lowering Undecidability Bounds for Decision Questions in Matrices

      Michael Domaratzki

         Characterizing DNA Bond Shapes using Trajectories

      Manfred Droste and George Rahonis

         Weighted automata and weighted logics on infinite words

      M. Cavaliere, P. Frisco, H.J. Hoogeboom

         Computing by Only Observing

      Flavio D'Alessandro, Gwenael Richomme, Stefano Varricchio

         Well quasi orders and the shuffle closure of finite sets

      F. Mraz, F. Otto, M. Platek

         Gap-Complexity of sRL-Automata

      Alberto Bertoni, Christian Choffrut, Beatrice Palano

         Context-free Grammars and XML Languages

      Paola Bonizzoni Giancarlo Mauri

         A decision procedure for reflexive regular splicing languages

      Masami Ito, Peter Leupold, Kayoko Shikishima-Tsuji

         Closure of Language Classes under Bounded Duplication

      Jurgen Dassow, Gyorgy Vaszil

         Ciliate bio-operations on finite string multisets

      Sylvain Schmitz

         Noncanonical LALR(1) Parsing

      K. Lakshmanan

         End-marked Maximal Depth-first Contextual Grammars

      F. Drewes, S. Ewert, C. du Toit, J. Högberg, B. van der Merwe, A. van der Walt

         Bag Context Tree Grammars

      Tomasz Jurdzinski

         The Boolean Closure of Growing Context-Sensitive Languages

      Jean-Pierre BOREL

         Complexity of Degenerated three-dimensional Billiard Words

      Andrei PAUN, Bianca POPA

         P Systems with Proteins on Membranes and Membrane Division

      Vassilis Kountouriotis, Christos Nomikos, Panos Rondogiannis

         Well-Founded Semantics for Boolean Grammars

      D. Caucal

         Synchronization of pushdown automata

      Lutz Priese, Jan Robert Menzel, Monika Schuth

         Some Examples of Semi-rational DAG Languages

      Martin Kutrib and Andreas Malcher

         Context-Dependent Nondeterminism for Pushdown Automata

      Olivier Carton

         A Cobham-like theorem for rational relations

PREVIOUS DLTs

      DLT 2005

      DLT 2004

      DLT 2003


RELATED CONFERENCES

DLT 2006 will take place immediately after the 8th Workshop on Descriptional Complexity of Formal Systems (DCFS 2006) in Las Cruces, New Mexico, USA on June 21-23. The 12th International Computing and Combinatorics Conference (COCOON 2006) and the 11th International Conference on Implementation and Application of Automata (CIAA 2006) will be held in Taipei, Taiwan on August 15-18 and August 21-23, respectively.