116 @incollection{AHO1990255,

   117 @article{FERNAU2015287,

   117 title = {CHAPTER 5 - Algorithms for Finding Patterns in Strings},

   118 title = {Pattern matching with variables: A multivariate complexity analysis},

   118 editor = {JAN {VAN LEEUWEN}},

   119 journal = {Information and Computation},

   119 booktitle = {Algorithms and Complexity},

   120 volume = {242},

   120 publisher = {Elsevier},

   121 pages = {287-305},

   121 address = {Amsterdam},

   122 year = {2015},

   122 pages = {255-300},

   123 issn = {0890-5401},

   123 year = {1990},

   124 doi = {https://doi.org/10.1016/j.ic.2015.03.006},

   124 series = {Handbook of Theoretical Computer Science},

   125 url = {https://www.sciencedirect.com/science/article/pii/S0890540115000218},

   125 isbn = {978-0-444-88071-0},

   126 author = {H.~Fernau and M.L.~Schmid},

   126 doi = {https://doi.org/10.1016/B978-0-444-88071-0.50010-2},

   127 keywords = {Parameterised pattern matching, Function matching, NP-completeness, Membership problem for pattern languages, Morphisms},

   127 url = {https://www.sciencedirect.com/science/article/pii/B9780444880710500102},

   128 abstract = {A pattern α, i.e., a string that contains variables and terminals, matches a terminal word w if w can be obtained by uniformly substituting the variables of α by terminal words. Deciding whether a given terminal word matches a given pattern is NP-complete and this holds for several natural variants of the problem that result from whether or not variables can be erased, whether or not the patterns are required to be terminal-free or whether or not the mapping of variables to terminal words must be injective. We consider numerous parameters of this problem (i.e., number of variables, length of w, length of the words substituted for variables, number of occurrences per variable, cardinality of the terminal alphabet) and for all possible combinations of the parameters (and variants described above), we answer the question whether or not the problem is still NP-complete if these parameters are bounded by constants.}

   128 author = {Alfred V. AHO},

   129 }

   129 abstract = {Publisher Summary

   130 

   130 This chapter discusses the algorithms for solving string-matching problems that have proven useful for text-editing and text-processing applications. String pattern matching is an important problem that occurs in many areas of science and information processing. In computing, it occurs naturally as part of data processing, text editing, term rewriting, lexical analysis, and information retrieval. Many text editors and programming languages have facilities for matching strings. In biology, string-matching problems arise in the analysis of nucleic acids and protein sequences, and in the investigation of molecular phylogeny. String matching is also one of the central and most widely studied problems in theoretical computer science. The simplest form of the problem is to locate an occurrence of a keyword as a substring in a sequence of characters, which is called the input string. For example, the input string queueing contains the keyword ueuei as a substring. Even for this problem, several innovative, theoretically interesting algorithms have been devised that run significantly faster than the obvious brute-force method.}

   131 @inproceedings{Schmid2012,

   131 }

   132 author = {M.L.~Schmid},

   133 title = {Inside the Class of REGEX Languages},

   134 year = {2012},

   135 isbn = {9783642316524},

   136 publisher = {Springer-Verlag},

   137 address = {Berlin, Heidelberg},

   138 url = {https://doi.org/10.1007/978-3-642-31653-1_8},

   139 doi = {10.1007/978-3-642-31653-1_8},

   140 abstract = {We study different possibilities of combining the concept of homomorphic replacement with regular expressions in order to investigate the class of languages given by extended regular expressions with backreferences (REGEX). It is shown in which regard existing and natural ways to do this fail to reach the expressive power of REGEX. Furthermore, the complexity of the membership problem for REGEX with a bounded number of backreferences is considered.},

   141 booktitle = {Proceedings of the 16th International Conference on Developments in Language Theory},

   142 pages = {73–84},

   143 numpages = {12},

   144 keywords = {extended regular expressions, pattern languages, REGEX, pattern expressions, homomorphic replacement},

   145 location = {Taipei, Taiwan},

   146 series = {DLT'12}

   147 }

   148 

   149 

   150 

   151 @article{BERGLUND2022,

   152 title = {Re-examining regular expressions with backreferences},

   153 journal = {Theoretical Computer Science},

   154 year = {2022},

   155 issn = {0304-3975},

   156 doi = {https://doi.org/10.1016/j.tcs.2022.10.041},

   157 url = {https://www.sciencedirect.com/science/article/pii/S0304397522006570},

   158 author = {Martin Berglund and Brink {van der Merwe}},

   159 keywords = {Regular expressions, Backreferences},

   160 abstract = {Most modern regular expression matching libraries (one of the rare exceptions being Google's RE2) allow backreferences, operations which bind a substring to a variable, allowing it to be matched again verbatim. However, both real-world implementations and definitions in the literature use different syntactic restrictions and have differences in the semantics of the matching of backreferences. Our aim is to compare these various flavors by considering the classes of formal languages that each can describe, establishing, as a result, a hierarchy of language classes. Beyond the hierarchy itself, some complexity results are given, and as part of the effort on comparing language classes new pumping lemmas are established, old classes are extended to new ones, and several incidental results on the nature of these language classes are given.}

   161 }

   162 

   163 @article{FREYDENBERGER20191,

   164 title = {Deterministic regular expressions with back-references},

   165 journal = {Journal of Computer and System Sciences},

   166 volume = {105},

   167 pages = {1-39},

   168 year = {2019},

   169 issn = {0022-0000},

   170 doi = {https://doi.org/10.1016/j.jcss.2019.04.001},

   171 url = {https://www.sciencedirect.com/science/article/pii/S0022000018301818},

   172 author = {Dominik D. Freydenberger and Markus L. Schmid},

   173 keywords = {Deterministic regular expression, Regex, Glushkov automaton},

   174 abstract = {Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between expressiveness and tractability, we combine these with the notion of determinism for regular expressions used in XML DTDs and XML Schema. This includes the definition of a suitable automaton model, and a generalization of the Glushkov construction. We demonstrate that, compared to their non-deterministic superclass, these deterministic regular expressions with back-references have desirable algorithmic properties (i.e., efficiently solvable membership problem and some decidable problems in static analysis), while, at the same time, their expressive power exceeds that of deterministic regular expressions without back-references.}

   175 }

   176 @InProceedings{Frey2013,

   177   author =	{Dominik D. Freydenberger},

   178   title =	{{Extended Regular Expressions: Succinctness and Decidability}},

   179   booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },

   180   pages =	{507--518},

   181   series =	{Leibniz International Proceedings in Informatics (LIPIcs)},

   182   ISBN =	{978-3-939897-25-5},

   183   ISSN =	{1868-8969},

   184   year =	{2011},

   185   volume =	{9},

   186   editor =	{Thomas Schwentick and Christoph D{\"u}rr},

   187   publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},

   188   address =	{Dagstuhl, Germany},

   189   URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3039},

   190   URN =		{urn:nbn:de:0030-drops-30396},

   191   doi =		{10.4230/LIPIcs.STACS.2011.507},

   192   annote =	{Keywords: extended regular expressions, regex, decidability, non-recursive tradeoffs}

   193 }

   194 

   195 

   196 

   197 %% -------------------------- campeanu related

   198 @article{campeanu2003formal,

   199 	author = {C.~C{\^a}mpeanu and K.~Salomaa and S.~Yu},

   200 	journal = {International Journal of Foundations of Computer Science},

   201 	number = {06},

   202 	pages = {1007--1018},

   203 	publisher = {World Scientific},

   204 	title = {A formal study of practical regular expressions},

   205 	volume = {14},

   206 	year = {2003}}

   207 

   208 @article{campeanu2009patterns,

   209 author = {C.~C{\^a}mpeanu and N.~Santean},

   210 year = {2009},

   211 month = {05},

   212 pages = {193-207},

   213 title = {On the closure of pattern expressions languages under intersection with regular languages},

   214 volume = {46},

   215 journal = {Acta Inf.},

   216 doi = {10.1007/s00236-009-0090-y}

   217 }

   218 

   219 @article{CAMPEANU2009Intersect,

   220 	abstract = {In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255--300] and rigorously in 2003 by C{\^a}mpeanu, Salomaa and Yu [C. C{\^a}mpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007--1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines --- regex automata systems (RAS) --- which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.},

   221 	author = {Cezar C{\^a}mpeanu and Nicolae Santean},

   222 	doi = {https://doi.org/10.1016/j.tcs.2009.02.022},

   223 	issn = {0304-3975},

   224 	journal = {Theoretical Computer Science},

   225 	keywords = {Extended regular expression, Regex automata system, Regex},

   226 	note = {Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu},

   227 	number = {24},

   228 	pages = {2336-2344},

   229 	title = {On the intersection of regex languages with regular languages},

   230 	url = {https://www.sciencedirect.com/science/article/pii/S0304397509001789},

   231 	volume = {410},

   232 	year = {2009},

   233 	bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397509001789},

   234 	bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2009.02.022}}

   298 @article{CAMPEANU2009Intersect,

   393 	

   299 	abstract = {In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255--300] and rigorously in 2003 by C{\^a}mpeanu, Salomaa and Yu [C. C{\^a}mpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007--1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines --- regex automata systems (RAS) --- which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.},

   300 	author = {Cezar C{\^a}mpeanu and Nicolae Santean},

   301 	doi = {https://doi.org/10.1016/j.tcs.2009.02.022},

   302 	issn = {0304-3975},

   303 	journal = {Theoretical Computer Science},

   304 	keywords = {Extended regular expression, Regex automata system, Regex},

   305 	note = {Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu},

   306 	number = {24},

   307 	pages = {2336-2344},

   308 	title = {On the intersection of regex languages with regular languages},

   309 	url = {https://www.sciencedirect.com/science/article/pii/S0304397509001789},

   310 	volume = {410},

   311 	year = {2009},

   312 	bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397509001789},

   313 	bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2009.02.022}}

   314