Change search
ReferencesLink to record
Permanent link

Direct link
The complexity of the exponential output size problem for top-down and bottom-up tree transducers
Umeå University, Faculty of Science and Technology, Departement of Computing Science.
2001 (English)In: Information and Computation, Vol. 169, no 2, 264-283 p.Article in journal (Refereed) Published
Abstract [en]

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.
URN: urn:nbn:se:umu:diva-21889ISBN: 0890-5401OAI: diva2:212159
Available from: 2009-04-21 Created: 2009-04-21 Last updated: 2009-04-21

Open Access in DiVA

No full text

Other links

<Go to ISI>://000170947100007
By organisation
Departement of Computing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link