Sökning: id:"swepub:oai:DiVA.org:umu-67738" >
Cuts in Regular Exp...
Cuts in Regular Expressions
-
- Berglund, Martin, 1981- (författare)
- Umeå universitet,Institutionen för datavetenskap,Natural and Formal Languages
-
- Björklund, Henrik, 1973- (författare)
- Umeå universitet,Institutionen för datavetenskap,Natural and Formal Languages
-
- Drewes, Frank, 1963- (författare)
- Umeå universitet,Institutionen för datavetenskap,Natural and Formal Languages
-
visa fler...
-
- van der Merwe, Brink (författare)
- Stellenbosch University, South Africa
-
- Watson, Bruce (författare)
- Stellenbosch University, South Africa
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin/Heidelberg, 2013
- 2013
- Engelska.
-
Ingår i: Developments in Language Theory. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642387708 - 9783642387715 ; , s. 70-81
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Most software packages with regular expression matching engines offer operators that extend the classical regular expressions, such as counting, intersection, complementation, and interleaving. Some of the most popular engines, for example those of Java and Perl, also provide operators that are intended to control the nondeterminism inherent in regular expressions. We formalize this notion in the form of the cut and iterated cut operators. They do not extend the class of languages that can be defined beyond the regular, but they allow for exponentially more succinct representation of some languages. Membership testing remains polynomial, but emptiness testing becomes PSPACE-hard.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- regular expression
- finite automaton
- cut operator
- Computer Science
- datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas