Regular expressions (automata; parsing; axiomatization; operational interpretation)

Books and Proceedings

1. J.E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2006.
2. Dexter Kozen. Automata and computability. Springer Verlag, 1997.
3. Jeffrey Friedl. Mastering Regular Expressions-Powerful Techniques for Perl and Other Tools. O'Reilly, 1997.
4. J. Hopcroft, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
5. J. H. Conway. Regular Algebra and Finite Machines. Printed in GB by William Clowes & Sons Ltd, 1971.

Academic Journals

1. S. Owens, J. Reppy, A. Turon. Regular-expression derivatives re-examined. Journal of Functional Programming, 19(2):173-190, 2009.
2. Marco Almeida, Nelma Moreira, Rogério Reis. Testing the Equivalence of Regular Languages. CoRR, abs/0907.5058, 2009. download
3. Philip Bille, Martin Farach-Colton. Fast and compact regular expression matching. Theor. Comput. Sci, 409(3):486-496, 2008.
4. Jos C. M. Baeten, Flavio Corradini, Clemens Grabmayer. A characterization of regular expressions under bisimulation. J. ACM, 54(2), 2007. download
5. Stijn Vansummeren. Type inference for unique pattern matching. ACM Trans. Program. Lang. Syst, 28(3):389-428, 2006. download
6. B.C. Brodie, D.E. Taylor, R.K. Cytron. A scalable architecture for high-throughput regular-expression pattern matching. ACM SIGARCH Computer Architecture News, 34(2), 2006.
7. M. Douglas McIlroy. Enumerating the strings of regular languages. J. Funct. Program, 14(5):503-518, 2004.
8. Hubie Chen, Riccardo Pucella. A coalgebraic approach to Kleene algebra with tests. Theor. Comput. Sci, 327(1):23-44, 2004.
9. J.-M. Champarnaud, F. Coulon. NFA reduction algorithms by means of regular inequalities. Theor. Comput. Sci, 327(3):241-253, 2004.
10. Naoshi Tabuchi, Eijiro Sumii, Akinori Yonezawa. Regular Expression Types for Strings in a Text Processing Language. Electronic Notes in Theoretical Computer Science, TIP'02, International Workshop in Types in Programming, 75:95-113, 2003.
11. D. Kozen, J. Tiuryn. Substructural logic and partial correctness. ACM Transactions on Computational Logic (TOCL), 4(3):355-378, 2003.
12. Haruo Hosoya, Benjamin C. Pierce. XDuce: A statically typed XML processing language. ACM Trans. Internet Technol, 3(2):117-148, 2003. download
13. Dan R. Ghica, Guy McCusker. The regular-language semantics of second-order idealized A$_LGOL$. Theor. Comput. Sci, 309(1):469-502, 2003.
14. D. Kozen. On the complexity of reasoning in Kleene algebra. Information and Computation, 179(2):152-162, 2002.
15. D. Calvanese, G. De Giacomo, M. Lenzerini, M.Y. Vardi. Rewriting of regular expressions and regular path queries. Journal of Computer and System Sciences, 64(3):443-465, 2002.
16. A. Gattiker, E. Gasteiger, A. Bairoch. ScanProsite: A Reference Implementation of a PROSITE Scanning Tool. Applied Bioinformatics, 1(2):107-108, 2002.
17. J.M. Champarnaud, D. Ziadi. Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions. Theoretical Computer Science, 289(1):137-163, 2002.
18. J. Engelfriet, H.J. Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001.
19. Lunjin Lu. On Dart-Zobel Algorithm for testing regular type inclusion. SIGPLAN Not, 36(9):81-85, 2001. download
20. P. Caron, D. Ziadi. Characterization of Glushkov automata. Theoretical Computer Science, 233(1):75-90, 2000.
21. C. Hagenah, A. Muscholl. Computing $\epsilon$-Free NFA from Regular Expressions in $O(n \log^2(n))$ Time. R.A.I.R.O. Theoretical Informatics and Applications, 34:257-277, 2000.
22. Danny Dubé, Marc Feeley. Efficiently building a parse tree from a regular expression. Acta Informatica, 37(2):121-144, 2000.
23. N. Klarlund, M.I. Schwartzbach. A domain-specific language for regular sets of strings and trees. Software Engineering, IEEE Transactions on, 25(3):378-386, 1999.
24. Robert Harper. Proof-directed debugging. Journal of Functional Programming, 9(4):463-469, 1999. download
25. A. Brüggemann-Klein, D. Wood. One-Unambiguous Regular Languages. Information and computation, 140(2):229-253, 1998.
26. Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir. On a question of A. Salomaa: The equational theory of regular expressions over a singleton alphabet is not finitely based. Theoretical Computer Science, 209(1):163-178, 1998.
27. Thomas Reps. "Maximal-munch" Tokenization in Linear Time. ACM Trans. Program. Lang. Syst, 20(2):259-273, 1998. download
28. Lunjin Lu, John G. Cleary. On Dart-Zobel Algorithm for Testing Regular Type Inclusion. CoRR, cs.LO/9810001, 1998. download
29. Chia-Hsiang Chang, Robert Paige. From Regular Expressions to DFA's Using Compressed NFA's. Theoretical Computer Science (TCS), 178:1-36, 1997.
30. Valentin Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci, 155(2):291-319, 1996.
31. Valentin M. Antimirov, Peter D. Mosses. Rewriting Extended Regular Expressions. Theor. Comput. Sci, 143(1):51-72, 1995.
32. Dexter Kozen. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Information and Computation, 110(2):366-390, May 1994.
33. Anne Brüggemann-Klein. Regular Expressions into Finite Automata. Theor. Comput. Sci, 120(2):197-213, 1993.
34. Gene Myers. A Four Russians Algorithm for Regular Expression Pattern Matching. J. ACM, 39(2):432-448, 1992. download
35. P. Hudak, J. H. Fasel. A gentle introduction to Haskell. Sigplan, 27(5), May 1992.
36. S.M. Kearns. Extending regular expressions with context operators and parse extraction. Software - Practice and Experience, 21(8):787-804, 1991.
37. Gerard Berry, Ravi Sethi. From regular expressions to deterministic automata. Theoretical Computer Science, 48:117-126, 1986.
38. Harry B. Hunt III, Daniel J. Rosenkrantz, Thomas G. Szymanski. On the equivalence, containment, and covering problems for the regular and context-free languages. Journal of Computer and System Sciences, 12(2):222-268, 1976. download download
39. Ronald Book, Shimon Even, Sheila Greibach, Gene Ott. Ambiguity in Graphs and Expressions. IEEE Transactions on Computers, 20(2):149-153, 1971.
40. Ken Thompson. Programming Techniques: Regular expression search algorithm. Commun. ACM, 11(6):419-422, 1968. download
41. A. Ginzburg. A Procedure for Checking Equality of Regular Expressions. J. ACM, 14(2):355-362, 1967. download
42. B.G. Mirkin. An Algorithm for Constructing a Base in a Language of Regular Expressions. Engineering Cybernetics, According to Champernaud et al. (2002) this is contains the same construction as Antimirov's construction (1996), 5:110-116, 1966.
43. Arto Salomaa. Two Complete Axiom Systems for the Algebra of Regular Events. J. ACM, 13(1):158-169, 1966. download
44. Peter Johansen. Construction of recognition devices for regular languages from their Backus Normal Form definition. BIT Numerical Mathematics, 6(4):294-309, July 1966.
45. Stal Aanderaa. On the Algebra of Regular Expressions. Appl. Math, Harvard U, pages 1-18, January 1965.
46. R. McNaughton, H. Yamada. Regular Expressions and State Graphs for Automata. Sequential Machines: Selected Papers, 1964.
47. Janusz A. Brzozowski. Derivatives of Regular Expressions. J. ACM, 11(4):481-494, 1964. download
48. J.A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, 12:529-561, 1962.
49. J.A. Brzozowski. A Survey of Regular Expressions and their Applications. IEEE Transactions on Electronic Computers, 11:324-335, 1962.
50. VM Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16(5):1-53, 1961.
51. R. McNaughton, H. Yamada. Regular Expressions and Finite State Graphs for Automata. IRE Trans. on Electronic Comput, EC-9(1):38-47, 1960.
52. Noam Chomsky. On certain formal properties of grammars. Information and Control, 2(2):137-167, 1959.
53. D. Huffman. Canonical forms for information-lossless finite-state logical machines. Information Theory, IRE Transactions on, 5(5):41-59, 1959.
54. M.O. Rabin, D. Scott. Finite Automata and their Decision Problems. IBM Journal of Research and Development, 3(2):114-125, 1959.
55. A. Nerode. Linear automaton transformations. Proceedings of the American Mathematical Society, 9(4):541-544, 1958.
56. S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata. Automata Studies, 1956.
57. N. Chomsky. Three models for the description of language. Information Theory, IEEE Transactions on, 2(3):113-124, 1956.
58. Sebastian Fischer, Frank Huch, Thomas Wilke. A Play on Regular Expressions. ICFP, 0.
59. V. M. Glushkov. On a synthesis algorithm for abstract automata. Ukr. Matem. Zhurnal, 12(0):147-156, 0.

