Cuts in Regular Expressions
2013 (English)In: Developments in Language Theory: 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings / [ed] Marie-Pierre Béal, Olivier Carton, Springer Berlin/Heidelberg, 2013, 70-81 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. 70-81 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 7907
regular expression, finite automaton, cut operator
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-67738DOI: 10.1007/978-3-642-38771-5_8ISBN: 978-3-642-38770-8 (Print)ISBN: 978-3-642-38771-5 (Online)OAI: oai:DiVA.org:umu-67738DiVA: diva2:613536
17th International Conference on Developments in Language Theory, DLT 2013, 18 June 2013 through 21 June 2013, Marne-la-Vallee