Memoized Regular Expressions
2021 (Engelska)Ingå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-52Konferensbidrag, Publicerat paper (Refereegranskat)
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.
Ort, förlag, år, upplaga, sidor
Springer, 2021. s. 39-52
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12803
Nyckelord [en]
Ambiguity, Regular expression matching, Memoization
Nationell ämneskategori
Datavetenskap (datalogi)
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
Konferens
25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021
Anmärkning
Also part of the Theoretical Computer Science and General Issues book sub series (LNTCS, volume 12803)
2022-03-022022-03-022022-03-03Bibliografiskt granskad