3.30 pm, Lecture Hall 1
Polynomial Tree Automata
Helmut Seidl
Technical Univ. of Munich, Germany.
29-09-17

---

Abstract

A polynomial tree automaton can be considered as an attribute grammar with synthesized attributes only where the values of attributes at a node are determined by means of polynomial functions from the attributes of the ancestors of the node.

The presentation explains how the equivalence problem for various classes of tree-to-string transducers can be reduced to the question whether or not a conjunction of polynomial equalities holds for all possible attribute values at the root. In particular, we consider the classes of linear deterministic tree-to-string transducers, streaming tree transducers, and general deterministic topdown tree-to-string transducers.

We prove that polynomial equalities are decidable for general polynomial tree automata. This central result is obtained by relying on inductive polynomial invariants, as known from program proving, and abstract interpretation. We also identify subclasses of polynomial automata where explicit complexity bounds can be provided and show how these translate into into complexity bounds for the equivalence problem of classes of deterministic tree transducers.

[Joint work with Sebastian Maneth (Edinburgh) and Gregor Kemper (Munich)]