{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:12Z","timestamp":1750221012009,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":44,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472405,61872339"],"award-info":[{"award-number":["61472405,61872339"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1145\/3331076.3331100","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T17:40:26Z","timestamp":1563558026000},"page":"1-10","source":"Crossref","is-referenced-by-count":1,"title":["An effective algorithm for learning single occurrence regular expressions with interleaving"],"prefix":"10.1145","author":[{"given":"Yeting","family":"Li","sequence":"first","affiliation":[{"name":"University of Chinese Academy of Sciences, Beijing, China"}]},{"given":"Haiming","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Software Chinese Academy of Sciences, Beijing, China"}]},{"given":"Xiaolan","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Chinese Academy of Sciences, Beijing, China"}]},{"given":"Lingqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing University of Technology, Beijing, China"}]}],"member":"320","reference":[{"key":"key-10.1145\/3331076.3331100-1","unstructured":"Serge Abiteboul, Pierre Bourhis, and Victor Vianu. 2015. Highly Expressive Query Languages for Unordered Data Trees. Theory Comput. Syst. 57, 4 (2015), 927--966."},{"key":"key-10.1145\/3331076.3331100-2","doi-asserted-by":"crossref","unstructured":"Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, and Carlo Sartiani. 2019. Parametric schema inference for massive JSON datasets. The VLDB Journal (Jan 2019).","DOI":"10.1007\/s00778-018-0532-7"},{"key":"key-10.1145\/3331076.3331100-3","unstructured":"Denilson Barbosa, Laurent Mignet, and Pierangelo Veltri. 2005. Studying the XML Web: Gathering Statistics from an XML Sample. World Wide Web 8, 4 (2005), 413--438."},{"key":"key-10.1145\/3331076.3331100-4","unstructured":"Martin Berglund, Henrik Björklund, and Johanna Björklund. 2013. Shuffled languages - Representation and recognition. Theor. Comput. Sci. 489--490 (2013), 1--20."},{"key":"key-10.1145\/3331076.3331100-5","unstructured":"Geert Jan Bex, Wouter Gelade, Frank Neven, and Stijn Vansummeren. 2010. Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data. TWEB 4, 4 (2010), 14:1--14:32."},{"key":"key-10.1145\/3331076.3331100-6","unstructured":"Geert Jan Bex, Frank Neven, and Jan Van den Bussche. 2004. DTDs versus XML Schema: A Practical Study. In Proceedings of the Seventh International Workshop on the Web and Databases, WebDB 2004, June 17-18, 2004, Maison de la Chimie, Paris, France, Colocated with ACM SIGMOD\/PODS 2004. 79--84."},{"key":"key-10.1145\/3331076.3331100-7","unstructured":"Geert Jan Bex, Frank Neven, Thomas Schwentick, and Karl Tuyls. 2006. Inference of Concise DTDs from XML Data. In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006. 115--126."},{"key":"key-10.1145\/3331076.3331100-8","unstructured":"Geert Jan Bex, Frank Neven, Thomas Schwentick, and Stijn Vansummeren. 2010. Inference of Concise Regular Expressions and DTDs. ACM Transactions on Database Systems 35, 2 (2010), 1--47."},{"key":"key-10.1145\/3331076.3331100-9","unstructured":"Geert Jan Bex, Frank Neven, and Stijn Vansummeren. 2007. Inferring XML Schema Definitions from XML Data. In Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007. 998--1009."},{"key":"key-10.1145\/3331076.3331100-10","unstructured":"Mikolaj Boja'nczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, and Claire David. 2006. Two-Variable Logic on Words with Data. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings. 7--16."},{"key":"key-10.1145\/3331076.3331100-11","unstructured":"Iovka Boneva, Radu Ciucanu, and Slawek Staworko. 2013. Simple Schemas for Unordered XML. In Proceedings of the 16th International Workshop on the Web and Databases 2013, WebDB 2013, New York, NY, USA, June 23, 2013. 13--18."},{"key":"key-10.1145\/3331076.3331100-12","unstructured":"R Boppana and M M Halldrsson. 1992. Approximating Maximum Independent Set by Excluding Subgraphs. Bit Numerical Mathematics 32, 2 (1992), 180--196."},{"key":"key-10.1145\/3331076.3331100-13","unstructured":"Radu Ciucanu and Slawek Staworko. 2013. Learning Schemas for Unordered XML. In Proceedings of the 14th International Symposium on Database Programming Languages (DBPL 2013), August 30, 2013, Riva del Garda, Trento, Italy."},{"key":"key-10.1145\/3331076.3331100-14","unstructured":"James Clark and MURATA Makoto. 2003. RELAX NG Tutorial. Retrieved February 28, 2018 from https:\/\/relaxng.org\/tutorial-20030326.html"},{"key":"key-10.1145\/3331076.3331100-15","unstructured":"Dario Colazzo, Giorgio Ghelli, and Carlo Sartiani. 2011. Schemas for safe and efficient XML processing. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany. 1378--1379."},{"key":"key-10.1145\/3331076.3331100-16","unstructured":"Xiaoqiang Feng, Lixiao Zheng, and Haiming Chen. 2014. Inference Algorithm for a Restricted Class of Regular Expressions. Vol. 41. Computer Science. 178--183 pages."},{"key":"key-10.1145\/3331076.3331100-17","unstructured":"Dominik D. Freydenberger and Timo Kötzing. 2015. Fast Learning of Restricted Regular Expressions and DTDs. Theory Comput. Syst. 57, 4 (2015), 1114--1158."},{"key":"key-10.1145\/3331076.3331100-18","unstructured":"Enrico Gallinucci, Matteo Golfarelli, and Stefano Rizzi. 2018. Schema profiling of document-oriented databases. Inf. Syst. 75 (2018), 13--25."},{"key":"key-10.1145\/3331076.3331100-19","unstructured":"Shudi Gao, Black Mesa C. M. Sperberg-McQueen, and Henry S. Thompson. 2012. W3C XML Schema Definition Language (XSD) 1.1 Part 1: Structures. Retrieved February 28, 2018 from https:\/\/www.w3.org\/TR\/xmlschema11-1\/"},{"key":"key-10.1145\/3331076.3331100-20","unstructured":"P. Garcia and E. Vidal. 2002. Inference of k-Testable Languages in the Strict Sense and Application to Syntactic Pattern Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 9 (2002), 920--925."},{"key":"key-10.1145\/3331076.3331100-21","unstructured":"Vijay K. Garg and M. T. Ragunath. 1992. Concurrent Regular Expressions and Their Relationship to Petri Nets. Theor. Comput. Sci. 96, 2 (1992), 285--304."},{"key":"key-10.1145\/3331076.3331100-22","unstructured":"Minos N. Garofalakis, Aristides Gionis, Rajeev Rastogi, S. Seshadri, and Kyuseok Shim. 2003. XTRACT: Learning Document Type Descriptors from XML Document Collections. Data Min. Knowl. Discov. 7, 1 (2003), 23--56."},{"key":"key-10.1145\/3331076.3331100-23","unstructured":"Jay L. Gischer. 1981. Shuffle Languages, Petri Nets, and Context-Sensitive Grammars. Commun. ACM 24, 9 (1981), 597--605."},{"key":"key-10.1145\/3331076.3331100-24","unstructured":"E. Mark Gold. 1967. Language Identification in the Limit. Information and Control 10, 5 (1967), 447--474."},{"key":"key-10.1145\/3331076.3331100-25","unstructured":"Steven Grijzenhout and Maarten Marx. 2013. The quality of the XML Web. J. Web Semant. 19 (2013), 59--68."},{"key":"key-10.1145\/3331076.3331100-26","unstructured":"Johanna Högberg and Lisa Kaati. 2010. Weighted unranked tree automata as a framework for plan recognition. In 13th Conference on Information Fusion, FUSION 2010, Edinburgh, UK, July 26-29, 2010. 1--8."},{"key":"key-10.1145\/3331076.3331100-27","unstructured":"Marco Kuhlmann and Giorgio Satta. 2009. Treebank Grammar Techniques for Non-Projective Dependency Parsing. In EACL 2009, 12th Conference of the European Chapter of the Association for Computational Linguistics, Proceedings of the Conference, Athens, Greece, March 30 - April 3, 2009. 478--486."},{"key":"#cr-split#-key-10.1145\/3331076.3331100-28.1","unstructured":"Yeting Li, Xinyu Chu, Xiaoying Mou, Chunmei Dong, and Haiming Chen. 2018. Practical Study of Deterministic Regular Expressions from Large-scale XML and Schema Data. In Proceedings of the 22nd International Database Engineering &#38"},{"key":"#cr-split#-key-10.1145\/3331076.3331100-28.2","unstructured":"Applications Symposium, IDEAS 2018, Villa San Giovanni, Italy, June 18-20, 2018. 45--53."},{"key":"key-10.1145\/3331076.3331100-29","unstructured":"Yeting Li, Chunmei Dong, Xinyu Chu, and Haiming Chen. 2019. Learning DMEs from Positive and Negative Examples. In Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Chiang Mai, Thailand, April 22-25, 2019, Proceedings. 434--438."},{"key":"key-10.1145\/3331076.3331100-30","unstructured":"Yeting Li, Xiaoying Mou, and Haiming Chen. 2018. Learning Concise Relax NG Schemas Supporting Interleaving from XML Documents. In Advanced Data Mining and Applications - 14th International Conference, ADMA 2018, Nanjing, China, November 16-18, 2018, Proceedings. 303--317."},{"key":"key-10.1145\/3331076.3331100-31","unstructured":"Yeting Li, Xiaolan Zhang, Feifei Peng, and Haiming Chen. 2016. Practical Study of Subclasses of Regular Expressions in DTD and XML Schema. In Web Technologies and Applications - 18th Asia-Pacific Web Conference, APWeb 2016, Suzhou, China, September 23-25, 2016. Proceedings, Part II. 368--382."},{"key":"key-10.1145\/3331076.3331100-32","unstructured":"Yeting Li, Xiaolan Zhang, Han Xu, Xiaoying Mou, and Haiming Chen. 2018. Learning Restricted Regular Expressions with Interleaving from XML Data. In Conceptual Modeling - 37th International Conference, ER 2018, Xi'an, China, October 22-25, 2018, Proceedings. 586--593."},{"key":"key-10.1145\/3331076.3331100-33","unstructured":"Zheng Li and Tingjian Ge. 2015. PIE: Approximate interleaving event matching over sequences. In 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015. 747--758."},{"key":"key-10.1145\/3331076.3331100-34","unstructured":"Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick. 2017. BonXai: Combining the Simplicity of DTD with the Expressiveness of XML Schema. ACM Trans. Database Syst. 42, 3 (2017), 15:1--15:42."},{"key":"key-10.1145\/3331076.3331100-35","unstructured":"Wim Martens, Frank Neven, and Thomas Schwentick. 2013. Complexity of Decision Problems for XML Schemas and Chain Regular Expressions. Siam Journal on Computing 39, 4 (2013), 1486--1530."},{"key":"key-10.1145\/3331076.3331100-36","unstructured":"Wim Martens, Frank Neven, Thomas Schwentick, and Geert Jan Bex. 2006. Expressiveness and complexity of XML Schema. ACM Trans. Database Syst. 31, 3 (2006), 770--813."},{"key":"key-10.1145\/3331076.3331100-37","unstructured":"Laurent Mignet, Denilson Barbosa, and Pierangelo Veltri. 2003. The XML web: a first study. In Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20-24, 2003. 500--510."},{"key":"key-10.1145\/3331076.3331100-38","unstructured":"Jun-Ki Min, Jae-Yong Ahn, and Chin-Wan Chung. 2003. Efficient extraction of schemas for XML documents. Inf. Process. Lett. 85, 1 (2003), 7--12."},{"key":"key-10.1145\/3331076.3331100-39","unstructured":"Joakim Nivre. 2009. Non-Projective Dependency Parsing in Expected Linear Time. In ACL 2009, Proceedings of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing of the AFNLP, 2-7 August 2009, Singapore. 351--359."},{"key":"key-10.1145\/3331076.3331100-40","unstructured":"Feifei Peng and Haiming Chen. 2015. Discovering Restricted Regular Expressions with Interleaving. In Web Technologies and Applications - 17th Asia-Pacific Web Conference, AP Web 2015, Guangzhou, China, September 18-20, 2015, Proceedings. 104--115."},{"key":"key-10.1145\/3331076.3331100-41","unstructured":"Arnaud Sahuguet. 2000. Everything You Ever Wanted to Know About DTDs, But Were Afraid to Ask (Extended Abstract). In The World Wide Web and Databases, Third International Workshop WebDB 2000, Dallas, Texas, USA, Maaay 18-19, 2000, Selected Papers. 171--183."},{"key":"key-10.1145\/3331076.3331100-42","unstructured":"Lanjun Wang, Oktie Hassanzadeh, Shuo Zhang, Juwei Shi, Limei Jiao, Jia Zou, and Chen Wang. 2015. Schema Management for Document Stores. PVLDB 8, 9 (2015), 922--933."},{"key":"key-10.1145\/3331076.3331100-43","unstructured":"Xiaolan Zhang, Yeting Li, Fanlin Cui, Chunmei Dong, and Haiming Chen. 2018. Inference of a Concise Regular Expression Considering Interleaving from XML Documents. In Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part II. 389--401."}],"event":{"name":"the 23rd International Database Applications & Engineering Symposium","start":{"date-parts":[[2019,6,10]]},"number":"23","location":"Athens, Greece","end":{"date-parts":[[2019,6,12]]},"acronym":"IDEAS '19"},"container-title":["Proceedings of the 23rd International Database Applications & Engineering Symposium on   - IDEAS '19"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331076.3331100","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3331100&ftid=2073422&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:06Z","timestamp":1750206366000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3331076.3331100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"references-count":44,"URL":"https:\/\/doi.org\/10.1145\/3331076.3331100","relation":{},"subject":[],"published":{"date-parts":[[2019]]}}}