4 papers
Hardness of Regular Expression Matching with Extensions
Taisei Nogami, Yoshiki Nakamura, Tachio Terauchi
Regular expression matching asks whether a given regular expression of length matches a given string of length , and its time complexity is fairly well understood. Meanwhile…
Efficient Matching of Some Fundamental Regular Expressions with Backreferences
Taisei Nogami, Tachio Terauchi
Regular expression matching is of practical importance due to its widespread use in real-world applications. In practical use, regular expressions are often used with real-world ex…
Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
Taisei Nogami, Tachio Terauchi
Backreference is a well-known practical extension of regular expressions and is supported by the regular expression engines in the standard libraries of most modern programming lan…
On the Expressive Power of Regular Expressions with Backreferences
Taisei Nogami, Tachio Terauchi
A rewb is a regular expression extended with a feature called backreference. It is broadly known that backreference is a practical extension of regular expressions, and is supporte…