ResearchSpace

The output size problem for string-to-tree transducers

Show simple item record

dc.contributor.author Berglund, Martin
dc.contributor.author Drewes, F
dc.contributor.author Van der Merwe, B
dc.date.accessioned 2019-03-07T12:13:06Z
dc.date.available 2019-03-07T12:13:06Z
dc.date.issued 2018-04
dc.identifier.citation Berglund, M., Drewes, F. and van der Merwe, B. 2018. The output size problem for string-to-tree transducers. Journal of Automata, Languages and Combinatorics, vol. 23: 19-38 en_US
dc.identifier.issn 2567-3785
dc.identifier.issn 1430-189X
dc.identifier.uri DOI: 10.25596/jalc-2018-019
dc.identifier.uri https://www.jalc.de/issues/2018/issue_23_1-3/jalc-2018-019-038.php
dc.identifier.uri http://hdl.handle.net/10204/10756
dc.description Due to copyright restrictions, the attached PDF file contains the accepted version of the published item. The article may be used for non-commercial purposes only.The definitive version is published in Journal of Automata, Languages and Combinatorics. For access to the published version, kindly consult the publisher's website: https://www.jalc.de/issues/2018/issue_23_1-3/jalc-2018-019-038.php en_US
dc.description.abstract The output size problem, for a string-to-tree transducer, is to determine the asymptotic behavior of the function describing the maximum size of output trees, with respect to the length of input strings. We show that the problem to determine, for a given regular expression, the worst-case matching time of a backtracking regular expression matcher, can be reduced to the output size problem. The latter can, in turn, be solved by determining the degree of ambiguity of a non-deterministic finite automaton. en_US
dc.language.iso en en_US
dc.publisher Institut für Informatik en_US
dc.relation.ispartofseries Worklist;22096
dc.subject Backtracking regular expression matchers en_US
dc.subject NFA ambiguity en_US
dc.subject Output size en_US
dc.subject String-to-tree transducers en_US
dc.title The output size problem for string-to-tree transducers en_US
dc.type Article en_US
dc.identifier.apacitation Berglund, M., Drewes, F., & Van der Merwe, B. (2018). The output size problem for string-to-tree transducers. http://hdl.handle.net/10204/10756 en_ZA
dc.identifier.chicagocitation Berglund, Martin, F Drewes, and B Van der Merwe "The output size problem for string-to-tree transducers." (2018) http://hdl.handle.net/10204/10756 en_ZA
dc.identifier.vancouvercitation Berglund M, Drewes F, Van der Merwe B. The output size problem for string-to-tree transducers. 2018; http://hdl.handle.net/10204/10756. en_ZA
dc.identifier.ris TY - Article AU - Berglund, Martin AU - Drewes, F AU - Van der Merwe, B AB - The output size problem, for a string-to-tree transducer, is to determine the asymptotic behavior of the function describing the maximum size of output trees, with respect to the length of input strings. We show that the problem to determine, for a given regular expression, the worst-case matching time of a backtracking regular expression matcher, can be reduced to the output size problem. The latter can, in turn, be solved by determining the degree of ambiguity of a non-deterministic finite automaton. DA - 2018-04 DB - ResearchSpace DP - CSIR KW - Backtracking regular expression matchers KW - NFA ambiguity KW - Output size KW - String-to-tree transducers LK - https://researchspace.csir.co.za PY - 2018 SM - 2567-3785 SM - 1430-189X T1 - The output size problem for string-to-tree transducers TI - The output size problem for string-to-tree transducers UR - http://hdl.handle.net/10204/10756 ER - en_ZA


Files in this item

Thumbnail
Name: Berglund_22096_20 ...
Size: 575.6Kb
Format: PDF
Description: Article (accepted ...
View/Open

This item appears in the following Collection(s)

Show simple item record