Sökning: id:"swepub:oai:DiVA.org:umu-149995" >
On Regular Expressi...
On Regular Expressions with Backreferences and Transducers
-
- Berglund, Martin (författare)
- Stellenbosch University
-
- Drewes, Frank (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Merwe, Brink van der (författare)
- University of Stellenbosch
-
(creator_code:org_t)
- Österreichische Computer Gesellschaft, 2018
- 2018
- Engelska.
-
Ingår i: Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018). - : Österreichische Computer Gesellschaft. - 9783903035218 ; , s. 49-64
- Relaterad länk:
-
https://dblp.uni-tri...
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer Science
- datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas