{"id":27016,"date":"2026-09-27T20:02:28","date_gmt":"2026-09-27T18:02:28","guid":{"rendered":"https:\/\/www.itspy.cz\/thesis\/advanced-approaches-for-data-languages\/"},"modified":"2026-09-27T20:05:07","modified_gmt":"2026-09-27T18:05:07","slug":"advanced-approaches-for-data-languages","status":"publish","type":"thesis","link":"https:\/\/www.itspy.cz\/en\/thesis\/advanced-approaches-for-data-languages\/","title":{"rendered":"Advanced Approaches for Data Languages"},"content":{"rendered":"<p>Matching regular expressions with back-references (regexes)<br \/>\nis a common task in computer programs. To match these<br \/>\nregexes, current state-of-the-art regex matchers use<br \/>\nbacktracking algorithms with exponential worst-case<br \/>\ncomplexity, or do not support them at all. The exponential<br \/>\nworst-case time complexity makes the backtracking matchers<br \/>\nusing backtracking vulnerable to the so-called regular<br \/>\nexpression denial of service attack (ReDoS), where an<br \/>\nattacker submits a malicious text to a regex matcher<br \/>\nrunning on a server, triggering a large slowdown and<br \/>\ncausing the server to become unresponsive. We present a<br \/>\nrobust regex matcher capable of matching a class of regexes<br \/>\nwith back-references in linear time (for a fixed number of<br \/>\ncapture groups). Our matcher is based on recently<br \/>\nintroduced model of register set automata, which are<br \/>\ncapable of representing the above-mentioned class of<br \/>\nregexes with back-references deterministically. We tested<br \/>\nthe performance of our matcher under simulated ReDoS<br \/>\nattacks on regexes from real-world projects and compared it<br \/>\nagainst state-of-the-art tools. The experiments show that<br \/>\nour matcher is immune to all tested ReDoS attacks; in<br \/>\ncontrast with the state-of-the-art matchers, which on these<br \/>\nattacks suffer from extreme slowdowns.<\/p>\n","protected":false},"featured_media":26795,"template":"","meta":{"_acf_changed":false,"_links_to":"","_links_to_target":""},"university":[189,441],"thesis-year":[466],"class_list":["post-27016","thesis","type-thesis","status-publish","has-post-thumbnail","hentry","thesis-year-466"],"acf":{"autor":"Jan Va\u0161\u00e1k","portret":"","vedouci":"doc. Ing. Ond\u0159ej Leng\u00e1l, Ph.D."},"_links":{"self":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/27016","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis"}],"about":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/types\/thesis"}],"version-history":[{"count":1,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/27016\/revisions"}],"predecessor-version":[{"id":27071,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/27016\/revisions\/27071"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/media\/26795"}],"wp:attachment":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/media?parent=27016"}],"wp:term":[{"taxonomy":"university","embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/university?post=27016"},{"taxonomy":"thesis-year","embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis-year?post=27016"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}