Memoized Regular Expressions
2021 (engelsk)Inngår i: Implementation and Application of Automata: 25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021, Proceedings / [ed] Sebastian Maneth, Springer, 2021, s. 39-52Konferansepaper, Publicerat paper (Fagfellevurdert)
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.
sted, utgiver, år, opplag, sider
Springer, 2021. s. 39-52
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12803
Emneord [en]
Ambiguity, Regular expression matching, Memoization
HSV kategori
Identifikatorer
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 (tryckt)ISBN: 978-3-030-79121-6 (digital)OAI: oai:DiVA.org:umu-192865DiVA, id: diva2:1641659
Konferanse
25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021
Merknad
Also part of the Theoretical Computer Science and General Issues book sub series (LNTCS, volume 12803)
2022-03-022022-03-022022-03-03bibliografisk kontrollert