Modern regular expression matching software features many extensions, some general while some are very narrowly specified. Here we consider the generalization of adding a class of operators which can be described by, e.g. finite-state transducers. Combined with backreferences they enable new classes of languages to be matched. The addition of finite-state transducers is shown to make membership testing undecidable. Following this result, we study the complexity of membership testing for various restricted cases of the model.
Reference:
Berglund, M., Drewes, F. and van der Merwe, B. 2018. On regular expressions with backreferences and transducers. 10th Workshop on Non-Classical Models of Automata and Applications, 8-10th August 2018, Saskatoon, Canada
Berglund, M., Drewes, F., & Van der Merwe, B. (2018). On regular expressions with backreferences and transducers. http://hdl.handle.net/10204/10837
Berglund, Martin, F Drewes, and B Van der Merwe. "On regular expressions with backreferences and transducers." (2018): http://hdl.handle.net/10204/10837
Berglund M, Drewes F, Van der Merwe B, On regular expressions with backreferences and transducers; 2018. http://hdl.handle.net/10204/10837 .
