Single-valuedness of tree transducers is decidable in polynomial time (Q685348)

A bottom-up finite-state tree transducer (FST) is a generalization of a generalized sequential machine that outputs a tree while scanning an input tree in a bottom-up fashion. A deterministic polynomial time algorithm is constructed to decide whether a given FST is single-valued. It follows from this result that the equivalence problem of deterministic FSTs can be decided in deterministic polynomial time.