{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:14:16Z","timestamp":1771697656126,"version":"3.50.1"},"reference-count":91,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int. J. Autom. Comput."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Regular expressions are widely used within and even outside of computer science due to their expressiveness and flexibility. However, regular expressions have a quite compact and rather tolerant syntax that makes them hard to understand, hard to compose, and error-prone. Faulty regular expressions may cause failures of the applications that use them. Therefore, ensuring the correctness of regular expressions is a vital prerequisite for their use in practical applications. The importance and necessity of ensuring correct definitions of regular expressions have attracted extensive attention from researchers and practitioners, especially in recent years. In this study, we provide a review of the recent works for ensuring the correct usage of regular expressions. We classify those works into different categories, including the empirical study, test string generation, automatic synthesis and learning, static checking and verification, visual representation and explanation, and repairing. For each category, we review the main results, compare different approaches, and discuss their advantages and disadvantages. We also discuss some potential future research directions.<\/jats:p>","DOI":"10.1007\/s11633-021-1301-4","type":"journal-article","created":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T15:02:50Z","timestamp":1622818970000},"page":"521-535","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Ensuring the Correctness of Regular Expressions: A Review"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9146-5465","authenticated-orcid":false,"given":"Li-Xiao","family":"Zheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4050-0443","authenticated-orcid":false,"given":"Shuai","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zu-Xi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiang-Yu","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"key":"1301_CR1","volume-title":"Compilers: Principles, Techniques, & Tools","author":"A V Aho","year":"2007","unstructured":"A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman. Compilers: Principles, Techniques, & Tools, 2nd ed., Harlow, UK: Pearson Addison Wesley, 2007.","edition":"2nd ed."},{"key":"1301_CR2","unstructured":"G. Wondracek, P. M. Comparetti, C. Kr\u00fcgel, E. Kirda. Automatic network protocol analysis. In Proceedings of the Network and Distributed System Security Symposium, San Diego, USA, pp. 1\u201314, 2008."},{"key":"1301_CR3","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1145\/1980022.1980229","volume-title":"Analysis of different technique for detection of SQL injection","author":"A S Yeole","year":"2011","unstructured":"A. S. Yeole, B. B. Meshram. Analysis of different technique for detection of SQL injection. In Proceedings of International Conference & Workshop on Emerging Trends in Technology, ACM, Mumbai, India, pp. 963\u2013966, 2011. DOI: https:\/\/doi.org\/10.1145\/1980022.1980229."},{"key":"1301_CR4","unstructured":"Vern Paxson. The Bro network security monitor, [Online], Available: http:\/\/www.bro.org, 2015."},{"issue":"4","key":"1301_CR5","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1145\/1111627.1111631","volume":"5","author":"M Murata","year":"2005","unstructured":"M. Murata, D. Lee, M. Mani, K. Kawaguchi. Taxonomy of XML schema languages using formal language theory. ACM Transactions on Internet Technology, vol. 5, no. 4, pp. 660\u2013704, 2005. DOI: https:\/\/doi.org\/10.1145\/1111627.1111631.","journal-title":"ACM Transactions on Internet Technology"},{"issue":"2","key":"1301_CR6","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.websem.2009.02.002","volume":"7","author":"F Alkhateeb","year":"2009","unstructured":"F. Alkhateeb, J. F. Baget, J. Euzenat. Extending SPARQL with regular expression patterns (for querying RDF). Journal of Web Semantics, vol. 7, no. 2, pp. 57\u201373, 2009. DOI: https:\/\/doi.org\/10.1016\/j.websem.2009.02.002.","journal-title":"Journal of Web Semantics"},{"key":"1301_CR7","doi-asserted-by":"publisher","DOI":"10.1109\/CIBCB.2005.1594922","volume-title":"Multiple sequence alignment containing a sequence of regular expressions","author":"A N Arslan","year":"2005","unstructured":"A. N. Arslan. Multiple sequence alignment containing a sequence of regular expressions. In Proceedings of IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, IEEE, La Jolla, USA, 2005. DOI: https:\/\/doi.org\/10.1109\/CIBCB.2005.1594922."},{"key":"1301_CR8","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1145\/2931037.2931073","volume-title":"Exploring regular expression usage and context in Python","author":"C Chapman","year":"2016","unstructured":"C. Chapman, K. T. Stolee. Exploring regular expression usage and context in Python. In Proceedings of the 25th International Symposium on Software Testing and Analysis, ACM, Saarbr\u00fccken, Germany, pp. 282\u2013293, 2016. DOI: https:\/\/doi.org\/10.1145\/2931037.2931073."},{"key":"1301_CR9","doi-asserted-by":"publisher","unstructured":"J. C. Davis, C. A. Coghlan, F. Servant, D. Lee. The impact of regular expression denial of service (ReDoS) in practice: An empirical study at the ecosystem scale. In Proceedings of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Lake Buena Vista, USA, pp. 246\u2013256, 2018. DOI: https:\/\/doi.org\/10.1145\/3236024.3236027.","DOI":"10.1145\/3236024.3236027"},{"key":"1301_CR10","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2318202.2318207","volume-title":"A type system for regular expressions","author":"E Spishak","year":"2012","unstructured":"E. Spishak, W. Dietl, M. D. Ernst. A type system for regular expressions. In Proceedings of the 14th Workshop on Formal Techniques for Java-like Programs, ACM, Beijing, China, pp. 20\u201326, 2012. DOI: https:\/\/doi.org\/10.1145\/2318202.2318207."},{"key":"1301_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1109\/ICST.2016.29","volume-title":"Generating evil test strings for regular expressions","author":"E Larson","year":"2016","unstructured":"E. Larson, A. Kirk. Generating evil test strings for regular expressions. In Proceedings of IEEE International Conference on Software Testing, Verification and Validation, IEEE, Chicago, USA, pp. 309\u2013319, 2016. DOI: https:\/\/doi.org\/10.1109\/ICST.2016.29."},{"key":"1301_CR12","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-28872-2_27","volume-title":"Explanations for regular expressions","author":"M Erwig","year":"2012","unstructured":"M. Erwig, R. Gopinath. Explanations for regular expressions. In Proceedings of the 15th International Conference on Fundamental Approaches to Software Engineering, Springer, Tallinn, Estonia, pp. 394\u2013408, 2012. DOI: https:\/\/doi.org\/10.1007\/978-3-642-28872-2_27."},{"issue":"3","key":"1301_CR13","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/1072997.1073000","volume":"14","author":"P Klint","year":"2005","unstructured":"P. Klint, R. L\u00e4mmel, C. Verhoef. Toward an engineering discipline for grammarware. ACM Transactions on Software Engineering and Methodology, vol. 14, no. 3, pp. 331\u2013380, 2005. DOI: https:\/\/doi.org\/10.1145\/1072997.1073000.","journal-title":"ACM Transactions on Software Engineering and Methodology"},{"key":"1301_CR14","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/3236024.3236072","volume-title":"How well are regular expressions tested in the wild?","author":"P P Wang","year":"2018","unstructured":"P. P. Wang, K. T. Stolee. How well are regular expressions tested in the wild? In Proceedings of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ACM, Lake Buena Vista, USA, pp.668\u2013678, 2018. DOI: https:\/\/doi.org\/10.1145\/3236024.3236072."},{"key":"1301_CR15","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J E Hopcroft","year":"2001","unstructured":"J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd ed., Boston, USA: Addison-Wesley, 2001.","edition":"2nd ed."},{"key":"1301_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2010.04.036","volume":"411","author":"W Gelade","year":"2010","unstructured":"W. Gelade. Succinctness of regular expressions with interleaving, intersection and counting. Theoretical Computer Science, vol. 411, no. 31\u201333, pp. 2987\u20132998, 2010. DOI: https:\/\/doi.org\/10.1016\/j.tcs.2010.04.036.","journal-title":"Theoretical Computer Science"},{"key":"1301_CR17","unstructured":"H. S. Thompson, D. Beech, M. Maloney, N. Mendelsohn. XML schema part 1: Structures Second edition, [Online], Available: https:\/\/www.w3.org\/TR\/xmlschema-1\/, October 28, 2004"},{"key":"1301_CR18","unstructured":"J. Clark, M. Makoto. Relax NG tutorial, [Online], Available: https:\/\/relaxng.org\/tutorial-20011203.html, August 10, 2001."},{"key":"1301_CR19","unstructured":"P. Hazel. PCRE-Perl compatible regular expressions, [Online], Available: http:\/\/pcre.org\/, 2005."},{"key":"1301_CR20","unstructured":"The Open Group Base Specifications Issue 7, IEEE Std 1003.1-2017, 2018."},{"key":"1301_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/9781316771273","volume-title":"Introduction to Software Testing","author":"P Ammann","year":"2016","unstructured":"P. Ammann, J. Offutt. Introduction to Software Testing Cambridge USA: Cambridge University Press, 2016."},{"key":"1301_CR22","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/3379597.3387464","volume-title":"An empirical study on regular expression bugs","author":"P P Wang","year":"2020","unstructured":"P. P. Wang, C. Brown, J. A Jennings, K. T. Stolee. An empirical study on regular expression bugs. In Proceedings of the 17th International Conference on Mining Software Repositories, ACM, Seoul, Korea, pp. 103\u2013113, 2020. DOI: https:\/\/doi.org\/10.1145\/3379597.3387464."},{"key":"1301_CR23","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1109\/ASE.2017.8115653","volume-title":"Exploring regular expression comprehension","author":"C Chapman","year":"2017","unstructured":"C. Chapman, P. P. Wang, K. T. Stolee. Exploring regular expression comprehension. In Proceedings of the 32nd IEEE\/ACM International Conference on Automated Software Engineering, IEEE, Urbana, USA, pp. 405\u2013416, 2017. DOI: https:\/\/doi.org\/10.1109\/ASE.2017.8115653."},{"key":"1301_CR24","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1109\/SANER.2019.8667972","volume-title":"Exploring regular expression evolution","author":"P P Wang","year":"2019","unstructured":"P. P. Wang, G. R. Bai, K. T. Stolee. Exploring regular expression evolution. In Proceedings of the 26th IEEE International Conference on Software Analysis, Evolution and Reengineering, IEEE, Hangzhou, China, pp. 502\u2013513, 2019. DOI: https:\/\/doi.org\/10.1109\/SANER.2019.8667972."},{"key":"1301_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1109\/ICPC.2019.00039","volume-title":"Exploring tools and strategies used during regular expression composition tasks","author":"G R Bai","year":"2019","unstructured":"G. R. Bai, B. Clee, N. Shrestha, C. Chapman, C. Wright, K. T. Stolee. Exploring tools and strategies used during regular expression composition tasks. In Proceedings of the 27th IEEE\/ACM International Conference on Program Comprehension, IEEE, Montreal, Canada, pp. 197\u2013208, 2019. DOI: https:\/\/doi.org\/10.1109\/ICPC.2019.00039."},{"key":"1301_CR26","unstructured":"Regular Expression Library. [Online], Available: https:\/\/www.regexlib.com."},{"key":"1301_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/WSE.2010.5623572","volume-title":"Regular expressions on the web","author":"R Hodov\u01cen","year":"2010","unstructured":"R. Hodov\u01cen, Z. Herczeg, \u01cd, Kiss. Regular expressions on the web. In Proceedings of the 12th IEEE International Symposium on Web Systems Evolution, IEEE, Timisoara, Romania, pp. 29\u201332, 2010. DOI: https:\/\/doi.org\/10.1109\/WSE.2010.5623572."},{"key":"1301_CR28","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1145\/3338906.3338909","volume-title":"Why aren\u2019t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions","author":"J C Davis","year":"2019","unstructured":"J. C. Davis, L. G. Michael IV, C. A. Coghlan, F. Servant, D. Lee. Why aren\u2019t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions. In Proceedings of the 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ACM, Tallinn, Estonia, pp. 443\u2013454, 2019. DOI: https:\/\/doi.org\/10.1145\/3338906.3338909."},{"key":"1301_CR29","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-38631-2_11","volume-title":"Static analysis for regular expression denial-of-service attacks","author":"J Kirrage","year":"2013","unstructured":"J. Kirrage, A. Rathnayake, H. Thielecke. Static analysis for regular expression denial-of-service attacks. In Proceedings of the 7th International Conference on Network and System Security, Springer, Madrid, Spain, pp. 135\u2013148, 2013. DOI: https:\/\/doi.org\/10.1007\/978-3-642-38631-2_11."},{"key":"1301_CR30","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1109\/ASE.2019.00047","volume-title":"Regexes are hard: Decision-making, difficulties, and risks in programming regular expressions","author":"L G Michael","year":"2019","unstructured":"L. G. Michael, J. Donohue, J. C. Davis, D. Lee, F. Servant. Regexes are hard: Decision-making, difficulties, and risks in programming regular expressions. In Proceedings of the 34th IEEE\/ACM International Conference on Automated Software Engineering, IEEE, San Diego, USA, pp. 415\u2013426, 2019. DOI: https:\/\/doi.org\/10.1109\/ASE.2019.00047."},{"issue":"2","key":"1301_CR31","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/inco.1997.2688","volume":"140","author":"A Br\u00fcggemann-Klein","year":"1998","unstructured":"A. Br\u00fcggemann-Klein, D. Wood. One-unambiguous regular languages. Information and Computation, vol. 140, no. 2, pp. 229\u2013253, 1998. DOI: https:\/\/doi.org\/10.1006\/inco.1997.2688.","journal-title":"Information and Computation"},{"key":"1301_CR32","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/3216122.3216126","volume-title":"Practical study of deterministic regular expressions from large-scale XML and schema data","author":"Y T Li","year":"2018","unstructured":"Y. T. Li, X. Y. Chu, X. Y. Mou, C. M. Dong, H. M. Chen. Practical study of deterministic regular expressions from large-scale XML and schema data. In Proceedings of the 22nd International Database Engineering & Applications Symposium, ACM, Villa San Giovanni, Italy, pp. 45\u201353, 2018. DOI: https:\/\/doi.org\/10.1145\/3216122.3216126."},{"issue":"1","key":"1301_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1093\/comjnl\/bxy137","volume":"63","author":"L X Zheng","year":"2020","unstructured":"L. X. Zheng, S. Ma, Y. Y. Wang, G. Lin. String generation for testing regular expressions. The Computer Journal, vol. 63, no. 1, pp. 41\u201365, 2020. DOI: https:\/\/doi.org\/10.1093\/comjnl\/bxy137.","journal-title":"The Computer Journal"},{"key":"1301_CR34","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1109\/ASE.2019.00048","volume-title":"Testing regex generalizability and its implications: A large-scale many-language measurement study","author":"J C Davis","year":"2019","unstructured":"J. C. Davis, D. Moyer, A. M. Kazerouni, D. Lee. Testing regex generalizability and its implications: A large-scale many-language measurement study. In Proceedings of the 34th IEEE\/ACM International Conference on Automated Software Engineering, IEEE, San Diego, USA, pp. 427\u2013439, 2019. DOI: https:\/\/doi.org\/10.1109\/ASE.2019.00048."},{"issue":"2","key":"1301_CR35","doi-asserted-by":"publisher","DOI":"10.1145\/1883612.1883618","volume":"43","year":"2011","unstructured":"C. Nie, H. Leung. A survey of combinatorial testing. ACM Computing Surveys, vol. 43, no. 2, Article number 11, 2011. DOI: https:\/\/doi.org\/10.1145\/1883612.1883618.","journal-title":"ACM Computing Surveys"},{"issue":"4","key":"1301_CR36","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/C-M.1978.218136","volume":"11","author":"R A DeMillo","year":"1978","unstructured":"R. A. DeMillo, R. J. Lipton, F. G. Sayward. Hints on test data selection: Help for the practicing programmer. Computer, vol. 11, no. 4, pp. 34\u201341, 1978. DOI: https:\/\/doi.org\/10.1109\/CM.1978.218136.","journal-title":"Computer"},{"key":"1301_CR37","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1109\/ICSTW.2017.23","volume-title":"MutRex: A mutation-based generator of fault detecting strings for regular expressions","author":"P Arcaini","year":"2017","unstructured":"P. Arcaini, A. Gargantini, E. Riccobene. MutRex: A mutation-based generator of fault detecting strings for regular expressions. In Proceedings of IEEE International Conference on Software Testing, Verification and Validation Workshops, IEEE, Tokyo, Japan, pp. 87\u201396, 2017. DOI: https:\/\/doi.org\/10.1109\/ICSTW.2017.23."},{"issue":"3","key":"1301_CR38","first-page":"531","volume":"30","author":"M C F P Emer","year":"2011","unstructured":"M. C. F. P. Emer, I. F. Nazar, S. R. Vergilio, M. Jino. Fault-based test of XML schemas. Computing and Informatics, vol. 30, no. 3, pp. 531\u2013557, 2011.","journal-title":"Computing and Informatics"},{"key":"1301_CR39","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/COMPSAC.2005.151","volume-title":"Testing the semantics of W3C XML schema","author":"J B Li","year":"2005","unstructured":"J. B. Li, J. Miller. Testing the semantics of W3C XML schema. In Proceedings of the 29th Annual International Computer Software and Applications Conference, IEEE, Edinburgh, UK, pp. 443\u2013448, 2005. DOI: https:\/\/doi.org\/10.1109\/COMPSAC.2005.151."},{"key":"1301_CR40","first-page":"551","volume-title":"Counting and random generation of strings in regular languages","author":"S Kannan","year":"1995","unstructured":"S. Kannan, Z. Sweedyk, S. R. Mahaney. Counting and random generation of strings in regular languages. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, San Francisco, USA, pp. 551\u2013557, 1995."},{"issue":"1\u20132","key":"1301_CR41","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/s00453-010-9446-5","volume":"62","author":"O Bernardi","year":"2012","unstructured":"O. Bernardi, O. Gim\u00e8nez. A linear algorithm for the random sampling from regular languages. Algorithmica, vol. 62, no. 1\u20132, pp. 130\u2013145, 2012. DOI: https:\/\/doi.org\/10.1007\/s00453-010-9446-5.","journal-title":"Algorithmica"},{"key":"1301_CR42","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-540-76336-9_22","volume-title":"Efficient enumeration of regular languages","author":"M Ackerman","year":"2007","unstructured":"M. Ackerman, J. Shallit. Efficient enumeration of regular languages. In Proceedings of the 12th International Conference on Implementation and Application of Automata, Praque, Czech Republic, Springer, pp. 226\u2013242, 2007. DOI: https:\/\/doi.org\/10.1007\/978-3-540-76336-9_22."},{"issue":"37","key":"1301_CR43","doi-asserted-by":"publisher","first-page":"3461","DOI":"10.1016\/j.tcs.2009.03.018","volume":"410","author":"M Ackerman","year":"2009","unstructured":"M. Ackerman, J. Shallit. Efficient enumeration of words in regular languages. Theoretical Computer Science, vol. 410, no. 37, pp. 3461\u20133470, 2009. DOI: https:\/\/doi.org\/10.1016\/j.tcs.2009.03.018.","journal-title":"Theoretical Computer Science"},{"key":"1301_CR44","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/3278122.3278133","volume-title":"Regenerate: A language generator for extended regular expressions","author":"G Radanne","year":"2018","unstructured":"G. Radanne, P. Thiemann. Regenerate: A language generator for extended regular expressions. In Proceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, ACM, Boston, USA, pp. 202\u2013214, 2018. DOI: https:\/\/doi.org\/10.1145\/3278122.3278133."},{"key":"1301_CR45","unstructured":"Xeger. [Online], Availabe: https:\/\/code.google.com\/archive\/p\/xeger\/."},{"key":"1301_CR46","unstructured":"Exrex. [Online], Available: https:\/\/github.com\/asciimoo\/exrex."},{"key":"1301_CR47","unstructured":"Generex. [Online], Available: https:\/\/github.com\/mifmif\/generex."},{"key":"1301_CR48","unstructured":"Regldg. [Online], Available: https:\/\/regldg.com\/."},{"issue":"1\u20132","key":"1301_CR49","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.1664","volume":"29","year":"2019","unstructured":"P. Arcaini, A. Gargantini, E. Riccobene. Fault-based test generation for regular expressions by mutation. Software: Testing, Verification and Reliability, vol. 29, no. 1\u20132, Article number e1664, 2019. DOI: https:\/\/doi.org\/10.1002\/stvr.1664.","journal-title":"Software: Testing, Verification and Reliability"},{"issue":"3","key":"1301_CR50","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E M Gold","year":"1978","unstructured":"E. M. Gold. Complexity of automaton identification from given data. Information and Control, vol. 37, no. 3, pp. 302\u2013320, 1978. DOI: https:\/\/doi.org\/10.1016\/S0019-9958(78)90562-4.","journal-title":"Information and Control"},{"key":"1301_CR51","doi-asserted-by":"publisher","unstructured":"J. Oncina, P. Garc\u01d0a. Identifying regular languages in polynomial time. Advances in Structural and Syntactic Pattern Recognition, H. Bunke, Ed., World Scientific, pp. 99\u2013108, 1993. DOI: https:\/\/doi.org\/10.1142\/9789812797919_0007.","DOI":"10.1142\/9789812797919_0007"},{"key":"1301_CR52","doi-asserted-by":"publisher","first-page":"1285","DOI":"10.1145\/2063576.2063763","volume-title":"Enabling information extraction by inference of regular expressions from sample entities","author":"F Brauer","year":"2011","unstructured":"F. Brauer, R. Rieger, A. Mocan, W. M. Barczynski. Enabling information extraction by inference of regular expressions from sample entities. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, ACM, Glasgow, UK, pp. 1285\u20131294, 2011. DOI: https:\/\/doi.org\/10.1145\/2063576.2063763."},{"issue":"12","key":"1301_CR53","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1109\/MC.2014.344","volume":"47","author":"A Bartoli","year":"2014","unstructured":"A. Bartoli, G. Davanzo, A. De Lorenzo, E. Medvet, E. Sorio. Automatic synthesis of regular expressions from examples. Computer, vol. 47, no. 12, pp. 72\u201380, 2014. DOI: https:\/\/doi.org\/10.1109\/MC.2014.344.","journal-title":"Computer"},{"issue":"6","key":"1301_CR54","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1109\/MIS.2016.46","volume":"31","author":"A Bartoli","year":"2016","unstructured":"A. Bartoli, A. De Lorenzo, E. Medvet, F. Tarlao. Can a machine replace humans in building regular expressions? A case study IEEE Intelligent Systems, vol. 31, no. 6, pp. 15\u201321, 2016. DOI: https:\/\/doi.org\/10.1109\/MIS.2016.46.","journal-title":"IEEE Intelligent Systems"},{"issue":"3","key":"1301_CR55","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1109\/TCYB.2017.2680466","volume":"48","author":"A Bartoli","year":"2017","unstructured":"A. Bartoli, A. De Lorenzo, E. Medvet, F. Tarlao. Active learning of regular expressions for entity extraction. IEEE Transactions on Cybernetics, vol. 48, no. 3, pp. 1067\u20131080, 2017. DOI: https:\/\/doi.org\/10.1109\/TCYB.2017.2680466.","journal-title":"IEEE Transactions on Cybernetics"},{"issue":"5","key":"1301_CR56","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1109\/TKDE.2016.2515587","volume":"28","author":"A Bartoli","year":"2016","unstructured":"A. Bartoli, A. De Lorenzo, E. Medvet, F. Tarlao. Inference of regular expressions for text extraction from examples. IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp. 1217\u20131230, 2016. DOI: https:\/\/doi.org\/10.1109\/TKDE.2016.2515587.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"1301_CR57","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2993236.2993244","volume-title":"Synthesizing regular expressions from examples for introductory automata assignments","author":"M Lee","year":"2016","unstructured":"M. Lee, S. So, H. Oh. Synthesizing regular expressions from examples for introductory automata assignments. In Proceedings of ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, ACM, Amsterdam, The Netherlands, pp. 70\u201380, 2016. DOI: https:\/\/doi.org\/10.1145\/2993236.2993244."},{"issue":"5","key":"1301_CR58","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E M Gold","year":"1967","unstructured":"E. M. Gold, The RAND Corporation. Language identification in the limit. Information and Control, vol. 10, no. 5, pp. 447\u2013474, 1967. DOI: https:\/\/doi.org\/10.1016\/S0019-9958(67)91165-5.","journal-title":"Information and Control"},{"key":"1301_CR59","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890","volume-title":"ACM Transactions on Database Systems","author":"G J Bex","year":"2010","unstructured":"G. J. Bex, F. Neven, T. Schwentick, S. Vansummeren. Inference of concise regular expressions and DTDs. ACM Transactions on Database Systems, vol. 35, no. 2, Article number 11, 2010. DOI: https:\/\/doi.org\/10.1145\/1735886.1735890."},{"issue":"4","key":"1301_CR60","doi-asserted-by":"publisher","first-page":"1114","DOI":"10.1007\/s00224-014-9559-3","volume":"57","author":"D D Freydenberger","year":"2015","unstructured":"D. D. Freydenberger, T. K\u00f6tzing. Fast learning of restricted regular expressions and DTDs. Theory of Computing Systems, vol. 57, no. 4, pp. 1114\u20131158, 2015. DOI: https:\/\/doi.org\/10.1007\/s00224-014-9559-3.","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"1301_CR61","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/j.ic.2008.12.008","volume":"207","author":"H Fernau","year":"2009","unstructured":"H. Fernau. Algorithms for learning regular expressions from positive data. Information and Computation, vol. 207, no. 4, pp. 521\u2013541, 2009. DOI: https:\/\/doi.org\/10.1016\/j.ic.2008.12.008.","journal-title":"Information and Computation"},{"key":"1301_CR62","unstructured":"N. Kushman, R. Barzilay. Using semantic unification to generate regular expressions from natural language. In Proceedings of Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Atlanta, USA, pp. 826\u2013836, 2013."},{"key":"1301_CR63","doi-asserted-by":"publisher","unstructured":"N. Locascio, K. Narasimhan, E. DeLeon, N. Kushman, R. Barzilay. Neural generation of regular expressions from natural language with minimal domain knowledge. In Proceedings of Conference on Empirical Methods in Natural Language Processing, Austin, Texas, USA, pp. 1918\u20131923, 2016. DOI: https:\/\/doi.org\/10.18653\/v1\/D16-1197.","DOI":"10.18653\/v1\/D16-1197"},{"key":"1301_CR64","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.18653\/v1\/D18-1189","volume-title":"SemRegex: A semantics-based approach for generating regular expressions from natural language specifications","author":"Z X Zhong","year":"2018","unstructured":"Z. X. Zhong, J. Q. Guo, W. Yang, J. Peng, T. Xie, J. G. Lou, T. Liu, D. M. Zhang. SemRegex: A semantics-based approach for generating regular expressions from natural language specifications. In Proceedings of Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Brussels, Belgium, pp. 1608\u20131618, 2018. DOI: https:\/\/doi.org\/10.18653\/v1\/D18-1189."},{"key":"1301_CR65","doi-asserted-by":"crossref","unstructured":"Z. X. Zhong, J. Q. Guo, W. Yang, T. Xie, J. G. Lou, T. Liu, D. M. Zhang. Generating regular expressions from natural language specifications: Are we there yet? In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, New Orleans, USA, pp. 791\u2013794, 2018.","DOI":"10.18653\/v1\/D18-1189"},{"key":"1301_CR66","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1145\/33854122.3385988","volume-title":"Multi-modal synthesis of regular expressions","author":"Q C Chen","year":"2020","unstructured":"Q. C. Chen, X. Y. Wang, X. Ye, G. Durrett, I. Dillig. Multi-modal synthesis of regular expressions. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM, London, UK, pp. 487\u2013502, 2020. DOI: https:\/\/doi.org\/10.1145\/33854122.3385988."},{"issue":"2","key":"1301_CR67","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/767193.767195","volume":"3","author":"H Hosoya","year":"2003","unstructured":"H. Hosoya, B. C. Pierce. XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology, vol. 3, no. 2, pp. 117\u2013148, 2003. DOI: https:\/\/doi.org\/10.1145\/767193.767195.","journal-title":"ACM Transactions on Internet Technology"},{"key":"1301_CR68","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11560586_13","volume-title":"Error mining for regular expression patterns","author":"G Castagna","year":"2005","unstructured":"G. Castagna, D. Colazzo, A. Frisch. Error mining for regular expression patterns. In Proceedings of the 9th Italian Conference on Theoretical Computer Science, Springer, Siena, Italy, pp. 160\u2013172, 2005. DOI: https:\/\/doi.org\/10.1007\/11560586_13."},{"issue":"9","key":"1301_CR69","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/944746.944711","volume":"38","author":"V Benzaken","year":"2003","unstructured":"V. Benzaken, G. Castagna, A. Frisch. CDuce: An XML-centric general-purpose language. ACM SIGPLAN Notices, vol. 38, no. 9, pp. 51\u201363, 2003. DOI: https:\/\/doi.org\/10.1145\/944746.944711.","journal-title":"ACM SIGPLAN Notices"},{"key":"1301_CR70","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/SCAM.2018.00034","volume-title":"Automatic checking of regular expressions","author":"E Larson","year":"2018","unstructured":"E. Larson. Automatic checking of regular expressions. In Proceedings of the 18th IEEE International Working Conference on Source Code Analysis and Manipulation, IEEE, Madrid, Spain, pp. 225\u2013234, 2018. DOI: https:\/\/doi.org\/10.1109\/SCAM.2018.00034."},{"key":"1301_CR71","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1109\/HASE.2019.00011","volume-title":"A lightweight framework for regular expression verification","author":"X Liu","year":"2019","unstructured":"X. Liu, Y. F. Jiang, D. H. Wu. A lightweight framework for regular expression verification. In Proceedings of the 19th IEEE International Symposium on High Assurance Systems Engineering, IEEE, Hangzhou, China, pp. 11\u20138, 2019. DOI: https:\/\/doi.org\/10.1109\/HASE.2019.00011."},{"key":"1301_CR72","unstructured":"RegExr. [Online], Available: https:\/\/regexr.com\/."},{"key":"1301_CR73","unstructured":"Regular Expressions 101. [Online], Available: https:\/\/regex101.com\/."},{"key":"1301_CR74","unstructured":"RegexBuddy. [Online], Available: http:\/\/www.regexbuddy.com\/."},{"key":"1301_CR75","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.1109\/EURCON.2007.4400374","volume-title":"RegExpert: A tool for visualization of regular expressions","author":"I Budiselic","year":"2007","unstructured":"I. Budiselic, S. Srbljic, M. Popovic. RegExpert: A tool for visualization of regular expressions. In Proceedings of International Conference on \u201cComputer as a Tool\u201d, IEEE, Warsaw, Poland, pp. 2387\u20132389, 2007. DOI: https:\/\/doi.org\/10.1109\/EURCON.2007.4400374."},{"key":"1301_CR76","unstructured":"RegExper. [Online], Available: https:\/\/regexper.com\/."},{"key":"1301_CR77","unstructured":"Regular Expression Exploration.[Online], Available: https:\/\/rise4fun.com\/rex\/."},{"key":"1301_CR78","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-45526-4_4","volume-title":"Animation of the generation and computation of finite automata for learning software","author":"B Braune","year":"2001","unstructured":"B. Braune, S. Diehl, A. Kerren, R. Wilhelm. Animation of the generation and computation of finite automata for learning software. In Proceedings of the 4th International Workshop on Implementing Automata, Springer, Potsdam, Germany, pp. 39\u201347, 2001. DOI: https:\/\/doi.org\/10.1007\/3-540-45526-4_4."},{"issue":"1","key":"1301_CR79","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/331795.331800","volume":"32","author":"T Hung","year":"2000","unstructured":"T. Hung, S. H. Rodger. Rodger. Increasing visualization and interaction in the automata theory course. ACM SIGCSE Bulletin, vol. 32, no. 1, pp. 6\u201310, 2000. DOI: https:\/\/doi.org\/10.1145\/331795.331800.","journal-title":"Rodger. Increasing visualization and interaction in the automata theory course"},{"issue":"5","key":"1301_CR80","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1006\/jvlc.2001.0216","volume":"12","author":"A F Blackwell","year":"2001","unstructured":"A. F. Blackwell. See what you need: Helping end-users to build abstractions. Journal of Visual Languages & Computing, vol. 12, no. 5, pp. 475\u2013499, 2001. DOI: https:\/\/doi.org\/10.1006\/jvlc.2001.0216.","journal-title":"Journal of Visual Languages & Computing"},{"key":"1301_CR81","first-page":"86","volume-title":"Y\u0131lmaz. Vi-xfst: A visual regular expression development environment for Xerox finite state tool","author":"K Oflazer","year":"2004","unstructured":"K. Oflazer, Y\u0131lmaz. Vi-xfst: A visual regular expression development environment for Xerox finite state tool. In Proceedings of the Workshop on ACL Special Interest Group in Computational Phonology, ACM, Barcelona, Spain, pp. 86\u201393, 2004."},{"key":"1301_CR82","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1145\/2591062.2591111","volume-title":"Regviz: Visual debugging of regular expressions","author":"F Beck","year":"2014","unstructured":"F. Beck, S. Gulan, B. Biegel, S. Baltes, D. Weiskopf. Regviz: Visual debugging of regular expressions. In Proceedings of the 36th International Conference on Software Engineering, ACM, Hyderabad, India, pp. 504\u2013507, 2014. DOI: https:\/\/doi.org\/10.1145\/2591062.2591111."},{"key":"1301_CR83","first-page":"21","volume-title":"Regular expression learning for information extraction","author":"Y Y Li","year":"2008","unstructured":"Y. Y. Li, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, H. V. Jagadish. Regular expression learning for information extraction. In Proceedings of Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Honolulu, USA, pp. 21\u201330, 2008."},{"key":"1301_CR84","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-93037-4_6","volume-title":"Adding missing words to regular expressions","author":"T Rebele","year":"2018","unstructured":"T. Rebele, K. Tzompanaki, F. M. Suchanek. Adding missing words to regular expressions. In Proceedings of the 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, Melbourne, Australia, pp. 67\u201379, 2018. DOI: https:\/\/doi.org\/10.1007\/978-3-319-93037-4_6."},{"key":"1301_CR85","doi-asserted-by":"publisher","unstructured":"R. Pan, Q. H. P. Hu, G. W. Xu, L. D\u2019Antoni. Automatic repair of regular expressions. In Proceedings of the ACM on Programming Languages, vol. 3, Article number 139, 2019. DOI: https:\/\/doi.org\/10.1145\/3360565.","DOI":"10.1145\/3360565"},{"key":"1301_CR86","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1145\/3324884.3416556","volume-title":"FlashRegex: Deducing Anti-ReDoS regexes from examples","author":"Y T Li","year":"2020","unstructured":"Y. T. Li, Z. W. Xu, J. L. Cao, H. M. Chen, T. J. Ge, S. C. Cheung, H. R. Zhao. FlashRegex: Deducing Anti-ReDoS regexes from examples. In Proceedings of the 35th IEEE\/ACM International Conference on Automated Software Engineering, IEEE, Melbourne, Australia, pp. 659\u2013671, 2020. DOI: https:\/\/doi.org\/10.1145\/3324884.3416556."},{"key":"1301_CR87","unstructured":"N. Chida, T. Terauchi. Automatic repair of vulnerable regular expressions. [Online], Available: https:\/\/arxiv.org\/abs\/2010.12450, 2020."},{"key":"1301_CR88","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-030-31280-0_2","volume-title":"Regular expression learning with evolutionary testing and repair","author":"P Arcaini","year":"2019","unstructured":"P. Arcaini, A. Gargantini, E. Riccobene. Regular expression learning with evolutionary testing and repair. In Proceedings of the 31st IFIP International Conference on Testing Software and Systems, Springer, Paris, France, pp. 22\u201340, 2019. DOI: https:\/\/doi.org\/10.1007\/978-3-030-31280-0_2."},{"key":"1301_CR89","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1145\/2676726.2676973","volume-title":"Program boosting: Program synthesis via crowd-sourcing","author":"R A Cochran","year":"2015","unstructured":"R. A. Cochran, L. D\u2019Antoni, B. Livshits, D. Molnar, M. Veanes. Program boosting: Program synthesis via crowd-sourcing. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM, Mumbai, India, pp. 677\u2013688, 2015. DOI: https:\/\/doi.org\/10.1145\/2676726.2676973."},{"key":"1301_CR90","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-99927-2_1","volume-title":"Interactive testing and repairing of regular expressions","author":"P Arcaini","year":"2018","unstructured":"P. Arcaini, A. Gargantini, E. Riccobene. Interactive testing and repairing of regular expressions. In Proceedings of the 30th IFIP International Conference on Testing Software and Systems, Springer, C\u00e1diz, Spain, pp. 1\u201316, 2018. DOI: https:\/\/doi.org\/10.1007\/978-3-319-99927-2_1."},{"issue":"3","key":"1301_CR91","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s11633-016-1008-0","volume":"16","author":"X H Qiu","year":"2019","unstructured":"X. H. Qiu, Y. T. Hu, B. Li. Sequential Fault diagnosis using an inertial velocity differential evolution algorithm. International Journal of Automation and Computing, vol. 16, no. 3, pp. 389\u2013397, 2019. DOI: https:\/\/doi.org\/10.1007\/s11633-016-1008-0.","journal-title":"International Journal of Automation and Computing"}],"container-title":["International Journal of Automation and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-021-1301-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11633-021-1301-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-021-1301-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T17:46:03Z","timestamp":1626284763000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11633-021-1301-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,4]]},"references-count":91,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["1301"],"URL":"https:\/\/doi.org\/10.1007\/s11633-021-1301-4","relation":{},"ISSN":["1476-8186","1751-8520"],"issn-type":[{"value":"1476-8186","type":"print"},{"value":"1751-8520","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,4]]},"assertion":[{"value":"27 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}