3 papers
cs.CC2026
Hardness of Regular Expression Matching with Extensions
Taisei Nogami, Yoshiki Nakamura, Tachio Terauchi
The regular expression matching problem asks whether a given regular expression of length matches a given string of length . As is well known, the problem can be solved in $…
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…