@conference{199, author = {Martin Berglund and F. Drewes and Brink van der Merwe}, title = {On Regular Expressions with Backreferences and Transducers}, abstract = {Modern regular expression matching software features many extensions, some general while some are very narrowly speci ed. Here we consider the generalization of adding a class of operators which can be described by, e.g. nite-state transducers. Combined with backreferences they enable new classes of languages to be matched. The addition of nite-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.}, year = {2018}, journal = {10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018)}, chapter = {1-19}, month = {21/08-22/08}, }