{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T22:15:33Z","timestamp":1774044933988,"version":"3.50.1"},"reference-count":31,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100004826","name":"Beijing Natural Science Foundation","doi-asserted-by":"publisher","award":["F251021"],"award-info":[{"award-number":["F251021"]}],"id":[{"id":"10.13039\/501100004826","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004826","name":"Beijing Natural Science Foundation","doi-asserted-by":"publisher","award":["4232038"],"award-info":[{"award-number":["4232038"]}],"id":[{"id":"10.13039\/501100004826","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372439"],"award-info":[{"award-number":["62372439"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872339"],"award-info":[{"award-number":["61872339"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Systems Architecture"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.sysarc.2026.103759","type":"journal-article","created":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T00:45:54Z","timestamp":1772671554000},"page":"103759","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Derivative-based algorithms for membership,\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" altimg=\"si5.svg\" display=\"inline\" id=\"d1e2250\">\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:math>\n                    -non-emptiness, and\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" altimg=\"si5.svg\" display=\"inline\" id=\"d1e2255\">\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:math>\n                    -non-empty complement problems in enhanced regular expressions"],"prefix":"10.1016","volume":"175","author":[{"given":"Mengxi","family":"Wang","sequence":"first","affiliation":[]},{"given":"Chunmei","family":"Dong","sequence":"additional","affiliation":[]},{"given":"Weihao","family":"Su","sequence":"additional","affiliation":[]},{"given":"Chengyao","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.sysarc.2026.103759_b1","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0304-3975(92)90339-H","article-title":"Concurrent regular expressions and their relationship to Petri nets","volume":"96","author":"Garg","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.sysarc.2026.103759_b2","series-title":"ASE 2023","first-page":"1505","article-title":"InfeRE: Step-by-step regex generation via chain of inference","author":"Zhang","year":"2023"},{"key":"10.1016\/j.sysarc.2026.103759_b3","series-title":"NSDI 19","first-page":"631","article-title":"Hyperscan: A fast multi-pattern regex matcher for modern CPUs","author":"Wang","year":"2019"},{"issue":"2","key":"10.1016\/j.sysarc.2026.103759_b4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3651601","article-title":"Distinct shortest walk enumeration for RPQs","volume":"2","author":"David","year":"2024","journal-title":"Proc. ACM Manag. Data"},{"key":"10.1016\/j.sysarc.2026.103759_b5","series-title":"ESEC\/FSE 2019","first-page":"443","article-title":"Why aren\u2019t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions","author":"Davis","year":"2019"},{"key":"10.1016\/j.sysarc.2026.103759_b6","series-title":"PLDI 2021","first-page":"620","article-title":"Symbolic boolean derivatives for efficiently solving extended regular expression constraints","author":"Stanford","year":"2021"},{"issue":"31\u201333","key":"10.1016\/j.sysarc.2026.103759_b7","doi-asserted-by":"crossref","first-page":"2987","DOI":"10.1016\/j.tcs.2010.04.036","article-title":"Succinctness of regular expressions with interleaving, intersection and counting","volume":"411","author":"Gelade","year":"2010","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"10.1016\/j.sysarc.2026.103759_b8","doi-asserted-by":"crossref","first-page":"2021","DOI":"10.1137\/070697367","article-title":"Optimizing schema languages for XML: Numerical constraints and interleaving","volume":"38","author":"Gelade","year":"2009","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.sysarc.2026.103759_b9","series-title":"STOC 1973","first-page":"1","article-title":"Word problems requiring exponential time (preliminary report)","author":"Stockmeyer","year":"1973"},{"key":"10.1016\/j.sysarc.2026.103759_b10","series-title":"SPLST\u201903","first-page":"163","article-title":"Regular expressions with numerical occurrence indicators-preliminary results.","author":"Kilpel\u00e4inen","year":"2003"},{"issue":"2","key":"10.1016\/j.sysarc.2026.103759_b11","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1006\/inco.1994.1098","article-title":"The complexity of word problems-this time with interleaving","volume":"115","author":"Mayer","year":"1994","journal-title":"Inform. and Comput."},{"issue":"Part B","key":"10.1016\/j.sysarc.2026.103759_b12","article-title":"Location automata for regular expressions with shuffle and intersection","volume":"295","author":"Broda","year":"2023","journal-title":"Inform. and Comput."},{"issue":"1","key":"10.1016\/j.sysarc.2026.103759_b13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0020-0190(05)80006-7","article-title":"A note on the space complexity of some decision problems for finite automata","volume":"40","author":"Jiang","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.sysarc.2026.103759_b14","series-title":"LATA 2012","first-page":"313","article-title":"The membership problem for regular expressions with unordered concatenation and numerical constraints","author":"Hovland","year":"2012"},{"key":"10.1016\/j.sysarc.2026.103759_b15","series-title":"CIKM 2008","first-page":"389","article-title":"Linear time membership in a class of regular expressions with interleaving and counting","author":"Ghelli","year":"2008"},{"issue":"4","key":"10.1016\/j.sysarc.2026.103759_b16","doi-asserted-by":"crossref","first-page":"24:1","DOI":"10.1145\/3132701","article-title":"Linear time membership in a class of regular expressions with counting, interleaving, and unordered concatenation","volume":"42","author":"Colazzo","year":"2017","journal-title":"ACM Trans. Database Syst."},{"key":"10.1016\/j.sysarc.2026.103759_b17","series-title":"DASFAA 2022","first-page":"526","article-title":"Membership algorithm for single-occurrence regular expressions with shuffle and counting","author":"Wang","year":"2022"},{"issue":"4","key":"10.1016\/j.sysarc.2026.103759_b18","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/321239.321249","article-title":"Derivatives of regular expressions","volume":"11","author":"Brzozowski","year":"1964","journal-title":"J. ACM"},{"key":"10.1016\/j.sysarc.2026.103759_b19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.jcss.2016.11.010","article-title":"Derivatives and partial derivatives for regular shuffle expressions","volume":"104","author":"Sulzmann","year":"2019","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.sysarc.2026.103759_b20","series-title":"RELAX NG specification. OASIS, december 2001","author":"Clark","year":"2001"},{"key":"10.1016\/j.sysarc.2026.103759_b21","series-title":"XML schema","author":"Sperberg-McQueen","year":"2005"},{"key":"10.1016\/j.sysarc.2026.103759_b22","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.ins.2014.09.044","article-title":"Approximate XML structure validation based on document-grammar tree similarity","volume":"295","author":"Tekli","year":"2015","journal-title":"Inform. Sci."},{"key":"10.1016\/j.sysarc.2026.103759_b23","series-title":"MFCS 2009","first-page":"369","article-title":"Regular expressions with counting: Weak versus strong determinism","author":"Gelade","year":"2009"},{"issue":"3","key":"10.1016\/j.sysarc.2026.103759_b24","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/j.tcs.2007.03.030","article-title":"Infinite unfair shuffles and associativity","volume":"380","author":"Ter Beek","year":"2007","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/j.sysarc.2026.103759_b25","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","article-title":"Regular expressions into finite automata","volume":"120","author":"Br\u00fcggemann-Klein","year":"1993","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/j.sysarc.2026.103759_b26","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","article-title":"Learning regular sets from queries and counterexamples","volume":"75","author":"Angluin","year":"1987","journal-title":"Inform. and Comput."},{"issue":"2\u20133","key":"10.1016\/j.sysarc.2026.103759_b27","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s10703-016-0263-6","article-title":"Z3str2: an efficient solver for strings, regular expressions, and length constraints","volume":"50","author":"Zheng","year":"2017","journal-title":"Form. Methods Syst. Des."},{"key":"10.1016\/j.sysarc.2026.103759_b28","series-title":"FroCoS 2015","first-page":"135","article-title":"A decision procedure for regular membership and length constraints over unbounded strings","author":"Liang","year":"2015"},{"key":"10.1016\/j.sysarc.2026.103759_b29","series-title":"IDEAS \u201918","first-page":"45","article-title":"Practical study of deterministic regular expressions from large-scale XML and schema data","author":"Li","year":"2018"},{"key":"10.1016\/j.sysarc.2026.103759_b30","series-title":"PAKDD 2018","first-page":"389","article-title":"Inference of a concise regular expression considering interleaving from XML documents","author":"Zhang","year":"2018"},{"key":"10.1016\/j.sysarc.2026.103759_b31","series-title":"ADMA 2018","first-page":"303","article-title":"Learning concise relax NG schemas supporting interleaving from XML documents","author":"Li","year":"2018"}],"container-title":["Journal of Systems Architecture"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1383762126000779?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1383762126000779?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T20:33:31Z","timestamp":1774038811000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1383762126000779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":31,"alternative-id":["S1383762126000779"],"URL":"https:\/\/doi.org\/10.1016\/j.sysarc.2026.103759","relation":{},"ISSN":["1383-7621"],"issn-type":[{"value":"1383-7621","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Derivative-based algorithms for membership, -non-emptiness, and -non-empty complement problems in enhanced regular expressions","name":"articletitle","label":"Article Title"},{"value":"Journal of Systems Architecture","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.sysarc.2026.103759","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"103759"}}