The output size problem for string-to-tree transducers

DOI10.25596/JALC-2018-019MaRDI QIDQ5376329zbMATH OpenOpenAlexFDO

Authors Martin Berglund, Brink van der Merwe, Frank Drewes

Publication date 17 September 2018

Full work available at URL https://researchspace.csir.co.za/dspace/handle/10204/10756

zbMATH Keywords

ambiguityoutput sizeregular expression matcherstring-to-tree transducer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Exponential output size of top-down tree transducers
• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• The complexity of compositions of deterministic tree transducers
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity

Cited in

(3)

• The complexity of the exponential output size problem for top-down and bottom-up tree transducers
• The Complexity of Tree Transducer Output Languages
• Exponential output size of top-down tree transducers

This page was built for publication: The output size problem for string-to-tree transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376329)