دورية أكاديمية
Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
| العنوان: | Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching |
|---|---|
| المؤلفون: | Martin Berglund, Frank Drewes, Brink van der Merwe |
| المصدر: | Electronic Proceedings in Theoretical Computer Science, Vol 151, Iss Proc. AFL 2014, Pp 109-123 (2014) |
| بيانات النشر: | Open Publishing Association, 2014. |
| سنة النشر: | 2014 |
| المجموعة: | LCC:Mathematics LCC:Electronic computers. Computer science |
| مصطلحات موضوعية: | Mathematics, QA1-939, Electronic computers. Computer science, QA75.5-76.95 |
| الوصف: | We develop a formal perspective on how regular expression matching works in Java, a popular representative of the category of regex-directed matching engines. In particular, we define an automata model which captures all the aspects needed to study such matching engines in a formal way. Based on this, we propose two types of static analysis, which take a regular expression and tell whether there exists a family of strings which makes Java-style matching run in exponential time. |
| نوع الوثيقة: | article |
| وصف الملف: | electronic resource |
| اللغة: | English |
| تدمد: | 2075-2180 |
| Relation: | http://arxiv.org/pdf/1405.5599v1; https://doaj.org/toc/2075-2180 |
| DOI: | 10.4204/EPTCS.151.7 |
| URL الوصول: | https://doaj.org/article/ec14689490654d7baecf7fdb554af28b |
| رقم الأكسشن: | edsdoj.14689490654d7baecf7fdb554af28b |
| قاعدة البيانات: | Directory of Open Access Journals |
Full Text Finder | تدمد: | 20752180 |
|---|---|
| DOI: | 10.4204/EPTCS.151.7 |