The Output Size Problem for String-to-Tree Transducers
2016 (English)In: Proc. 4th Intl. Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016) / [ed] A. Maletti, 2016Conference paper (Refereed)
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
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-122472OAI: oai:DiVA.org:umu-122472DiVA: diva2:939167
Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016)