3 papers
cs.CC2026
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…
cs.FL2025
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…
cs.FL2024
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 most modern programming languages, such as Java, Python, JavaScript and more, support regular expressio…