Book Chapters

1. Michael Sipser. Introduction to the Theory of Computation. ISBN-13: 978-0-619-21764-8, ISBN-10: 0-619-21764-2, ISBN-13: 978-0-619-21764-8, ISBN-10: 0-619-21764-2, Chap. 1, pp. 31-98, Course Technology CENGAGE Learning, 2006.
2. S. Yu. Regular Languages. In Handbook of Formal Languages, Rozenberg G, A. Salomaa (eds.), Vol. I (Words, Languages, Grammars), pp. 41-110, Springer-Verlag, 1997.
3. D. Kozen. On action algebras. In Logic and Information Flow, Jan van Eijck, Albert Visser (eds.), Chap. 5, pp. 78-88, Foundations of Computing, MIT Press, 1994.
4. P.W. Dart, J. Zobel. A Regular Type Language for Logic Programs. In Types in Logic Programming, F. Pfenning (ed.), MIT Press, 1992.
5. Wolfgang Thomas. Automata on Infinite Objects. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 133-192, 1990.
6. Dominique Perrin. Finite Automata. In Handbook of Theoretical Computer Science, Vol. Formal Models and Sematics (B), Chap. 1, pp. 1-57, 1990.
7. Alfred V. Aho. Algorithms for Finding Patterns in Strings. In Handbook of Theoretical Computer Science, ISBN 0-444-88071-2 and 0-262-22038-5, Jan van Leeuwen (ed.), ISBN 0-444-88071-2 and 0-262-22038-5, Vol. Algorithms and Complexity (A), pp. 255-300, Elsevier and MIT Press, 1990.
8. John Hopcroft. An $n \log n$ Algorithm for Minimizing States in a Finite Automaton. In Theory of Machines and Computations, Z. Kohavi, A. Paz (eds.), pp. 189-196, Academic Press, New York, 1971.
9. Cyril Allauzen, Mehryar Mohri. A Unified Construction of the Glushkov, Follow, and Antimirov Automata. In Mathematical Foundations of Computer Science 2006, 10.1007/11821069_10, Rastislav Kr\'alovic, Pawel Urzyczyn (eds.), 10.1007/11821069_10, Vol. 4162, Chap. 0, pp. 110-121, Springer Berlin / Heidelberg, 0.

International Conferences

1. Vladimir Komendantsky. Reflexive Toolbox for Regular Expression Matching. In Proc. 6th ACM SIGPLAN Workshop Programming Languages meets Program Verification (PLPV), Philadelphia, PA, USA, January 2012.
2. Thierry Coquand, Vincent Siles. A Decision Procedure for Regular Expression Equivalence in Type Theory. In Proc. 1st International Conference on Certified Programs and Proofs (CPP), 2011.
3. Lasse Nielsen, Fritz Henglein. Bit-coded Regular Expression Parsing. In Proc. 5th Int'l Conf. on Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science (LNCS), May 2011.
4. Fritz Henglein, Lasse Nielsen. Regular Expression Containment: Coinductive Axiomatization and Computational Interpretation. In Proc. 38th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), January 2011.
5. N. Li, T. Xie, N. Tillmann, J. de Halleux, W. Schulte. Reggae: Automated test generation for programs using complex regular expressions. In Automated Software Engineering, 2009. ASE'09. 24th IEEE/ACM International Conference on, Pages 515-519, 2010.
6. Philip Bille, Mikkel Thorup. Regular Expression Matching with Multi-Strings and Intervals. In Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
7. Claus Brabrand, Jakob Thomsen. Typed and Unambiguous Pattern Matching on Strings using Regular Expressions. In Proc. 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP), 2010.
8. Margus Veanes Margus Veanes, Peli de Halleux, Nikolai Tillmann. Rex: Symbolic Regular Expression Explorer. In Proc. 3d Int'l Conf. on Software Testing, Verification and Validation, Paris, France, 2010.
9. P. Hooimeijer, W. Weimer. A decision procedure for subset constraints over regular languages. In ACM SIGPLAN Notices, Volume 44, Pages 188-198, 2009.
10. F. Bonchi, M. Bonsangue, J. Rutten, A. Silva. Deriving syntax and axioms for quantitative regular behaviours. In Proc. CONCUR 2009-Concurrency Theory, Lecture Notes in Computer Science (LNCS), Volume 5710, Pages 146-162, 2009.
11. M. Bonsangue, J. Rutten, A. Silva. An algebra for Kripke polynomial coalgebras. In Proceedings of the 2009 24th Annual IEEE Symposium on Logic In Computer Science-Volume 00, Pages 49-58, 2009.
12. Marcello M. Bonsangue, Jan J. M. M. Rutten, Alexandra Silva. A Kleene Theorem for Polynomial Coalgebras. In FOSSACS, Pages 122-136, 2009.
13. Philip Bille. Fast Searching in Packed Strings. In CPM, Pages 116-126, 2009.
14. Philip Bille, Mikkel Thorup. Faster Regular Expression Matching. In ICALP (1), Pages 171-182, 2009.
15. F. Yu, Z. Chen, Y. Diao, TV Lakshman, R.H. Katz. Fast and memory-efficient regular expression matching for deep packet inspection. In Architecture for Networking and Communications systems, 2006. ANCS 2006. ACM/IEEE Symposium on, Pages 93-102, 2008.
16. J. Worthington. Automatic proof generation in Kleene algebra. In Proceedings of the 10th international conference on Relational and kleene algebra methods in computer science, and 5th international conference on Applications of kleene algebra, Lecture Notes in Computer Science (LNCS), Volume 4988, Pages 382-396, 2008.
17. Alain Frisch. OCaml + XDuce. In ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, Pages 192-200, New York, NY, USA, 2006. download
18. Philip Bille. New Algorithms for Regular Expression Matching. In ICALP (1), Pages 643-654, 2006.
19. Danny Dubé, Anass Kadiri. Automatic construction of parse trees for lexemes. In Proc. of Workshop on Scheme and Functional Programming, 2006. download
20. D. Kirsten. Distance desert automata and the star height problem. In Theoretical Informatics and Applications, Volume 39, Pages 455-509, 2005.
21. Burak Emir. Compiling regular patterns to sequential machines. In SAC, Pages 1385-1389, 2005.
22. J. C. M. Baeten, F. Corradini. Regular Expressions in Process Algebra. In LICS '05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, Pages 12-19, Washington, DC, USA, 2005.
23. Clemens Grabmayer. Using Proofs by Coinduction to Find ``Traditional'' Proofs. In Proc. 1st Conference on Algebra and Coalgebra in Computer Science (CALCO), Lecture Notes in Computer Science (LNCS), September 2005.
24. Guangming Xing. A simple way to construct NFA with fewer states and transitions. In ACM-SE 42: Proceedings of the 42nd annual Southeast regional conference, Pages 214-218, New York, NY, USA, 2004. download
25. Niklas Broberg, Andreas Farre, Josef Svenningsson. Regular expression patterns. In ICFP, Pages 67-78, 2004.
26. Kenny Zhuo Ming Lu, Martin Sulzmann. An Implementation of Subtyping Among Regular Expression Types. In Proc. Second Asian Symposium, APLAS 2004, Taipei, Taiwan, November 4-6, 2004, Lecture Notes in Computer Science (LNCS), Volume 3302, Pages 57-73, November 2004.
27. A. Frisch, L. Cardelli. Greedy Regular Expression Matching. In Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP), Lecture notes in computer science, Volume 3142, Pages 618-629, Turku, Finland, July 2004.
28. M.Y. Levin. Compiling regular patterns. In Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, Pages 65-77, 2003.
29. M. Levin, B. Pierce. Type-based optimization for regular patterns. In Database Programming Languages, Pages 184-198, 2003.
30. L. van Zijl. Succinct Descriptions of regular languages with binary ⊕-NFAs. In Proc. 8th International Conference on Implementation and Application of Automata, Lecture Notes in Computer Science (LNCS), Volume 2759, Pages 281-305, 2003.
31. Véronique Benzaken, Giuseppe Castagna, Alain Frisch. CDuce: An XML-Centric General-Purpose Language. In Proc. 8th ACM SIGPLAN Int'l Conf. on Functional Programming (ICFP), Pages 51-63, New York, NY, USA, 2003. download
32. Aske Simon Christensen, Anders M\oller, Michael I. Schwartzbach. Precise Analysis of String Expressions. In SAS, Pages 1-18, 2003.
33. Gonzalo Navarro, Mathieu Raffinot. Fast and simple character classes and bounded gaps pattern matching, with application to protein searching. In RECOMB '01: Proceedings of the fifth annual international conference on Computational biology, Pages 231-240, New York, NY, USA, 2001. download
34. Frank Neven, Thomas Schwentick, Victor Vianu. Towards Regular Languages over Infinite Alphabets. In MFCS, Pages 560-572, 2001.
35. George C. Necula, Shree Prakash Rahul. Oracle-based checking of untrusted software. In POPL, Pages 142-154, 2001. download
36. Ville Laurikari. NFAs with Tagged Transitions, Their Conversion to Deterministic Automata and Application to Regular Expressions. In SPIRE, Pages 181-187, 2000.
37. J. Polakow, F. Pfenning. Natural deduction for intuitionistic non-commutative linear logic. In Typed Lambda Calculi and Applications, Pages 644-644, 1999.
38. Jesper G. Henriksen, Jakob L. Jensen, Michael E. J\orgensen, Nils Klarlund, Robert Paige, Theis Rauhe, Anders Sandholm. Mona: Monadic Second-Order Logic in Practice. In Tools and Algorithms for the Construction and Analysis of Systems, Ed Brinksma, Rance Cleaveland, Kim Guldstrand Larsen, Tiziana Margaria, Bernhard Steffen (eds.), Volume 1019, Pages 89-110, 1995.
39. Valentin Antimirov. Rewriting regular inequalities. In Proc. 10th International Conference, FCT '95 Dresden, Germany, Lecture Notes in Computer Science (LNCS), Volume 965, Pages 116-125, August 1995.
40. David Sands. Total Correctness by Local Improvement in Program Transformation. In Proc. 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Pages 221-232, January 1995.
41. O. Christ. A modular and flexible architecture for an integrated corpus query system. In Proc. 3d Conference on Computational Lexicography and Text Research (COMPLEX), Arxiv preprint cmp-lg/9408005, Pages 23-32, July 1994.
42. Valentin M. Antimirov, Peter D. Mosses. Rewriting Extended Regular Expressions. In Developments in Language Theory, Pages 195-209, 1993.
43. Anne Brüggemann-Klein. Regular Expressions into Finite Automata. In LATIN, Pages 87-98, 1992.
44. Daniel Krob. A Complete System of B-Rational Identities. In ICALP, Pages 60-73, 1990.
45. L. J. Stockmeyer, A. R. Meyer. Word problems requiring exponential time (Preliminary Report). In Proceedings of the fifth annual ACM symposium on Theory of computing, Pages 1-9, 1973.
46. Peter Johansen. Free groups and regular expressions. In STOC '69: Proceedings of the first annual ACM symposium on Theory of computing, Pages 113-128, New York, NY, USA, 1969. download

