Home » Research » Research outputs » On Regular Expressions with Backreferences and Transducers

On Regular Expressions with Backreferences and Transducers

2018

  • Authors:
    Martin Berglund , Drewes, F , Brink van der Merwe

    Publication date:
    2018

    Institution:
    CSIR Meraka Institute, Stellenbosch University

    Output type:
    Conference proceedings

    Abstract:

    Modern regular expression matching software features many extensions, some general while some are very narrowly specied. 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.

    Document file:
    Proof of peer-review from publisher: