{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T10:19:31Z","timestamp":1780827571651,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7-ICT-233599"],"award-info":[{"award-number":["FP7-ICT-233599"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We study the succinctness of the complement and intersection of regular expressions. In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, cannot be avoided. All mentioned lower bounds improve the existing ones by one exponential and are tight in the sense that the target expression can be constructed in the corresponding time class, that is, exponential or double exponential time. As a by-product, we generalize a theorem by Ehrenfeucht and Zeiger stating that there is a class of DFAs which are exponentially more succinct than regular expressions, to a fixed alphabet. When the given regular expressions are one-unambiguous, as for instance required by the XML Schema specification, the complement can be computed in polynomial time whereas the bounds concerning intersection continue to hold. For the subclass of single-occurrence regular expressions, we prove a tight exponential lower bound for intersection.<\/jats:p>","DOI":"10.1145\/2071368.2071372","type":"journal-article","created":{"date-parts":[[2012,1,31]],"date-time":"2012-01-31T14:49:20Z","timestamp":1328021360000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Succinctness of the Complement and Intersection of Regular Expressions"],"prefix":"10.1145","volume":"13","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley."},{"key":"e_1_2_1_2_1","unstructured":"Bray T. Paoli J. Sperberg-McQueen C. Maler E. and Yergeau F. 2004. Extensible Markup Language (XML). Tech. rep. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/REC-xml\/. Bray T. Paoli J. Sperberg-McQueen C. Maler E. and Yergeau F. 2004. Extensible Markup Language (XML). Tech. rep. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/REC-xml\/."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907)","author":"Bex G. J.","unstructured":"Bex , G. J. , Neven , F. , and Vansummeren , S . 2007. Inferring XML schema definitions from XML data . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907) . ACM, 998--1009. Bex, G. J., Neven, F., and Vansummeren, S. 2007. Inferring XML schema definitions from XML data. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB\u201907). ACM, 998--1009."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735890"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223204"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"e_1_2_1_8_1","unstructured":"Dang Z. R. 1973. On the complexity of a finite automaton corresponding to a generalized regular expression. Dokl. Akad. Nauk SSSR. Dang Z. R. 1973. On the complexity of a finite automaton corresponding to a generalized regular expression. Dokl. Akad. Nauk SSSR ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"key":"e_1_2_1_10_1","first-page":"407","article-title":"Regular expressions: New results and open problems","volume":"10","author":"Ellul K.","year":"2005","unstructured":"Ellul , K. , Krawetz , B. , Shallit , J. , and Wang , M. 2005 . Regular expressions: New results and open problems . J. Autom. Lang. Combin. 10 , 4, 407 -- 437 . Ellul, K., Krawetz, B., Shallit, J., and Wang, M. 2005. Regular expressions: New results and open problems. J. Autom. Lang. Combin. 10, 4, 407--437.","journal-title":"J. Autom. Lang. Combin."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682559"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gelade W.\n     and \n      Neven F\n  . \n  2007\n  . Succinctness of pattern-based schema languages for xml. In Proceedings of the International Conference on Database Programming Languages. M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. \n  4797 Springer 201--215. Gelade W. and Neven F. 2007. Succinctness of pattern-based schema languages for xml. In Proceedings of the International Conference on Database Programming Languages . M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. 4797 Springer 201--215.","DOI":"10.1007\/978-3-540-75987-4_14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.036"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697367"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ghelli G. Colazzo D. and \n      Sartiani C\n  . \n  2007\n  . Efficient inclusion for a class of xml types with interleaving and counting. In Proceedings of the International Conference on Database Programming Languages. M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. \n  4797 Springer 231--245. Ghelli G. Colazzo D. and Sartiani C. 2007. Efficient inclusion for a class of xml types with interleaving and counting. In Proceedings of the International Conference on Database Programming Languages . M. Arenas and M. I. Schwartzbach Eds. Lecture Notes in Computer Science vol. 4797 Springer 231--245.","DOI":"10.1007\/978-3-540-75987-4_16"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00119-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(1:6)2005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85780-8_30"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Gruber H.\n     and \n      Johannsen J\n  . \n  2008\n  . Optimal lower bounds on regular expression size using communication complexity. In Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS\u201908). R. M. Amadio Ed. Lecture Notes in Computer Science vol. \n  4962 Springer 273--286. Gruber H. and Johannsen J. 2008. Optimal lower bounds on regular expression size using communication complexity. In Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS\u201908) . R. M. Amadio Ed. Lecture Notes in Computer Science vol. 4962 Springer 273--286.","DOI":"10.1007\/978-3-540-78499-9_20"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1748"},{"key":"e_1_2_1_23_1","volume-title":"Department of Computer Science","author":"Hunt III, H. B.","unstructured":"Hunt III, H. B. 1973. The equivalence problem for regular expressions with intersection is not polynomial in tape. Tech. rep ., Department of Computer Science , Cornell University . Hunt III, H. B. 1973. The equivalence problem for regular expressions with intersection is not polynomial in tape. Tech. rep., Department of Computer Science, Cornell University."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ilie L.\n     and \n      Yu S\n  . \n  2002\n  . Algorithms for computing small NFAs. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201902). K. Diks and W. Rytter Eds. Lecture Notes in Computer Science vol. \n  2420 Springer 328--340. Ilie L. and Yu S. 2002. Algorithms for computing small NFAs. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201902) . K. Diks and W. Rytter Eds. Lecture Notes in Computer Science vol. 2420 Springer 328--340.","DOI":"10.1007\/3-540-45687-2_27"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(05)80006-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645731.668360"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/080743457"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/128749.128755"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/647852.737555"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.696168"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90073-5"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 10th International Conference on Foundations of Software Science and Computational Structures (FOSSACS\u201907)","volume":"4423","author":"Rosu G.","year":"2007","unstructured":"Rosu , G. 2007 . An effective algorithm for the membership problem for extended regular expressions . In Proceedings of the 10th International Conference on Foundations of Software Science and Computational Structures (FOSSACS\u201907) . H. Seidl Ed., Lecture Notes in Computer Science , vol. 4423 , Springer, 332--345. Rosu, G. 2007. An effective algorithm for the membership problem for extended regular expressions. In Proceedings of the 10th International Conference on Foundations of Software Science and Computational Structures (FOSSACS\u201907). H. Seidl Ed., Lecture Notes in Computer Science, vol. 4423, Springer, 332--345."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Rosu G.\n     and \n      Viswanathan M\n  . \n  2003\n  . Testing extended regular language membership incrementally by rewriting. In Proceedings of the 14th International Conference on Rewriting Techniques and Applications (RTA\u201903). R. Nieuwenhuis Ed. Lecture Notes in Computer Science vol. \n  2706 Springer 499--514. Rosu G. and Viswanathan M. 2003. Testing extended regular language membership incrementally by rewriting. In Proceedings of the 14th International Conference on Rewriting Techniques and Applications (RTA\u201903) . R. Nieuwenhuis Ed. Lecture Notes in Computer Science vol. 2706 Springer 499--514.","DOI":"10.1007\/3-540-44881-0_35"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.003"},{"key":"e_1_2_1_40_1","unstructured":"Sperberg-McQueen C. and Thompson H. 2005. XML Schema. http:\/\/www.w3.org\/XML\/Schema. Sperberg-McQueen C. and Thompson H. 2005. XML Schema. http:\/\/www.w3.org\/XML\/Schema."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.696315"},{"key":"e_1_2_1_43_1","unstructured":"Waizenegger V. 2000. Uber die Effizienz der Darstellung durch reguliire Ausdriicke und endliche Automaten. Diplomarbeit RWTH Aachen. Waizenegger V. 2000. Uber die Effizienz der Darstellung durch reguliire Ausdriicke und endliche Automaten. Diplomarbeit RWTH Aachen."},{"key":"e_1_2_1_44_1","volume-title":"Handbook of Formal Languages","author":"Yu S.","unstructured":"Yu , S. 1997. Regular languages . In Handbook of Formal Languages . G. Rozenberg and A. Salomaa Eds., Vol. 1 , Springer , Chapter 2, 41--110. Yu, S. 1997. Regular languages. In Handbook of Formal Languages. G. Rozenberg and A. Salomaa Eds., Vol. 1, Springer, Chapter 2, 41--110."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00028-X"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071368.2071372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071368.2071372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071368.2071372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071368.2071372"],"URL":"https:\/\/doi.org\/10.1145\/2071368.2071372","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}