Invited Speakers

  • Hendrik J. Hoogeboom (Leiden University, The Netherlands)

    • Automata Walking over Trees. In classic language theory trees are accepted using a bottom-up tree evaluation. Less well-known is the tree version of the two-way automaton that walks along the edges of a tree inspecting its properties. The problem whether these automata accept all regular languages has been only recently solved (in the negative). We suggest to use pebbles not to get lost in the tree, inspired by Hansel and Gretel. Selected nodes in the tree are marked so that they can be revisited later. Adding this feature must be done in a proper way. If pebbles can be retrieved in an arbitrary order, or when an infinite supply of them is available, we can use them to count and end up with nonregular languages.

  • Joachim Niehren (INRIA Lille Nord Europe, France)

    • Streaming Tree Automata and XPath. Streaming algorithms for query answering are of prime interest to XML database processing. In this talk we survey recent results on streaming for XPath and tree automata defined queries. We start with lower bounds for nondeterministic devices, showing that even small syntactic fragments of XPath are not streamable unless P=NP. We then discuss upper bounds for deterministic devices, including fragments of Forward XPath with semantic restrictions, that we can prove streamable by compilation to deterministic nested word automata in P-time. This shows that determinism is the most essential requirement for streamability.

  • Klaus Sutner (Carnegie Mellon University, USA)

    • Cellular Automata, Decidability and Phasespace. Cellular automata can be used to provide prototype models of physics-like computation. We study decidability issues in the phasespace of these automata, construed as structures in some suitable logic. In dimension one, slightly more than the first order theory is decidable. We comment on connections between this model and the lack of "natural" intermediate degrees.

Program Committee

  • Henning Bordihn (Universität Potsdam, Germany)
  • Rudolf Freund (Technische Universität Wien, Austria)
  • Mika Hirvensalo (University of Turku, Finland)
  • Markus Holzer (Universität Giessen, Germany)
  • Johanna Högberg (Umeå University, Sweden)
  • Tomasz Jurdzinski (Wroclaw University, Poland)
  • Martin Kutrib (Universität Giessen, Germany)
  • Maurice Margenstern (Université de Metz, France)
  • Carlo Mereghetti (Universitā degli Studi di Milano, Italy)
  • Friedrich Otto (Universität Kassel, Germany)
  • Hiroshi Umeo (Osaka Electro-Communication University, Japan)
  • Kai Salomaa (Queen's University, Canada)