The complexity of computing the behaviour of lattice automata on infinite trees (Q2447756)

The authors consider Büchi tree automata over infinite unlabelled \(k\)-ary trees with weights in a countable lattice whose operations are computable in polynomial time. It is observed that one can check in exponential time whether a given automaton computes a given value (unlike stated in the paper, this upper bound actually holds only under the stronger assumption that in the lattice arbitrary expressions can be evaluated in polynomial time), and a lattice is constructed for which this decision problem is PSPACE-hard. If the result of each operation in the lattice is bounded by the size of the arguments, then the problem can be decided in polynomial space, and it is shown that there exists a lattice with this property such that the problem is both NP-hard and coNP-hard. All lower bounds are obtained for automata over the tree of arity one, which perform only finitely many steps and then remain in the final state forever; therefore, these lower bounds can be formulated already for finite words over a unary alphabet.