umu.sePublications
Change search
ReferencesLink to record
Permanent link

Direct link
The Output Size Problem for String-to-Tree Transducers
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)ORCID iD: 0000-0001-7349-7693
University of Stellenbosch.
University of Stellenbosch.
2016 (English)In: Proc. 4th Intl. Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016) / [ed] A. Maletti, 2016Conference paper (Refereed)
Abstract [en]

The output size problem, for a string-to-tree transducer, is to determine the rate of growth of the function describing the maximum size of output trees, with respect to the length of the input strings. We study the complexity of this problem. Our motivation is that a solution to the output size problem can be used in order to determine the worst-case matching time (for a given regular expression) of a backtracking regular expression matcher, with respect to the length of the input strings.

Place, publisher, year, edition, pages
2016.
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-122472OAI: oai:DiVA.org:umu-122472DiVA: diva2:939167
Conference
Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016)
Available from: 2016-06-17 Created: 2016-06-17 Last updated: 2016-06-17

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer 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: 20 hits
ReferencesLink to record
Permanent link

Direct link