Time complexity analysis of backtracking regular expression matching is a procedure that, for a given regular expression, determines whether or not its matching runs in polynomial time. If it runs in polynomial time, the analysis also determines the degree of the polynomial.

• RegexStaticAnalysis
• RXXR2 regular expression static analyzer

We present a procedure to solve the satisfiability problem of string constraints consisting of (i) string concatenation and rational transductions of string variables restricted to be in the "straight-line" fragment, (ii) regular constraints to string variables, and (iii) integer constraints involving the length of string variables. We represent each atomic string constraint by a streaming string transducer.

• Masaki Kamano, Taiga Fukuda, Yasuhiko Minamide, Solving String Constraints with Nondeterminis- tic Streaming String Transducers and Parikh Automata, Computer Software, accepted, in Japanese, 2022. (authors version) (Solver)
• Solving String Constraints with Streaming String Transducers, Qizhen Zhu, Hitoshi Akama, Yasuhiko Minamide, Journal of Information Processing, Vol. 27, p. 810-821, 2019. (DOI) (Solver)