{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:29Z","timestamp":1750309169481,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":17,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,10,26]],"date-time":"2008-10-26T00:00:00Z","timestamp":1224979200000},"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":[],"published-print":{"date-parts":[[2008,10,26]]},"DOI":"10.1145\/1458082.1458135","type":"proceedings-article","created":{"date-parts":[[2008,11,11]],"date-time":"2008-11-11T12:59:40Z","timestamp":1226408380000},"page":"389-398","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Linear time membership in a class of regular expressions with interleaving and counting"],"prefix":"10.1145","author":[{"given":"Giorgio","family":"Ghelli","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dario","family":"Colazzo","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Sud, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Sartiani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10,26]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"http:\/\/xerces.apache.org\/.  http:\/\/xerces.apache.org\/."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841920_8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978093"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017095"},{"key":"e_1_3_2_1_5_1","first-page":"115","volume-title":"VLDB","author":"Bex G. J.","year":"2006","unstructured":"G. J. Bex , F. Neven , T. Schwentick , and K. Tuyls . Inference of concise DTDs from XML data . In VLDB , pages 115 -- 126 , 2006 . G. J. Bex, F. Neven, T. Schwentick, and K. Tuyls. Inference of concise DTDs from XML data. In VLDB, pages 115--126, 2006."},{"key":"e_1_3_2_1_6_1","first-page":"998","volume-title":"VLDB","author":"Bex G. J.","year":"2007","unstructured":"G. J. Bex , F. Neven , and S. Vansummeren . Inferring XML schema definitions from XML data . In VLDB , pages 998 -- 1009 , 2007 . G. J. Bex, F. Neven, and S. Vansummeren. Inferring XML schema definitions from XML data. In VLDB, pages 998--1009, 2007."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_1_8_1","first-page":"43","volume-title":"WebDB","author":"Choi B.","year":"2002","unstructured":"B. Choi . What are real DTDs like ? In WebDB , pages 43 -- 48 , 2002 . B. Choi. What are real DTDs like? In WebDB, pages 43--48, 2002."},{"key":"e_1_3_2_1_9_1","volume-title":"ICDT","author":"Gelade W.","year":"2007","unstructured":"W. Gelade , W. Martens , and F. Neven . Optimizing schema languages for XML: Numerical constraints and interleaving . In ICDT , 2007 . W. Gelade, W. Martens, and F. Neven. Optimizing schema languages for XML: Numerical constraints and interleaving. In ICDT, 2007."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783534.1783557"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_3_2_1_12_1","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman . Introduction to Automata Theory, Languages and Computation . Addison-Wesley , 1979 . J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"e_1_3_2_1_14_1","series-title":"LNCS","first-page":"17","volume-title":"XSym","author":"Montazerian M.","year":"2007","unstructured":"M. Montazerian , P. T. Wood , and S. R. Mousavi . XPath query satisfiability is in PTIME for real-world DTDs . In XSym , volume 4704 of LNCS , pages 17 -- 30 . Springer , 2007 . M. Montazerian, P. T. Wood, and S. R. Mousavi. XPath query satisfiability is in PTIME for real-world DTDs. In XSym, volume 4704 of LNCS, pages 17--30. Springer, 2007."},{"key":"e_1_3_2_1_15_1","volume-title":"Centrum voor Wiskunde en Informatica","author":"Schmidt A.","year":"2001","unstructured":"A. Schmidt , F. Waas , M. Kersten , D. Florescu , I. Manolescu , M. J. Carey , and R. Busse . The XML Benchmark Project. Technical report , Centrum voor Wiskunde en Informatica , April 2001 . A. Schmidt, F. Waas, M. Kersten, D. Florescu, I. Manolescu, M. J. Carey, and R. Busse. The XML Benchmark Project. Technical report, Centrum voor Wiskunde en Informatica, April 2001."},{"key":"e_1_3_2_1_16_1","volume-title":"XML Schema Part 1: Structures","author":"Thompson H. S.","year":"2004","unstructured":"H. S. Thompson , D. Beech , M. Maloney , and N. Mendelsohn . XML Schema Part 1: Structures Second Edition. Technical report, World Wide Web Consortium , Oct 2004 . W3C Recommendation. H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1: Structures Second Edition. Technical report, World Wide Web Consortium, Oct 2004. W3C Recommendation."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"}],"event":{"name":"CIKM08: Conference on Information and Knowledge Management","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","ACM Association for Computing Machinery","SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Napa Valley California USA","acronym":"CIKM08"},"container-title":["Proceedings of the 17th ACM conference on Information and knowledge management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1458082.1458135","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1458082.1458135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:44Z","timestamp":1750287224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1458082.1458135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,26]]},"references-count":17,"alternative-id":["10.1145\/1458082.1458135","10.1145\/1458082"],"URL":"https:\/\/doi.org\/10.1145\/1458082.1458135","relation":{},"subject":[],"published":{"date-parts":[[2008,10,26]]},"assertion":[{"value":"2008-10-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}