Translating regular expression matching into transducers

Berstel, 1979 C. Brabrand, J.G. Thomsen, Typed and unambiguous pattern matching on strings using regular expressions, in: Proceedings of 12th ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP), 2010, pp. 243–254. Cox Cox Cox Engelfriet, 1977, Top-down tree transducers with regular look-ahead, Mathematical Systems Theory, 10, 289, 10.1007/BF01683280 S. Fischer, F. Huch, T. Wilke, A play on regular expressions, in: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, 2010, pp. 357–368. Friedl, 2006 Frisch, 2004, Greedy regular expression matching, vol. 3142, 618 Grabmayer, 2005, Using proofs by coinduction to find “traditional” proofs, vol. 3629, 175 F. Henglein, L. Nielsen, Regular expression containment: Coinductive axiomatization and computational interpretation, in: Conference Record of POPL 2011: 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2011, pp. 385–398. Kozen, 1997, Kleene algebra with tests, Information and Computation, 19, 427 V. Laurikari, Nfas with tagged transitions, their conversion to deterministic automata and application to regular expressions, in: Proceedings of the 7th International Symposium on String Processing and Information Retrieval, IEEE, 2000, pp. 181–187. S. Liang, P. Hudak, M.P. Jones, Monad transformers and modular interpreters, in: Conference Record of POPLʼ95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1995, pp. 333–343. Mealy, 1955, A method for synthesizing sequential circuits, Bell System Technical Journal, 34, 1045, 10.1002/j.1538-7305.1955.tb03788.x Minamide, 2005, Static approximation of dynamically generated Web pages, 432 Y. Minamide, Y. Sakuma, A. Voronkov, Translating regular expression matching into transducers, in: Proceedings of International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2010), 2011, pp. 107–115. E. Moggi, Computational lambda-calculus and monads, in: Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS), 1989, pp. 14–23. E. Moggi, An abstract view of programming languages, Course Notes, 1989. Mohri, 2000, Minimization algorithms for sequential transducers, Theoretical Comput. Sci., 234, 177, 10.1016/S0304-3975(98)00115-7 Sakarovitch, 2009 Salomma, 1966, Two complete axiom systems for the algebra of regular events, J. ACM, 13, 148 Thompson, 1968, Regular expression search algorithm, Communications of the ACM, 11, 419, 10.1145/363347.363387 Vansummeren, 2006, Type inference for unique pattern matching, ACM Transactions on Programming Languages and Systems, 28, 389, 10.1145/1133651.1133652 P. Wadler, The essence of functional programming, in: Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1992, pp. 1–14. Wadler, 1992, Comprehending monads, Mathematical Structures in Computer Science, 2, 461, 10.1017/S0960129500001560 G. Wassermann, D. Yu, et al. Dynamic test input generation for web applications, in: Proceedings of the 2008 International Symposium on Software Testing and Analysis, 2008, pp. 249–260. H. Xi, Dependent types for program termination verification, in: Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001, pp. 231–242.