The complexity of the exponential output size problem for top-down and bottom-up tree transducers
2001 (English)In: Information and Computation, Vol. 169, no 2, 264-283 p.Article in journal (Refereed) Published
The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers, (C) 2001 Academic Press.
Place, publisher, year, edition, pages
2001. Vol. 169, no 2, 264-283 p.
IdentifiersURN: urn:nbn:se:umu:diva-21889ISBN: 0890-5401OAI: oai:DiVA.org:umu-21889DiVA: diva2:212159