Memoized Regular Expressions
2021 (English)In: Implementation and Application of Automata: 25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021, Proceedings / [ed] Sebastian Maneth, Springer, 2021, p. 39-52Conference paper, Published paper (Refereed)
Abstract [en]
We extend non-deterministic finite automata (NFAs) and regular expressions (regexes) by adding memoization to these formalisms. These extensions are aimed at improving the matching time of backtracking regex matchers. Additionally, we discuss how to extend the concept of ambiguity in order to be applicable to memoized extensions of regexes and NFAs. These more general notions of ambiguity can be used to analyze the matching time of backtracking regex matchers enhanced with memoization.
Place, publisher, year, edition, pages
Springer, 2021. p. 39-52
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12803
Keywords [en]
Ambiguity, Regular expression matching, Memoization
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-192865DOI: 10.1007/978-3-030-79121-6_4Scopus ID: 2-s2.0-85112599570ISBN: 978-3-030-79120-9 (print)ISBN: 978-3-030-79121-6 (electronic)OAI: oai:DiVA.org:umu-192865DiVA, id: diva2:1641659
Conference
25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021
Note
Also part of the Theoretical Computer Science and General Issues book sub series (LNTCS, volume 12803)
2022-03-022022-03-022022-03-03Bibliographically approved