{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:00:09Z","timestamp":1740142809570,"version":"3.37.3"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2018,11,8]],"date-time":"2018-11-08T00:00:00Z","timestamp":1541635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472405","61502308","61872339"],"award-info":[{"award-number":["61472405","61502308","61872339"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University"},{"name":"SZU R\/D Fund and Natural Science Foundation of SZU","award":["827-000200"],"award-info":[{"award-number":["827-000200"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Deterministic regular expressions are a core part of XML Schema and used in other applications. But unlike regular expressions, deterministic regular expressions do not have a simple syntax, instead they are defined in a semantic manner. Moreover, not every regular expression can be rewritten to an equivalent deterministic regular expression. These properties of deterministic regular expressions put a burden on the user to develop XML Schema Definitions and to use deterministic regular expressions. In this paper, we propose a syntax for deterministic standard regular expressions (DREGs), and prove that the syntax of DREGs is context-free. Based on the context-free grammars for DREGs, we further design a generator for DREGs, which can generate DREGs randomly, and be used in applications associated with DREGs, e.g. benchmarking a validator for DTD or XML Schema, and inclusion checking of DTD and XML Schema. Experimental results demonstrate the efficiency and usefulness of the generator.<\/jats:p>","DOI":"10.1093\/comjnl\/bxy110","type":"journal-article","created":{"date-parts":[[2018,10,5]],"date-time":"2018-10-05T07:30:38Z","timestamp":1538724638000},"page":"1322-1341","source":"Crossref","is-referenced-by-count":0,"title":["Towards an Effective Syntax and a Generator for Deterministic Standard Regular Expressions"],"prefix":"10.1093","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-440X","authenticated-orcid":false,"given":"Zhiwu","family":"Xu","sequence":"first","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Lu","sequence":"additional","affiliation":[{"name":"Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,11,8]]},"reference":[{"year":"2006","key":"2019101410285334900_bxy110C1"},{"year":"2005","key":"2019101410285334900_bxy110C2"},{"key":"2019101410285334900_bxy110C3","doi-asserted-by":"crossref","first-page":"24:1","DOI":"10.1145\/2494529","article-title":"The complexity of regular expressions and property paths in SPARQL","volume":"38","author":"Losemann","year":"2013","journal-title":"ACM Trans. Database Syst."},{"year":"2015","author":"Huang","key":"2019101410285334900_bxy110C4"},{"key":"2019101410285334900_bxy110C5","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":"Theor. Comput. Sci."},{"key":"2019101410285334900_bxy110C6","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/inco.1997.2695","article-title":"One-unambiguous regular languages","volume":"142","author":"Br\u00fcggemann-Klein","year":"1998","journal-title":"Inf. Comput."},{"key":"2019101410285334900_bxy110C7","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1137\/100814196","article-title":"Regular expressions with counting: weak versus strong determinism","volume":"41","author":"Gelade","year":"2012","journal-title":"SIAM J. Comput."},{"year":"2004","author":"Sperberg-McQueen","key":"2019101410285334900_bxy110C8"},{"year":"2011","author":"Chen","key":"2019101410285334900_bxy110C9"},{"key":"2019101410285334900_bxy110C10","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.ic.2014.12.001","article-title":"Checking determinism of regular expressions with counting","volume":"241","author":"Chen","year":"2015","journal-title":"Inf. Comput."},{"key":"2019101410285334900_bxy110C11","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2016.02.027","article-title":"Closure properties and descriptional complexity of deterministic regular expressions","volume":"627","author":"Losemann","year":"2016","journal-title":"Theor. Comput. Sci."},{"year":"2009","author":"Bex","key":"2019101410285334900_bxy110C12"},{"key":"2019101410285334900_bxy110C13","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/j.jcss.2017.05.013","article-title":"Efficient testing and matching of deterministic regular expressions","volume":"89","author":"Groz","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"2019101410285334900_bxy110C14","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.ic.2015.08.005","article-title":"Deciding determinism of unary languages","volume":"245","author":"Lu","year":"2015","journal-title":"Inf. Comput."},{"key":"2019101410285334900_bxy110C15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00224-014-9576-2","article-title":"Deciding determinism of regular languages","volume":"57","author":"Lu","year":"2015","journal-title":"Theory Comput. Syst."},{"year":"2015","author":"Latte","key":"2019101410285334900_bxy110C16"},{"key":"2019101410285334900_bxy110C17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jcss.2017.03.011","article-title":"Deciding definability by deterministic regular expressions","volume":"88","author":"Czerwinski","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"year":"2015","author":"Peng","key":"2019101410285334900_bxy110C18"},{"year":"1996","author":"Ahonen","key":"2019101410285334900_bxy110C19"},{"year":"2006","author":"Bex","key":"2019101410285334900_bxy110C20"},{"year":"2007","author":"Bex","key":"2019101410285334900_bxy110C21"},{"key":"2019101410285334900_bxy110C22","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1841909.1841911","article-title":"Learning deterministic regular expressions for the inference of schemas from XMLdata","volume":"4","author":"Bex","year":"2010","journal-title":"ACM Trans. Web"},{"key":"2019101410285334900_bxy110C23","doi-asserted-by":"crossref","first-page":"1114","DOI":"10.1007\/s00224-014-9559-3","article-title":"Fast learning of restricted regular expressions and DTDs","volume":"57","author":"Freydenberger","year":"2015","journal-title":"Theory Comput. Syst."},{"key":"2019101410285334900_bxy110C24","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00224-012-9428-x","article-title":"Generating, sampling and counting subclasses of regular tree languages","volume":"52","author":"Antonopoulos","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"2019101410285334900_bxy110C25","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1016\/j.is.2010.10.001","article-title":"Checking determinism of XML Schema content models in optimal time","volume":"36","author":"Kilpel\u00e4inen","year":"2011","journal-title":"Inf. Syst."},{"key":"2019101410285334900_bxy110C26","first-page":"1","article-title":"Succinctness of the complement and intersection of regular expressions","volume":"13","author":"Gelade","year":"2012","journal-title":"ACM Trans. Comput. Logic"},{"key":"2019101410285334900_bxy110C27","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1147\/sj.94.0242","article-title":"Automatic generation of test cases","volume":"9","author":"Hanford","year":"1970","journal-title":"IBM Syst. J."},{"key":"2019101410285334900_bxy110C28","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/357084.357091","article-title":"Uniform random generation of balanced parenthesis strings","volume":"2","author":"Arnold","year":"1980","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"2019101410285334900_bxy110C29","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1137\/0212044","article-title":"Uniform random generation of strings in a context-free language","volume":"12","author":"Hickey","year":"1983","journal-title":"SIAM J. Comput."},{"key":"2019101410285334900_bxy110C30","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(94)90033-7","article-title":"Generating words in a context-free language uniformly at random","volume":"49","author":"Mairson","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"2019101410285334900_bxy110C31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1006\/inco.1997.2621","article-title":"A quasi-polynomial-time algorithm for sampling words from a context-free language","volume":"134","author":"Gore","year":"1997","journal-title":"Inf. Comput."},{"year":"1997","author":"McKenzie","key":"2019101410285334900_bxy110C32"},{"year":"2000","author":"Denise","key":"2019101410285334900_bxy110C33"},{"key":"2019101410285334900_bxy110C34","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita:2001128","article-title":"Random generation for finitely ambiguous context-free languages","volume":"35","author":"Bertoni","year":"2001","journal-title":"RAIRO-Theor. Inf. Appl."},{"year":"2010","author":"Gardy","key":"2019101410285334900_bxy110C35"},{"key":"2019101410285334900_bxy110C36","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.tcs.2013.01.006","article-title":"Non-redundant random generation algorithms for weighted context-free grammars","volume":"502","author":"Lorenz","year":"2013","journal-title":"Theor. Comput. Sci."},{"year":"2011","author":"H\u00e9am","key":"2019101410285334900_bxy110C37"},{"key":"2019101410285334900_bxy110C38","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1007\/s11432-009-0132-7","article-title":"Linear algorithm for lexicographic enumeration of CFG parse trees","volume":"52","author":"Dong","year":"2009","journal-title":"Science in China (Series F\u2014Information Science)"},{"year":"2010","author":"Xu","key":"2019101410285334900_bxy110C39"},{"key":"2019101410285334900_bxy110C40","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/BF01932308","article-title":"A sentence generator for testing parsers","volume":"12","author":"Purdom","year":"1972","journal-title":"BIT Numer. Math."},{"key":"2019101410285334900_bxy110C41","first-page":"96","article-title":"Sentence generation based on context-dependent rule coverage","volume":"41","author":"Shen","year":"2005","journal-title":"Comput. Eng. Appl."},{"year":"2009","author":"Zheng","key":"2019101410285334900_bxy110C42"},{"key":"2019101410285334900_bxy110C43","first-page":"55","article-title":"On lexicographic enumeration of regular and context-free languages","volume":"13","author":"M\u00e4kinen","year":"1997","journal-title":"Acta Cybern."},{"key":"2019101410285334900_bxy110C44","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"2007","edition":"3rd edn"},{"year":"2008","author":"Chen","key":"2019101410285334900_bxy110C45"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/9\/1322\/30143449\/bxy110.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/9\/1322\/30143449\/bxy110.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,14]],"date-time":"2019-10-14T11:17:18Z","timestamp":1571051838000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/62\/9\/1322\/5165111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,8]]},"references-count":45,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,11,8]]},"published-print":{"date-parts":[[2019,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxy110","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2019,9]]},"published":{"date-parts":[[2018,11,8]]}}}