{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:19:10Z","timestamp":1742959150799,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":57,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819986637"},{"type":"electronic","value":"9789819986644"}],"license":[{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-99-8664-4_12","type":"book-chapter","created":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T06:05:13Z","timestamp":1702533913000},"page":"206-225","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Modeling Regex Operators for\u00a0Solving Regex Crossword Puzzles"],"prefix":"10.1007","author":[{"given":"Weihao","family":"Su","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rongchen","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zixuan","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,15]]},"reference":[{"key":"12_CR1","unstructured":"Abolofia, R.: regex-crossword-solver (2015). https:\/\/github.com\/purple4reina\/regex-crossword-solver"},{"key":"12_CR2","first-page":"255","volume":"1","author":"V Alfred","year":"2014","unstructured":"Alfred, V.: Algorithms for finding patterns in strings. Algorithms Complex. 1, 255 (2014)","journal-title":"Algorithms Complex."},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/1353782.1374190","volume":"15","author":"R Anderson","year":"2008","unstructured":"Anderson, R., Kolko, J.: Crossword puzzle: clues and solutions. Interactions 15(3), 35 (2008)","journal-title":"Interactions"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Appelt, D., Panichella, A., Briand, L.: Automatically repairing web application firewalls based on successful SQL injection attacks. In: ISSRE 2017, pp. 339\u2013350 (2017)","DOI":"10.1109\/ISSRE.2017.28"},{"key":"12_CR5","unstructured":"Bartoli, A., De Lorenzo, A., Medvet, E., Tarlao, F.: Active learning of predefined models for information extraction: selecting regular expressions from examples. In: FSDM 2019, pp. 645\u2013651 (2019)"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Beacham, A., Chen, X., Sillito, J., van Beek, P.: Constraint programming lessons learned from crossword puzzles. In: AI 2001, pp. 78\u201387 (2001)","DOI":"10.1007\/3-540-45153-6_8"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2022.10.041","volume":"940","author":"M Berglund","year":"2022","unstructured":"Berglund, M., van der Merwe, B.: Re-examining regular expressions with backreferences. Theor. Comput. Sci. 940, 66\u201380 (2022)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"12_CR8","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00236-016-0282-1","volume":"55","author":"H Bj\u00f6rklund","year":"2018","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Conjunctive query containment over trees using schema information. Acta Informatica 55(1), 17\u201356 (2018)","journal-title":"Acta Informatica"},{"key":"12_CR9","unstructured":"Black, L.: Can You Do the Regular Expression Crossword (2014). https:\/\/www.i-programmer.info\/news\/144-graphics-and-games\/5450-can-youdo-the-regular-expression-crossword.html"},{"issue":"06","key":"12_CR10","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14(06), 1007\u20131018 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Cao, J., Li, M., Li, Y., Wen, M., Cheung, S.C., Chen, H.: SemMT: a semantic-based testing approach for machine translation systems. In: TOSEM 2022, pp. 1\u201336 (2022)","DOI":"10.1145\/3490488"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Carle, B., Narendran, P.: On extended regular expressions. In: LATA 2009, pp. 279\u2013289 (2009)","DOI":"10.1007\/978-3-642-00982-2_24"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Caruccio, L., Cirillo, S., Deufemia, V., Polese, G.: Efficient validation of functional dependencies during incremental discovery. In: SEBD 2021, pp. 5\u20139 (2021)","DOI":"10.1145\/3487664.3487719"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Chen, Q., Wang, X., Ye, X., Durrett, G., Dillig, I.: Multi-modal synthesis of regular expressions. In: PLDI 2020, pp. 487\u2013502 (2020)","DOI":"10.1145\/3385412.3385988"},{"issue":"6","key":"12_CR15","first-page":"1","volume":"2022","author":"T Chen","year":"2022","unstructured":"Chen, T., et al.: Solving string constraints with regex-dependent functions through transducers with priorities and variables. POPL 2022(6), 1\u201331 (2022)","journal-title":"POPL"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Chen, T., et al.: Solving string constraints with regex-dependent functions through transducers with priorities and variables. In: POPL 2022, vol. 6, pp. 1\u201331 (2022)","DOI":"10.1145\/3498707"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Chida, N., Terauchi, T.: Repairing DoS vulnerability of real-world regexes. In: S &P 2022, pp. 1049\u20131066 (2022)","DOI":"10.1109\/SP46214.2022.9833597"},{"key":"12_CR18","unstructured":"Chida, N., Terauchi, T.: On lookaheads in regular expressions with backreferences. In: FSCD 2022, vol. 228, pp. 15:1\u201315:18 (2022)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Clarke, E., Grumberg, O., Jha, S., Lu, Y., Veith, H.: Counterexample-guided abstraction refinement. In: CAV 2000, pp. 154\u2013169 (2000)","DOI":"10.1007\/10722167_15"},{"key":"12_CR20","unstructured":"Cox, R.: Regular Expression Matching Can Be Simple And Fast (2007). https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html"},{"key":"12_CR21","unstructured":"Cox, R.: Regular Expression Matching in the Wild (2010). https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html"},{"key":"12_CR22","unstructured":"CTFtime.org: CTFtime.org\/HackPack CTF 2021\/Regex World (2021). https:\/\/ctftime.org\/task\/15582"},{"issue":"2","key":"12_CR23","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/3484622.3484624","volume":"50","author":"J Doleschal","year":"2021","unstructured":"Doleschal, J., Kimelfeld, B., Martens, W.: Database principles and challenges in text analysis. ACM SIGMOD Rec. 50(2), 6\u201317 (2021)","journal-title":"ACM SIGMOD Rec."},{"key":"12_CR24","unstructured":"ECMA-262: ECMAScript\u00ae 2022 Language Specification (2022). https:\/\/tc39.es\/ecma262\/multipage\/"},{"key":"12_CR25","unstructured":"Fenner, S.: The complexity of some regex crossword problems (2014)"},{"key":"12_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104777","volume":"286","author":"S Fenner","year":"2021","unstructured":"Fenner, S., Pad\u00e9, D., Thierauf, T.: The complexity of regex crosswords. Inf. Comput. 286, 104777 (2021)","journal-title":"Inf. Comput."},{"issue":"1","key":"12_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3351451","volume":"45","author":"F Florenzano","year":"2020","unstructured":"Florenzano, F., Riveros, C., Ugarte, M., Vansummeren, S., Vrgo\u010d, D.: Efficient enumeration algorithms for regular document spanners. ACM Trans. Database Syst. 45(1), 1\u201342 (2020)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"12_CR28","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-012-9389-0","volume":"53","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D.: Extended regular expressions: succinctness and decidability. Theory Comput. Syst. 53(2), 159\u2013193 (2013)","journal-title":"Theory Comput. Syst."},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2019.04.001","volume":"105","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. 105, 1\u201339 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1137\/100814196","volume":"41","author":"W Gelade","year":"2012","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: weak versus strong determinism. SIAM J. Comput. 41(1), 160\u2013190 (2012)","journal-title":"SIAM J. Comput."},{"key":"12_CR31","unstructured":"Ginsberg, M.L., Frank, M.C., Halpin, M.P., Torrance, M.C.: Search lessons learned from crossword puzzles. In: AAAI-1990 (1990)"},{"issue":"1","key":"12_CR32","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1109\/TR.2019.2925415","volume":"69","author":"H Gu","year":"2019","unstructured":"Gu, H., et al.: DIAVA: a traffic-based framework for detection of SQL injection attacks and vulnerability analysis of leaked data. IEEE Trans. Reliab. 69(1), 188\u2013202 (2019)","journal-title":"IEEE Trans. Reliab."},{"key":"12_CR33","unstructured":"Jeong, Y.: regex-crossword-solver (2018). https:\/\/github.com\/blukat29\/regex-crossword-solver"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Jiang, C., Zhao, Y., Chu, S., Shen, L., Tu, K.: Cold-start and interpretability: turning regular expressions into trainable recurrent neural networks. In: EMNLP 2020, pp. 3193\u20133207 (2020)","DOI":"10.18653\/v1\/2020.emnlp-main.258"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Li, G., Ghosh, I.: PASS: string solving with parameterized array and interval automaton. In: HVC 2013, pp. 15\u201331 (2013)","DOI":"10.1007\/978-3-319-03077-7_2"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Li, Y., Cao, J., Chen, H., Ge, T., Xu, Z., Peng, Q.: FlashSchema: achieving high quality XML schemas with powerful inference algorithms and large-scale schema data. In: ICDE 2020, pp. 1962\u20131965 (2020)","DOI":"10.1109\/ICDE48307.2020.00214"},{"key":"12_CR37","unstructured":"Li, Y., et al.: ReDoSHunter: a combined static and dynamic approach for regular expression DoS detection. In: USENIX Security 2021, pp. 3847\u20133864 (2021)"},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Li, Y., et al.: FlashRegex: deducing anti-ReDoS regexes from examples. In: ASE 2020, pp. 659\u2013671 (2020)","DOI":"10.1145\/3324884.3416556"},{"issue":"2","key":"12_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2850413","volume":"63","author":"L Libkin","year":"2016","unstructured":"Libkin, L., Martens, W., Vrgo\u010d, D.: Querying graphs with data. J. ACM 63(2), 1\u201353 (2016)","journal-title":"J. ACM"},{"key":"12_CR40","doi-asserted-by":"crossref","unstructured":"Liu, J., Bai, R., Lu, Z., Ge, P., Aickelin, U., Liu, D.: Data-driven regular expressions evolution for medical text classification using genetic programming. In: CEC 2020, pp. 1\u20138 (2020)","DOI":"10.1109\/CEC48606.2020.9185500"},{"key":"12_CR41","doi-asserted-by":"crossref","unstructured":"Loring, B., Mitchell, D., Kinder, J.: ExpoSE: practical symbolic execution of standalone JavaScript. In: SPIN 2017, pp. 196\u2013199 (2017)","DOI":"10.1145\/3092282.3092295"},{"key":"12_CR42","doi-asserted-by":"crossref","unstructured":"Loring, B., Mitchell, D., Kinder, J.: Sound regular expression semantics for dynamic symbolic execution of JavaScript. In: PLDI 2019, pp. 425\u2013438 (2019)","DOI":"10.1145\/3314221.3314645"},{"key":"12_CR43","unstructured":"MIT: A Regular Crossword (Solution) (2013). http:\/\/www.mit.edu\/activities\/puzzle\/2013\/coinheist.com\/rubik\/a_regular_crossword\/answer\/index.html"},{"key":"12_CR44","doi-asserted-by":"crossref","unstructured":"de Moura, L., Bj\u00f8rner, N.: Z3: an efficient SMT solver. In: TACAS 2008, pp. 337\u2013340 (2008)","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"12_CR45","doi-asserted-by":"crossref","unstructured":"Pan, R., Hu, Q., Xu, G., D\u2019Antoni, L.: Automatic repair of regular expressions. In: OOPSLA 2019, vol. 3, pp. 1\u201329 (2019)","DOI":"10.1145\/3360565"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Pesant, G.: A regular language membership constraint for finite sequences of variables. In: CP 2004, pp. 482\u2013495 (2004)","DOI":"10.1007\/978-3-540-30201-8_36"},{"key":"12_CR47","doi-asserted-by":"crossref","unstructured":"Polo, M., Pedreira, O., S. Places, \u00c1., Garcia Rodriguez de Guzman, I.: Automated generation of oracled test cases with regular expressions and combinatorial techniques. J. Softw. Evol. Process 32(12), e2273 (2020)","DOI":"10.1002\/smr.2273"},{"key":"12_CR48","doi-asserted-by":"crossref","unstructured":"Saxena, P., Akhawe, D., Hanna, S., Mao, F., McCamant, S., Song, D.: A symbolic execution framework for JavaScript. In: S &P 2010, pp. 513\u2013528 (2010)","DOI":"10.1109\/SP.2010.38"},{"key":"12_CR49","unstructured":"Schaaf, H.: regex-crossword-solver (2014). https:\/\/github.com\/hermanschaaf\/regex-crossword-solver"},{"key":"12_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising REGEX languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016)","journal-title":"Inf. Comput."},{"key":"12_CR51","unstructured":"Shcherban, M.: GP-crossword-solver (2019). https:\/\/github.com\/maxymczech\/gp-regex-crossword"},{"key":"12_CR52","unstructured":"Slashdot: Can You Do the Regular Expression Crossword (2013). https:\/\/games.slashdot.org\/story\/13\/02\/13\/2346253\/canyou-do-the-regular-expression-crossword"},{"key":"12_CR53","unstructured":"Trux, A.: Regex-crossword-solver (2017). https:\/\/github.com\/antoine-trux\/regex-crossword-solver"},{"key":"12_CR54","doi-asserted-by":"crossref","unstructured":"Veanes, M., De Halleux, P., Tillmann, N.: Rex: symbolic regular expression explorer. In: ICST 2010, pp. 498\u2013507 (2010)","DOI":"10.1109\/ICST.2010.15"},{"key":"12_CR55","doi-asserted-by":"crossref","unstructured":"Yan, Y., et al.: Deducing matching strings for real-world regular expressions. In: SETTA 2023 (2023, accepted)","DOI":"10.1007\/978-981-99-8664-4_19"},{"key":"12_CR56","doi-asserted-by":"crossref","unstructured":"Yu, F., Shueh, C.Y., Lin, C.H., Chen, Y.F., Wang, B.Y., Bultan, T.: Optimal sanitization synthesis for web application vulnerability repair. In: ISSTA 2016, pp. 189\u2013200 (2016)","DOI":"10.1145\/2931037.2931050"},{"key":"12_CR57","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar, pp. 41\u2013110 (1997)","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Dependable Software Engineering. Theories, Tools, and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-99-8664-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T03:21:54Z","timestamp":1703733714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-99-8664-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,15]]},"ISBN":["9789819986637","9789819986644"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-981-99-8664-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,15]]},"assertion":[{"value":"15 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SETTA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Dependable Software Engineering: Theories, Tools, and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nanjing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 November 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 November 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"setta2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lcs.ios.ac.cn\/setta2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}