Technical Reports

1. AM Silva, MM Bonsangue, J. Rutten. Kleene Coalgebras. Software Engineering [SEN] Centrum Wiskunde en Informatica (CWI), No 1001, 2010.
2. Hermann Gruber, Stefan Gulan. Simplifying Regular Expressions. A Quantitative Perspective. IFIG Research Report Justus-Liebig-Universität Giessen, No 904, August 2009.
3. Daan Leijen. Parsec, a fast combinator parser. CS-2001 Department of Computer Science, University of Utrecht (RUU), No 35, October 2001.
4. S. Thompson. Regular expressions and automata using Haskell. Research Report University of Kent at Canterbury Computing Laboratory, 2000.
5. J. Hopcroft, R. Karp. A Linear Algorithm for Testing Equivalence of Finite Automata. Research Report Dept. of Computer Science, Cornell U, No 0, December 1971.

Miscellaneous

1. Russ Cox. Regular Expression Matching in the Wild. March 2010.
2. Philip Hazel. PCRE - Perl-compatible regular expressions. Concatenation of PCRE man pages, 2010. download download
3. Russ Cox. Regular Expression Matching: the Virtual Machine Approach. December 2009.
4. Anders Möller. \textttdk.brics.automaton: Finite-State Automata and Regular Expressions for Java. \texttthttp://www.brics.dk/automaton/, 2008.
5. Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, .). January 2007.
6. The IEEE, The Open Group. The Open Group Base Specifications, Issue 6, IEEE Std 1003.1. The Open Group Base Specifications, Issue 6, IEEE Std 1003.1, 2004. download
7. R. Backhouse, D. Kozen, B. Möller. Applications of Kleene Algebra. Dagstuhl Seminar, February 2001. download

Dissertations

1. Philip Bille. Pattern Matching in Trees and Strings. PhD Thesis IT University of Copenhagen, June 2007. download
2. D. Kirsten. Distance desert automata and star height substitutions. PhD Thesis Fakultät Mathematik und Informatik der Universität Leipzig, 2006.
3. Haruo Hosoya. Regular Expression Types for XML. PhD Thesis The University of Tokyo, December 2000.
4. B.W. Watson. Taxonomies and toolkits of regular language algorithms. PhD Thesis TU Eindhoven, September 1995.
5. Chia-Hsiang Chang. From Regular Expressions to DFA's Using Compressed NFA's. PhD Thesis Computer Science Department, Courant Institute of Mathematical Sciences, New York University, October 1992.
6. Steven M. Kearns. Extending Regular Expressions. PhD Thesis Columbia University, 1990.
7. P. Johansen. An Algebraic Normal Form for Regular Events. PhD Thesis DIKU, University of Copenhagen, January 1973.

Master's thesis

1. V. Laurikari. Efficient submatch addressing for regular expressions. Master's theses Helsinki University of Technology, 2001.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.