{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T17:56:53Z","timestamp":1772733413534,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,11,13]],"date-time":"2017-11-13T00:00:00Z","timestamp":1510531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            Regular Expressions (REs) are ubiquitous in database and programming languages. While many applications make use of REs extended with\n            <jats:italic>interleaving<\/jats:italic>\n            (\n            <jats:italic>shuffle<\/jats:italic>\n            ) and\n            <jats:italic>unordered concatenation<\/jats:italic>\n            operators, this extension badly affects the complexity of basic operations, and, especially, makes\n            <jats:italic>membership<\/jats:italic>\n            NP-hard, which is unacceptable in most practical scenarios.\n          <\/jats:p>\n          <jats:p>\n            In this article, we study the problem of membership checking for a restricted class of these extended REs, called\n            <jats:italic>conflict-free REs<\/jats:italic>\n            , which are expressive enough to cover the vast majority of real-world applications. We present several polynomial algorithms for membership checking over conflict-free REs. The algorithms are all polynomial and differ in terms of adopted optimization techniques and in the kind of supported operators. As a particular application, we generalize the approach to check membership of Extensible Markup Language trees into a class of EDTDs (Extended Document Type Definitions) that models the crucial aspects of DTDs (Document Type Definitions) and XSD (XML Schema Definitions) schemas.\n          <\/jats:p>\n          <jats:p>Results about an extensive experimental analysis validate the efficiency of the presented membership checking techniques.<\/jats:p>","DOI":"10.1145\/3132701","type":"journal-article","created":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T14:02:44Z","timestamp":1510668164000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Linear Time Membership in a Class of Regular Expressions with Counting, Interleaving, and Unordered Concatenation"],"prefix":"10.1145","volume":"42","author":[{"given":"Dario","family":"Colazzo","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Dauphine - PSL Research University - CNRS, France, Paris"}]},{"given":"Giorgio","family":"Ghelli","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Italy"}]},{"given":"Carlo","family":"Sartiani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Basilicata, Italy"}]}],"member":"320","published-online":{"date-parts":[[2017,11,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.10.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042050"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841920_8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2004.1320036"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Conference on Very Large Data Bases (VLDB\u201907)","author":"Bex Geert Jan","year":"2007","unstructured":"Geert Jan Bex , Frank Neven , and Stijn Vansummeren . 2007 . Inferring XML schema definitions from XML data . In Proceedings of the Conference on Very Large Data Bases (VLDB\u201907) . 998--1009. Geert Jan Bex, Frank Neven, and Stijn Vansummeren. 2007. Inferring XML schema definitions from XML data. In Proceedings of the Conference on Very Large Data Bases (VLDB\u201907). 998--1009."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806434"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 16th International Workshop on the Web and Databases 2013 (WebDB\u201913)","author":"Boneva Iovka","year":"2013","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\u201913) . 13--18. 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\u201913). 13--18."},{"key":"e_1_2_1_10_1","volume-title":"Extensible Markup Language (XML) 1.1","author":"Bray Tim","unstructured":"Tim Bray , Jean Paoli , C. M. Sperberg-McQueen , Eve Maler , Fran\u00e7ois Yergeau , and John Cowan . 2006. Extensible Markup Language (XML) 1.1 ( 2 nd ed.). Technical Report. World Wide Web Consortium . W3C Recommendation. Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, Eve Maler, Fran\u00e7ois Yergeau, and John Cowan. 2006. Extensible Markup Language (XML) 1.1 (2nd ed.). Technical Report. World Wide Web Consortium. W3C Recommendation.","edition":"2"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 1st Annual European Symposium on Algorithms (ESA\u201993)","author":"Br\u00fcggemann-Klein Anne","year":"1993","unstructured":"Anne Br\u00fcggemann-Klein . 1993. Unambiguity of extended regular expressions in SGML document grammars . In Proceedings of the 1st Annual European Symposium on Algorithms (ESA\u201993) , Bad Honnef , Germany, September 30--October 2, 1993 (Lecture Notes in Computer Science), Vol. 726 . Springer , 73--84. Anne Br\u00fcggemann-Klein. 1993. Unambiguity of extended regular expressions in SGML document grammars. In Proceedings of the 1st Annual European Symposium on Algorithms (ESA\u201993), Bad Honnef, Germany, September 30--October 2, 1993 (Lecture Notes in Computer Science), Vol. 726. Springer, 73--84."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55210-3_182"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Workshop on Web and Databases (WebDB\u201902)","author":"Choi Byron","year":"2002","unstructured":"Byron Choi . 2002 . What are real DTDs like? In Proceedings of the International Workshop on Web and Databases (WebDB\u201902) . 43--48. Byron Choi. 2002. What are real DTDs like? In Proceedings of the International Workshop on Web and Databases (WebDB\u201902). 43--48."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1645973"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508020.2508022"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.023"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514916"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.10.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44881-0_18"},{"key":"e_1_2_1_22_1","volume-title":"Fallside and Priscilla Walmsley","author":"David","year":"2004","unstructured":"David C. Fallside and Priscilla Walmsley . 2004 . XML Schema Part 0: Primer, 2 nd ed. (Oct. 2004). W3C Recommendation . David C. Fallside and Priscilla Walmsley. 2004. XML Schema Part 0: Primer, 2nd ed. (Oct. 2004). W3C Recommendation.","edition":"2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814196"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697367"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75987-4_16"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458135"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_28_1","volume-title":"SGML Handbook","author":"Goldfarb Charles F.","unstructured":"Charles F. Goldfarb . 1990. SGML Handbook . Clarendon Press . Charles F. Goldfarb. 1990. SGML Handbook. Clarendon Press."},{"key":"e_1_2_1_29_1","volume-title":"Technical Report","author":"Harris Steve","unstructured":"Steve Harris and Andy Seaborne . 2013. SPARQL 1.1 Query Language . Technical Report . World Wide Web Consortium . W3C Recommendation. Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. Technical Report. World Wide Web Consortium. W3C Recommendation."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1_27"},{"key":"e_1_2_1_31_1","unstructured":"J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley.  J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST\u201903)","author":"Kilpel\u00e4inen Pekka","year":"2003","unstructured":"Pekka Kilpel\u00e4inen and Rauno Tuhkanen . 2003 . Regular expressions with numerical occurrence indicators - Preliminary results . In Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST\u201903) , Pekka Kilpel\u00e4inen and Niina P\u00e4ivinen (Eds.). University of Kuopio, Department of Computer Science, 163--173. Pekka Kilpel\u00e4inen and Rauno Tuhkanen. 2003. Regular expressions with numerical occurrence indicators - Preliminary results. In Proceedings of the 8th Symposium on Programming Languages and Software Tools (SPLST\u201903), Pekka Kilpel\u00e4inen and Niina P\u00e4ivinen (Eds.). University of Kuopio, Department of Computer Science, 163--173."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030397.1030441"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90021-5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"e_1_2_1_37_1","unstructured":"Anders M\u00f8ller. 2010. dk.brics.automaton\u2014Finite-State Automata and Regular Expressions for Java. Retrieved from http:\/\/www.brics.dk\/automaton\/.  Anders M\u00f8ller. 2010. dk.brics.automaton\u2014Finite-State Automata and Regular Expressions for Java. Retrieved from http:\/\/www.brics.dk\/automaton\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75288-2_3"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402958.1402983"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the Extreme Markup Languages 2005 Conference.","author":"Sperberg-McQueen C. M.","year":"2005","unstructured":"C. M. Sperberg-McQueen . 2005 . Applications of Brzozowski derivatives to XML schema processing . In Proceedings of the Extreme Markup Languages 2005 Conference. C. M. Sperberg-McQueen. 2005. Applications of Brzozowski derivatives to XML schema processing. In Proceedings of the Extreme Markup Languages 2005 Conference."},{"key":"e_1_2_1_43_1","volume-title":"XML Schema Part 1: Structures","author":"Thompson Henry S.","unstructured":"Henry S. Thompson , David Beech , Murray Maloney , and Noah Mendelsohn . 2004. XML Schema Part 1: Structures , 2 nd ed. Technical Report. World Wide Web Consortium . W3C Recommendation. Henry S. Thompson, David Beech, Murray Maloney, and Noah Mendelsohn. 2004. XML Schema Part 1: Structures, 2nd ed. Technical Report. World Wide Web Consortium. W3C Recommendation.","edition":"2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90018-7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_20"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3132701","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3132701","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:10:56Z","timestamp":1750212656000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3132701"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,13]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3132701"],"URL":"https:\/\/doi.org\/10.1145\/3132701","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,13]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}