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)