umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Identifiers
URN: urn:nbn:se:umu:diva-21889ISBN: 0890-5401 OAI: oai:DiVA.org:umu-21889DiVA: 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf