Sökning: id:"swepub:oai:DiVA.org:umu-88232" >
Analyzing catastrop...
Analyzing catastrophic backtracking behavior in practical regular expression matching
-
- Berglund, Martin, 1981- (författare)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
- Drewes, Frank, 1963- (författare)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
- van der Merwe, Brink (författare)
- University of Stellenbosch, South Africa,Dept of Mathematical Sciences, Computer Science Division
-
(creator_code:org_t)
- Open Publishing Association, 2014
- 2014
- Engelska.
-
Ingår i: Proceedings 14th international conference on <em>automata and formal languages</em> (AFL 2014). - : Open Publishing Association. ; , s. 109-123
- Relaterad länk:
-
https://cgi.cse.unsw...
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- We consider in some detail how regular expression matching happens in Java, as a popular representative of the category of regex-directed matching engines. We extract a slightly idealized algorithm for this scenario. Next we define an automata model which captures all the aspects needed to perform matching, of the Java style, in a formal way. Finally, two types of static analysis, which take a regular expression and tells whether there exists a family of strings which make Java-style matching run in exponential time, are done.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- regular expressions
- catastrophic backtracking
- static analysis
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)