ResearchSpace

On regular expressions with backreferences and transducers

Show simple item record

dc.contributor.author Berglund, Martin
dc.contributor.author Drewes, F
dc.contributor.author Van der Merwe, B
dc.date.accessioned 2019-03-23T13:37:48Z
dc.date.available 2019-03-23T13:37:48Z
dc.date.issued 2018-08
dc.identifier.citation 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 en_US
dc.identifier.uri http://im.saske.sk/ncma2018/ncma2018_ocg332.pdf
dc.identifier.uri http://hdl.handle.net/10204/10837
dc.description Paper presented at the 10th Workshop on Non-Classical Models of Automata and Applications, 8-10th August 2018, Saskatoon, Canada en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.relation.ispartofseries Worklist;22117
dc.subject Backreferences en_US
dc.subject Transducers en_US
dc.title On regular expressions with backreferences and transducers en_US
dc.type Conference Presentation en_US
dc.identifier.apacitation Berglund, M., Drewes, F., & Van der Merwe, B. (2018). On regular expressions with backreferences and transducers. http://hdl.handle.net/10204/10837 en_ZA
dc.identifier.chicagocitation Berglund, Martin, F Drewes, and B Van der Merwe. "On regular expressions with backreferences and transducers." (2018): http://hdl.handle.net/10204/10837 en_ZA
dc.identifier.vancouvercitation Berglund M, Drewes F, Van der Merwe B, On regular expressions with backreferences and transducers; 2018. http://hdl.handle.net/10204/10837 . en_ZA
dc.identifier.ris TY - Conference Presentation AU - Berglund, Martin AU - Drewes, F AU - Van der Merwe, B AB - 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. DA - 2018-08 DB - ResearchSpace DP - CSIR KW - Backreferences KW - Transducers LK - https://researchspace.csir.co.za PY - 2018 T1 - On regular expressions with backreferences and transducers TI - On regular expressions with backreferences and transducers UR - http://hdl.handle.net/10204/10837 ER - en_ZA


Files in this item

Thumbnail
Name: Berglund_22117_20 ...
Size: 354.4Kb
Format: PDF
Description: Conference paper
View/Open

This item appears in the following Collection(s)

Show simple item record