Invited Speakers

  • Tomasz Jurdzinski (Wroclaw University, Poland)

    • Growing Grammars and Length-Reducing Automata. Growing Context-Sensitive Grammars (GCSG)form a very natural restricted version of context-sensitive grammars. The language family defined by GCSG complements the Chomsky hierarchy in a natural way and it enjoys many interesting properties. In particular, this class forms an abstract family of languages, its membership problem is solvable in polynomial time and it possesses a machine model characterization by so-called length-reducing two-pushdown automata (lrTPDA).

      We will review main results concerning the class of growing context-sensitive languages and its deterministic counterpart. We will also discuss some generalizations of the model of lrTPDAs and connections of lrTPDAs to other new models of automata. We conclude with some open problems and directions for further research.

  • Andreas Maletti (Universitat Rovira i Virgili, Spain)

    • Tree Transducers in Machine Translation. We will review the applications of tree transducers in syntax-based machine translation. The classical models of top-down and bottom-up tree transducers are not powerful enough for most of those applications, which led to the reemergence of non-classical tree transducer models such as the extended tree transducers of Arnold & Dauchet, the multi bottom-up tree transducers of Lilin, and the embedded tree transducers of Shieber. We explore those and several other tree transformation devices with a strong focus on applications. In addition, we present the main results and compare them with the corresponding results for the classical devices. We conclude with several open problems and directions for further research.

Program Committee

  • Henning Bordihn (Universität Potsdam, Germany)
  • Rudolf Freund (Technische Universität Wien, Austria)
  • Thomas Hinze (Friedrich-Schiller-Universität Jena, Germany)
  • Mika Hirvensalo (University of Turku, Finland)
  • Markus Holzer (Universität Giessen, Germany)
  • Martin Kutrib (Universität Giessen, Germany)
  • František Mráz (Charles University Prague, Czech Republic)
  • Alexander Okhotin (University of Turku, Finland)
  • Friedrich Otto (Universität Kassel, Germany)
  • Beatrice Palano (Università degli Studi di Milano, Italy)
  • Daniel Reidenbach (Loughborough University, United Kingdom)
  • Kai Salomaa (Queen's University, Canada)
  • György Vaszil (MTA SZTAKI, Hungary)
  • Sergey Verlan (University Paris XII, France)
  • Sheng Yu (University of Western Ontario, Canada)