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 |