The complexity of computing the behaviour of lattice automata on infinite trees

DOI10.1016/J.TCS.2014.02.036MaRDI QIDQ2447756zbMATH OpenOpenAlexFDO

Authors Karsten Lehmann, Rafael Peñaloza

Publication date 29 April 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.02.036

behaviour computation computational complexity lattice automaton tree automaton weighted automaton

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The complexity of computing the behaviour of lattice automata on infinite trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447756)