1 %% This BibTeX bibliography file was created using BibDesk. |
1 %% This BibTeX bibliography file was created using BibDesk. |
2 %% https://bibdesk.sourceforge.io/ |
2 %% https://bibdesk.sourceforge.io/ |
3 |
3 |
4 %% Created for CS TAN at 2022-03-16 16:38:47 +0000 |
4 %% Created for CS TAN at 2022-05-23 18:43:50 +0100 |
5 |
5 |
6 |
6 |
7 %% Saved with string encoding Unicode (UTF-8) |
7 %% Saved with string encoding Unicode (UTF-8) |
8 |
8 |
|
9 |
|
10 |
|
11 @article{Turo_ov__2020, |
|
12 author = {Lenka Turo{\v{n}}ov{\'{a}} and Luk{\'{a}}{\v{s}} Hol{\'{\i}}k and Ond{\v{r}}ej Leng{\'{a}}l and Olli Saarikivi and Margus Veanes and Tom{\'{a}}{\v{s}} Vojnar}, |
|
13 date-added = {2022-05-23 18:43:04 +0100}, |
|
14 date-modified = {2022-05-23 18:43:04 +0100}, |
|
15 doi = {10.1145/3428286}, |
|
16 journal = {Proceedings of the {ACM} on Programming Languages}, |
|
17 month = {nov}, |
|
18 number = {{OOPSLA}}, |
|
19 pages = {1--30}, |
|
20 publisher = {Association for Computing Machinery ({ACM})}, |
|
21 title = {Regex matching with counting-set automata}, |
|
22 url = {https://doi.org/10.1145%2F3428286}, |
|
23 volume = {4}, |
|
24 year = 2020, |
|
25 bdsk-url-1 = {https://doi.org/10.1145%2F3428286}, |
|
26 bdsk-url-2 = {https://doi.org/10.1145/3428286}} |
|
27 |
9 @article{Rathnayake2014StaticAF, |
28 @article{Rathnayake2014StaticAF, |
10 title={Static Analysis for Regular Expression Exponential Runtime via Substructural Logics}, |
29 author = {Asiri Rathnayake and Hayo Thielecke}, |
11 author={Asiri Rathnayake and Hayo Thielecke}, |
30 journal = {ArXiv}, |
12 journal={ArXiv}, |
31 title = {Static Analysis for Regular Expression Exponential Runtime via Substructural Logics}, |
13 year={2014}, |
32 volume = {abs/1405.7058}, |
14 volume={abs/1405.7058} |
33 year = {2014}} |
15 } |
|
16 |
34 |
17 @inproceedings{Weideman2017Static, |
35 @inproceedings{Weideman2017Static, |
18 title={Static analysis of regular expressions}, |
36 author = {Nicolaas Weideman}, |
19 author={Nicolaas Weideman}, |
37 title = {Static analysis of regular expressions}, |
20 year={2017} |
38 year = {2017}} |
21 } |
|
22 |
39 |
23 @inproceedings{RibeiroAgda2017, |
40 @inproceedings{RibeiroAgda2017, |
24 abstract = {We describe the formalization of a regular expression (RE) parsing algorithm that produces a bit representation of its parse tree in the dependently typed language Agda. The algorithm computes bit-codes using Brzozowski derivatives and we prove that produced codes are equivalent to parse trees ensuring soundness and completeness w.r.t an inductive RE semantics. We include the certified algorithm in a tool developed by us, named verigrep, for regular expression based search in the style of the well known GNU grep. Practical experiments conducted with this tool are reported.}, |
41 abstract = {We describe the formalization of a regular expression (RE) parsing algorithm that produces a bit representation of its parse tree in the dependently typed language Agda. The algorithm computes bit-codes using Brzozowski derivatives and we prove that produced codes are equivalent to parse trees ensuring soundness and completeness w.r.t an inductive RE semantics. We include the certified algorithm in a tool developed by us, named verigrep, for regular expression based search in the style of the well known GNU grep. Practical experiments conducted with this tool are reported.}, |
25 address = {New York, NY, USA}, |
42 address = {New York, NY, USA}, |
26 articleno = {4}, |
43 articleno = {4}, |
61 date-added = {2019-08-18 17:57:30 +0000}, |
78 date-added = {2019-08-18 17:57:30 +0000}, |
62 date-modified = {2019-08-18 18:00:13 +0000}, |
79 date-modified = {2019-08-18 18:00:13 +0000}, |
63 journal = {arXiv:1405.7058}, |
80 journal = {arXiv:1405.7058}, |
64 title = {Static Analysis for Regular Expression Exponential Runtime via Substructural Logics}, |
81 title = {Static Analysis for Regular Expression Exponential Runtime via Substructural Logics}, |
65 year = {2017}} |
82 year = {2017}} |
|
83 |
66 @article{campeanu2003formal, |
84 @article{campeanu2003formal, |
67 title={A formal study of practical regular expressions}, |
85 author = {C{\^a}mpeanu, Cezar and Salomaa, Kai and Yu, Sheng}, |
68 author={C{\^a}mpeanu, Cezar and Salomaa, Kai and Yu, Sheng}, |
86 journal = {International Journal of Foundations of Computer Science}, |
69 journal={International Journal of Foundations of Computer Science}, |
87 number = {06}, |
70 volume={14}, |
88 pages = {1007--1018}, |
71 number={06}, |
89 publisher = {World Scientific}, |
72 pages={1007--1018}, |
90 title = {A formal study of practical regular expressions}, |
73 year={2003}, |
91 volume = {14}, |
74 publisher={World Scientific} |
92 year = {2003}} |
75 } |
|
76 |
93 |
77 @article{alfred2014algorithms, |
94 @article{alfred2014algorithms, |
78 title={Algorithms for finding patterns in strings}, |
95 author = {Alfred, V}, |
79 author={Alfred, V}, |
96 journal = {Algorithms and Complexity}, |
80 journal={Algorithms and Complexity}, |
97 pages = {255}, |
81 volume={1}, |
98 publisher = {Elsevier}, |
82 pages={255}, |
99 title = {Algorithms for finding patterns in strings}, |
83 year={2014}, |
100 volume = {1}, |
84 publisher={Elsevier} |
101 year = {2014}} |
85 } |
|
86 |
|
87 |
102 |
88 @article{CAMPEANU2009Intersect, |
103 @article{CAMPEANU2009Intersect, |
89 title = {On the intersection of regex languages with regular languages}, |
104 abstract = {In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255--300] and rigorously in 2003 by C{\^a}mpeanu, Salomaa and Yu [C. C{\^a}mpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007--1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines --- regex automata systems (RAS) --- which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.}, |
90 journal = {Theoretical Computer Science}, |
105 author = {Cezar C{\^a}mpeanu and Nicolae Santean}, |
91 volume = {410}, |
106 doi = {https://doi.org/10.1016/j.tcs.2009.02.022}, |
92 number = {24}, |
107 issn = {0304-3975}, |
93 pages = {2336-2344}, |
108 journal = {Theoretical Computer Science}, |
94 year = {2009}, |
109 keywords = {Extended regular expression, Regex automata system, Regex}, |
95 note = {Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu}, |
110 note = {Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu}, |
96 issn = {0304-3975}, |
111 number = {24}, |
97 doi = {https://doi.org/10.1016/j.tcs.2009.02.022}, |
112 pages = {2336-2344}, |
98 url = {https://www.sciencedirect.com/science/article/pii/S0304397509001789}, |
113 title = {On the intersection of regex languages with regular languages}, |
99 author = {Cezar Câmpeanu and Nicolae Santean}, |
114 url = {https://www.sciencedirect.com/science/article/pii/S0304397509001789}, |
100 keywords = {Extended regular expression, Regex automata system, Regex}, |
115 volume = {410}, |
101 abstract = {In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.} |
116 year = {2009}, |
102 } |
117 bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397509001789}, |
103 |
118 bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2009.02.022}} |
104 |
119 |
105 @article{nielson11bcre, |
120 @article{nielson11bcre, |
106 author = {Lasse Nielsen, Fritz Henglein}, |
121 author = {Lasse Nielsen, Fritz Henglein}, |
107 date-added = {2019-07-03 21:09:39 +0000}, |
122 date-added = {2019-07-03 21:09:39 +0000}, |
108 date-modified = {2019-07-03 21:17:33 +0000}, |
123 date-modified = {2019-07-03 21:17:33 +0000}, |
109 journal = {LATA}, |
124 journal = {LATA}, |
110 title = {Bit-coded Regular Expression Parsing}, |
125 title = {Bit-coded Regular Expression Parsing}, |
111 year = {2011}, |
126 year = {2011}, |
112 bdsk-file-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxA1Li4vLi4vLi4vTXkgTWFjIChNYWNCb29rLVBybykvRGVza3RvcC9mcml0ei1wYXBlci5wZGZPEQF+AAAAAAF+AAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAAAAAAAAQkQAAf////8PZnJpdHotcGFwZXIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/////wAAAAAAAAAAAAAAAAADAAMAAAogY3UAAAAAAAAAAAAAAAAAB0Rlc2t0b3AAAAIAQi86VXNlcnM6Y3N0YW46RHJvcGJveDpNeSBNYWMgKE1hY0Jvb2stUHJvKTpEZXNrdG9wOmZyaXR6LXBhcGVyLnBkZgAOACAADwBmAHIAaQB0AHoALQBwAGEAcABlAHIALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAEBVc2Vycy9jc3Rhbi9Ecm9wYm94L015IE1hYyAoTWFjQm9vay1Qcm8pL0Rlc2t0b3AvZnJpdHotcGFwZXIucGRmABMAAS8AABUAAgAM//8AAAAIAA0AGgAkAFwAAAAAAAACAQAAAAAAAAAFAAAAAAAAAAAAAAAAAAAB3g==}} |
127 bdsk-file-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxA1Li4vLi4vLi4vTXkgTWFjIChNYWNCb29rLVBybykvRGVza3RvcC9mcml0ei1wYXBlci5wZGZPEQF+AAAAAAF+AAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAAAAAAAAQkQAAf////8PZnJpdHotcGFwZXIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/////wAAAAAAAAAAAAAAAAADAAMAAAogY3UAAAAAAAAAAAAAAAAAB0Rlc2t0b3AAAAIAQi86VXNlcnM6Y3N0YW46RHJvcGJveDpNeSBNYWMgKE1hY0Jvb2stUHJvKTpEZXNrdG9wOmZyaXR6LXBhcGVyLnBkZgAOACAADwBmAHIAaQB0AHoALQBwAGEAcABlAHIALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAEBVc2Vycy9jc3Rhbi9Ecm9wYm94L015IE1hYyAoTWFjQm9vay1Qcm8pL0Rlc2t0b3AvZnJpdHotcGFwZXIucGRmABMAAS8AABUAAgAM//8AAAAIAA0AGgAkAFwAAAAAAAACAQAAAAAAAAAFAAAAAAAAAAAAAAAAAAAB3g==}} |
|
128 |
113 @software{regexploit2021, |
129 @software{regexploit2021, |
114 author = {Ben Caller, Luca Carettoni}, |
130 author = {Ben Caller, Luca Carettoni}, |
115 date-added = {2020-11-24 00:00:00 +0000}, |
131 date-added = {2020-11-24 00:00:00 +0000}, |
116 date-modified = {2021-05-07 00:00:00 +0000}, |
132 date-modified = {2021-05-07 00:00:00 +0000}, |
117 keywords = {ReDos static analyser}, |
133 keywords = {ReDos static analyser}, |
118 month = {May}, |
134 month = {May}, |
119 title = {regexploit}, |
135 title = {regexploit}, |
120 url = {https://github.com/doyensec/regexploit}, |
136 url = {https://github.com/doyensec/regexploit}, |
121 year = {2021} |
137 year = {2021}, |
122 } |
138 bdsk-url-1 = {https://github.com/doyensec/regexploit}} |
123 |
139 |
124 @misc{KuklewiczHaskell, |
140 @misc{KuklewiczHaskell, |
125 title = {Regex Posix}, |
|
126 author = {Kuklewicz}, |
141 author = {Kuklewicz}, |
127 keywords = {Buggy C POSIX Lexing Libraries}, |
142 keywords = {Buggy C POSIX Lexing Libraries}, |
|
143 title = {Regex Posix}, |
128 url = {https://wiki.haskell.org/Regex_Posix}, |
144 url = {https://wiki.haskell.org/Regex_Posix}, |
129 year = {2017} |
145 year = {2017}, |
130 } |
146 bdsk-url-1 = {https://wiki.haskell.org/Regex_Posix}} |
|
147 |
131 @misc{regex101, |
148 @misc{regex101, |
|
149 author = {Firas Dib}, |
|
150 keywords = {regex tester debugger}, |
132 title = {regex101}, |
151 title = {regex101}, |
133 author = {Firas Dib}, |
152 url = {https://regex101.com/}, |
134 year = {2011}, |
153 year = {2011}, |
135 url = {https://regex101.com/}, |
154 bdsk-url-1 = {https://regex101.com/}} |
136 keywords = {regex tester debugger} |
155 |
137 } |
|
138 @misc{atomEditor, |
156 @misc{atomEditor, |
|
157 author = {Dunno}, |
|
158 keywords = {text editor}, |
139 title = {Atom Editor}, |
159 title = {Atom Editor}, |
140 author = {Dunno}, |
160 url = {https://atom.io}, |
141 year = {2022}, |
161 year = {2022}, |
142 url = {https://atom.io}, |
162 bdsk-url-1 = {https://atom.io}} |
143 keywords = {text editor} |
163 |
144 } |
|
145 @techreport{grathwohl2014crash, |
164 @techreport{grathwohl2014crash, |
146 title={A Crash-Course in Regular Expression Parsing and Regular Expressions as Types}, |
165 author = {Grathwohl, Niels Bj{\o}rn Bugge and Henglein, Fritz and Rasmussen, Ulrik Terp}, |
147 author={Grathwohl, Niels Bj{\o}rn Bugge and Henglein, Fritz and Rasmussen, Ulrik Terp}, |
166 institution = {Technical report, University of Copenhagen}, |
148 year={2014}, |
167 title = {A Crash-Course in Regular Expression Parsing and Regular Expressions as Types}, |
149 institution={Technical report, University of Copenhagen} |
168 year = {2014}} |
150 } |
|
151 |
169 |
152 @misc{SE16, |
170 @misc{SE16, |
153 author = {StackStatus}, |
171 author = {StackStatus}, |
154 date-added = {2019-06-26 11:28:41 +0000}, |
172 date-added = {2019-06-26 11:28:41 +0000}, |
155 date-modified = {2019-06-26 16:07:31 +0000}, |
173 date-modified = {2019-06-26 16:07:31 +0000}, |