@inproceedings{899646864d954c8f9eff61b4d3f38b01,

title = "From regular expression matching to parsing",

abstract = "Given a regular expression R and a string Q, the regular expression parsing problem is to determine if Q matches R and if so, determine how it matches, e.g., by a mapping of the characters of Q to the characters in R. Regular expression parsing makes finding matches of a regular expression even more useful by allowing us to directly extract subpatterns of the match, e.g., for extracting IP-addresses from internet traffic analysis or extracting subparts of genomes from genetic data bases. We present a new general techniques for efficiently converting a large class of algorithms that determine if a string Q matches regular expression R into algorithms that can construct a corresponding mapping. As a consequence, we obtain the first efficient linear space solutions for regular expression parsing.",

keywords = "Algorithms, Finite automata, Regular expression parsing, Regular expressions",

author = "Philip Bille and G{\o}rtz, {Inge Li}",

year = "2019",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.MFCS.2019.71",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Joost-Pieter Katoen and Pinar Heggernes and Peter Rossmanith",

booktitle = "Proceedings of 44th International Symposium on Mathematical Foundations of Computer Science",

note = "44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",

}