{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:42:39Z","timestamp":1743100959826,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":31,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819606016"},{"type":"electronic","value":"9789819606023"}],"license":[{"start":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T00:00:00Z","timestamp":1732492800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T00:00:00Z","timestamp":1732492800000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-0602-3_19","type":"book-chapter","created":{"date-parts":[[2024,11,24]],"date-time":"2024-11-24T03:46:25Z","timestamp":1732419985000},"page":"344-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Derivative-Based Membership Algorithm for\u00a0Enhanced Regular Expressions"],"prefix":"10.1007","author":[{"given":"Mengxi","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunmei","family":"Dong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weihao","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengyao","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,25]]},"reference":[{"issue":"2","key":"19_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Location automata for regular expressions with shuffle and intersection. Inf. Comput. 295(Part B), 104917 (2023)","DOI":"10.1016\/j.ic.2022.104917"},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theoret. Comput. Sci. 120(2), 197\u2013213 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"19_CR4","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"JA Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481\u2013494 (1964)","journal-title":"J. ACM"},{"key":"19_CR5","unstructured":"Clark, J., Makoto, M.: Relax NG specification. oasis (2001). http:\/\/www.oasis-open.org\/committees\/relax-ng\/spec-20011203.html (2004)"},{"issue":"4","key":"19_CR6","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3132701","volume":"42","author":"D Colazzo","year":"2017","unstructured":"Colazzo, D., Ghelli, G., Sartiani, C.: Linear time membership in a class of regular expressions with counting, interleaving, and unordered concatenation. ACM Trans. Database Syst. 42(4), 24 (2017)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3651601","volume":"2","author":"C David","year":"2024","unstructured":"David, C., Francis, N., Marsault, V.: Distinct shortest walk enumeration for RPQs. Proc. ACM Manage. Data 2(2), 1\u201322 (2024)","journal-title":"Proc. ACM Manage. Data"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Davis, J.C., IV, L.G.M., Coghlan, C.A., Servant, F., Lee, D.: Why aren\u2019t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions. In: ESEC\/FSE 2019, pp. 443\u2013454 (2019)","DOI":"10.1145\/3338906.3338909"},{"issue":"2","key":"19_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0304-3975(92)90339-H","volume":"96","author":"VK Garg","year":"1992","unstructured":"Garg, V.K., Ragunath, M.: Concurrent regular expressions and their relationship to Petri nets. Theoret. Comput. Sci. 96(2), 285\u2013304 (1992)","journal-title":"Theoret. Comput. Sci."},{"issue":"31\u201333","key":"19_CR10","doi-asserted-by":"publisher","first-page":"2987","DOI":"10.1016\/j.tcs.2010.04.036","volume":"411","author":"W Gelade","year":"2010","unstructured":"Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. Theoret. Comput. Sci. 411(31\u201333), 2987\u20132998 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-03816-7_32","volume-title":"Mathematical Foundations of Computer Science 2009","author":"W Gelade","year":"2009","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: weak versus strong determinism. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 369\u2013381. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03816-7_32"},{"issue":"5","key":"19_CR12","doi-asserted-by":"publisher","first-page":"2021","DOI":"10.1137\/070697367","volume":"38","author":"W Gelade","year":"2009","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: Numerical constraints and interleaving. SIAM J. Comput. 38(5), 2021\u20132043 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Ghelli, G., Colazzo, D., Sartiani, C.: Linear time membership in a class of regular expressions with interleaving and counting. In: CIKM 2008, pp. 389\u2013398 (2008)","DOI":"10.1145\/1458082.1458135"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-28332-1_27","volume-title":"Language and Automata Theory and Applications","author":"D Hovland","year":"2012","unstructured":"Hovland, D.: The membership problem for regular expressions with unordered concatenation and numerical constraints. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 313\u2013324. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28332-1_27"},{"issue":"1","key":"19_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","volume":"40","author":"T Jiang","year":"1991","unstructured":"Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Inf. Process. Lett. 40(1), 25\u201331 (1991)","journal-title":"Inf. Process. Lett."},{"key":"19_CR16","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: Regular expressions with numerical occurrence indicators-preliminary results. In: SPLST 2003, pp. 163\u2013173 (2003)"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Li, Y., Chu, X., Mou, X., Dong, C., Chen, H.: Practical study of deterministic regular expressions from large-scale XML and schema data. In: IDEAS 2018, pp. 45\u201353 (2018)","DOI":"10.1145\/3216122.3216126"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-030-05090-0_26","volume-title":"Advanced Data Mining and Applications","author":"Y Li","year":"2018","unstructured":"Li, Y., Mou, X., Chen, H.: Learning concise relax ng schemas supporting interleaving from XML documents. In: Gan, G., Li, B., Li, X., Wang, S. (eds.) ADMA 2018. LNCS (LNAI), vol. 11323, pp. 303\u2013317. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-05090-0_26"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-319-24246-0_9","volume-title":"Frontiers of Combining Systems","author":"T Liang","year":"2015","unstructured":"Liang, T., Tsiskaridze, N., Reynolds, A., Tinelli, C., Barrett, C.: A decision procedure for regular membership and length constraints over unbounded strings. In: Lutz, C., Ranise, S. (eds.) FroCoS 2015. LNCS (LNAI), vol. 9322, pp. 135\u2013150. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24246-0_9"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/inco.1994.1098","volume":"115","author":"AJ Mayer","year":"1994","unstructured":"Mayer, A.J., Stockmeyer, L.J.: The complexity of word problems-this time with interleaving. Inf. Comput. 115(2), 293\u2013311 (1994)","journal-title":"Inf. Comput."},{"key":"19_CR21","unstructured":"Sperberg-McQueen, C., Thompson, H.: XML schema (2005). http:\/\/www.w3.org\/xml\/schema"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Stanford, C., Veanes, M., Bj\u00f8rner, N.S.: Symbolic Boolean derivatives for efficiently solving extended regular expression constraints. In: PLDI 2021, pp. 620\u2013635 (2021)","DOI":"10.1145\/3453483.3454066"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time (Preliminary Report). In: STOC 1973, pp.\u00a01\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.jcss.2016.11.010","volume":"104","author":"M Sulzmann","year":"2019","unstructured":"Sulzmann, M., Thiemann, P.: Derivatives and partial derivatives for regular shuffle expressions. J. Comput. Syst. Sci. 104, 323\u2013341 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Tekli, J., Chbeir, R., Traina, A.J.M., Jr., C.T., Fileto, R.: Approximate XML structure validation based on document-grammar tree similarity. Inf. Sci. 295, 258\u2013302 (2015)","DOI":"10.1016\/j.ins.2014.09.044"},{"issue":"3","key":"19_CR26","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.tcs.2007.03.030","volume":"380","author":"MH Ter Beek","year":"2007","unstructured":"Ter Beek, M.H., Kleijn, J.: Infinite unfair shuffles and associativity. Theoret. Comput. Sci. 380(3), 401\u2013410 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR27","unstructured":"Wang, X., Hong, Y., Chang, H., Langdale, G., Hu, J.: Hyperscan: a fast multi-pattern regex matcher for modern CPUs. In: NSDI 19, pp. 631\u2013648 (2019)"},{"key":"19_CR28","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/978-3-031-00123-9_41","volume-title":"DASFAA 2022","author":"X Wang","year":"2022","unstructured":"Wang, X.: Membership algorithm for single-occurrence regular expressions with shuffle and counting. In: Bhattacharya, A., et al. (eds.) DASFAA 2022. LNCS, vol. 13245, pp. 526\u2013542. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-00123-9_41"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, S., Gu, X., Chen, Y., Shen, B.: InfeRE: step-by-step regex generation via chain of inference. In: ASE 2023, pp. 1505\u20131515 (2023)","DOI":"10.1109\/ASE56229.2023.00111"},{"key":"19_CR30","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-319-93037-4_31","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"X Zhang","year":"2018","unstructured":"Zhang, X., Li, Y., Cui, F., Dong, C., Chen, H.: Inference of a concise regular expression considering interleaving from XML documents. In: Phung, D., Tseng, V.S., Webb, G.I., Ho, B., Ganji, M., Rashidi, L. (eds.) PAKDD 2018. LNCS (LNAI), vol. 10938, pp. 389\u2013401. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93037-4_31"},{"issue":"2\u20133","key":"19_CR31","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10703-016-0263-6","volume":"50","author":"Y Zheng","year":"2017","unstructured":"Zheng, Y., et al.: Z3str2: an efficient solver for strings, regular expressions, and length constraints. Formal Methods Syst. Des. 50(2\u20133), 249\u2013288 (2017)","journal-title":"Formal Methods Syst. Des."}],"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-96-0602-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,24]],"date-time":"2024-11-24T04:20:28Z","timestamp":1732422028000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-0602-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,25]]},"ISBN":["9789819606016","9789819606023"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-0602-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,25]]},"assertion":[{"value":"25 November 2024","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":"Hong Kong","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":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 November 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 November 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"setta2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/setta2024.cs.cityu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}