References

  1. Cyril Allauzen, Mehryar Mohri & Ashish Rastogi (2008): General Algorithms for Testing the Ambiguity of Finite Automata.. In: Masami Ito & Masafumi Toyama: Developments in Language Theory, Lecture Notes in Computer Science 5257. Springer, pp. 108–120, doi:10.1007/978-3-540-85780-8_8.
  2. Robert S. Boyer & J. Strother Moore (1977): A fast string searching algorithm. Communications of the ACM 20(10), pp. 762–772, doi:10.1145/359842.359859.
  3. Cezar Câmpeanu, Kai Salomaa & Sheng Yu (2003): A Formal Study of Practical Regular Expressions. International Journal of Foundations of Computer Science 14(6), pp. 1007–1018, doi:10.1142/S012905410300214X.
  4. Frank Drewes (2001): The Complexity of the Exponential Output Size Problem for Top-Down and Bottom-Up Tree Transducers,. Information and Computation 169(2), pp. 264 – 283, doi:10.1006/inco.2001.3039.
  5. Bryan Ford (2004): Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. In: Neil D. Jones & Xavier Leroy: Symposium on Principles of Programming Languages (POPL'04). ACM Press, pp. 111–122, doi:10.1145/964001.964011.
  6. Michael R. Garey & David S. Johnson (1979): Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
  7. James Kirrage, Asiri Rathnayake & Hayo Thielecke (2013): Static Analysis for Regular Expression Denial-of-Service Attacks. In: Network and System Security. Springer, pp. 135–148, doi:10.1007/978-3-642-38631-2_11.
  8. Sérgio Medeiros, Fabio Mascarenhas & Roberto Ierusalimschy (2012): From Regexes to Parsing Expression Grammars. CoRR abs/1210.4992, doi:10.1016/j.scico.2012.11.006.
  9. Ken Thompson (1968): Regular Expression Search Algorithm.. Communications of the ACM 11(6), pp. 419–422, doi:10.1145/363347.363387.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org