{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:25Z","timestamp":1761611185845,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"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. Program. Lang. Syst."],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>Regular expression patterns provide a natural, declarative way to express constraints on semistructured data and to extract relevant information from it. Indeed, it is a core feature of the programming language Perl, surfaces in various UNIX tools such as sed and awk, and has recently been proposed in the context of the XML programming language XDuce. Since regular expressions can be ambiguous in general, different disambiguation policies have been proposed to get a unique matching strategy. We formally define the matching semantics under both (1) the POSIX, and (2) the first and longest match disambiguation strategies. We show that the generally accepted method of defining the longest match in terms of the first match and recursion does not conform to the natural notion of longest match. We continue by solving the type inference problem for both disambiguation strategies, which consists of calculating the set of all subparts of input values a subexpression can match under the given policy.<\/jats:p>","DOI":"10.1145\/1133651.1133652","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"389-428","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Type inference for unique pattern matching"],"prefix":"10.1145","volume":"28","author":[{"given":"Stijn","family":"Vansummeren","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/s007990050005","article-title":"The Lorel query language for semistructured data","volume":"1","author":"Abiteboul S.","year":"1997","unstructured":"Abiteboul , S. , Quass , D. , McHugh , J. , Widom , J. , and Wiener , J. L. 1997 . The Lorel query language for semistructured data . Int. J. Dig. Lib. 1 , 1, 68 -- 88 . Abiteboul, S., Quass, D., McHugh, J., Widom, J., and Wiener, J. L. 1997. The Lorel query language for semistructured data. Int. J. Dig. Lib. 1, 1, 68--88.","journal-title":"Int. J. Dig. Lib."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Baader F. and Nipkow T. 1998. Term Rewriting and All That Section 2.3. Cambridge University Press Cambridge U.K.   Baader F. and Nipkow T. 1998. Term Rewriting and All That Section 2.3. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9781139172752"},{"key":"e_1_2_1_3_1","unstructured":"Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2005. XQuery 1.0: An XML Query Language. W3C working draft. World Wide Web Consortium. Go online to www.w3.org.  Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2005. XQuery 1.0: An XML Query Language. W3C working draft. World Wide Web Consortium. Go online to www.w3.org."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1109\/T-C.1971.223204","article-title":"Ambiguity in graphs and expressions","volume":"20","author":"Book R.","year":"1971","unstructured":"Book , R. , Even , S. , Greibach , S. , and Ott , G. 1971 . Ambiguity in graphs and expressions . IEEE Trans. Comput. 20 , 2, 149 -- 153 . Book, R., Even, S., Greibach, S., and Ott, G. 1971. Ambiguity in graphs and expressions. IEEE Trans. Comput. 20, 2, 149--153.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_5_1","unstructured":"Br\u00fcggemann-Klein A. Murata M. and Wood D. 2001. Regular tree and regular hedge languages over unranked alphabets. Unpublished manuscript version 1.  Br\u00fcggemann-Klein A. Murata M. and Wood D. 2001. Regular tree and regular hedge languages over unranked alphabets. Unpublished manuscript version 1."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050084"},{"key":"e_1_2_1_7_1","unstructured":"Clark J. and Makoto M. 2001. RELAX NG Specification. Organization for the Advancement of Structured Information Standards. Go online to www.oasis-open.org.  Clark J. and Makoto M. 2001. RELAX NG Specification. Organization for the Advancement of Structured Information Standards. Go online to www.oasis-open.org."},{"key":"e_1_2_1_8_1","unstructured":"Davidson A. Fuchs M. Hedin M. Jain M. Koistinen J. Lloyd C. Maloney M. and Schwarzhof K. 1999. Schema for object-oriented XML 2.0. Tech. rep. Veo Systems Inc. (Now part of Perfect Commerce. Go online to www.perfect.com.)  Davidson A. Fuchs M. Hedin M. Jain M. Koistinen J. Lloyd C. Maloney M. and Schwarzhof K. 1999. Schema for object-oriented XML 2.0. Tech. rep. Veo Systems Inc. (Now part of Perfect Commerce. Go online to www.perfect.com.)"},{"key":"e_1_2_1_9_1","unstructured":"Dougherty D. and Robbins A. 1996. Sed and Awk. O'Reilly Sebastopol CA.   Dougherty D. and Robbins A. 1996. Sed and Awk. O'Reilly Sebastopol CA."},{"key":"e_1_2_1_10_1","volume-title":"CAV '98, Proceedings. Lecture Notes in Computer Science","volume":"1427","author":"Elgaard J.","unstructured":"Elgaard , J. , Klarlund , N. , and M\u00f8ller , A . 1998. Mona 1.x: New techniques for WS1S and WS2S. In Computer Aided Verification , CAV '98, Proceedings. Lecture Notes in Computer Science , vol. 1427 . Springer-Verlag, Berlin, Germany. Elgaard, J., Klarlund, N., and M\u00f8ller, A. 1998. Mona 1.x: New techniques for WS1S and WS2S. In Computer Aided Verification, CAV '98, Proceedings. Lecture Notes in Computer Science, vol. 1427. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_11_1","volume-title":"IFIP 18th World Computer Congress, TCS 3rd International Conference on Theoretical Computer Science. Kluwer","author":"Frisch A.","year":"2004","unstructured":"Frisch , A. 2004 . Regular tree language recognition with static information. In Exploring New Frontiers of Theoretical Informatics , IFIP 18th World Computer Congress, TCS 3rd International Conference on Theoretical Computer Science. Kluwer , Dordrecht, The Netherlands, 661--674. Frisch, A. 2004. Regular tree language recognition with static information. In Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TCS 3rd International Conference on Theoretical Computer Science. Kluwer, Dordrecht, The Netherlands, 661--674."},{"key":"e_1_2_1_12_1","volume-title":"Languages and Programming: ICALP 2004. Proceedings. Lecture Notes in Computer Science","volume":"3142","author":"Frisch A.","unstructured":"Frisch , A. and Cardelli , L . 2004. Greedy regular expression matching. In Automata , Languages and Programming: ICALP 2004. Proceedings. Lecture Notes in Computer Science , vol. 3142 . Springer-Verlag, Berlin, Germany, 618--629. Frisch, A. and Cardelli, L. 2004. Greedy regular expression matching. In Automata, Languages and Programming: ICALP 2004. Proceedings. Lecture Notes in Computer Science, vol. 3142. Springer-Verlag, Berlin, Germany, 618--629."},{"volume-title":"Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Frisch A.","key":"e_1_2_1_13_1","unstructured":"Frisch , A. , Castagna , G. , and Benzaken , V . 2002. Semantic subtyping . In Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 137--146. Frisch, A., Castagna, G., and Benzaken, V. 2002. Semantic subtyping. In Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 137--146."},{"volume-title":"Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press","author":"Frisch A.","key":"e_1_2_1_14_1","unstructured":"Frisch , A. , Castagna , G. , and Benzaken , V . 2003. &Copf;Duce: An XML-centric general-purpose language . In Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press , New York, NY, 51--63. 10.1145\/944705.944711 Frisch, A., Castagna, G., and Benzaken, V. 2003. &Copf;Duce: An XML-centric general-purpose language. In Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press, New York, NY, 51--63. 10.1145\/944705.944711"},{"key":"e_1_2_1_15_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.   Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA."},{"volume-title":"RIMS","author":"Hosoya H.","key":"e_1_2_1_17_1","unstructured":"Hosoya , H. 2003. Regular expression pattern matching---a simpler design. Tech. rep. 1397 , RIMS , Kyoto University , Kyoto, Japan . Hosoya, H. 2003. Regular expression pattern matching---a simpler design. Tech. rep. 1397, RIMS, Kyoto University, Kyoto, Japan."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004410"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053468.1053470"},{"volume-title":"Portable operating system interface (POSIX)","author":"Institute of Electrical and Electronic Engineers. 1992.","key":"e_1_2_1_21_1","unstructured":"Institute of Electrical and Electronic Engineers. 1992. Portable operating system interface (POSIX) . IEEE Std 1003.2. IEEE, Piscataway, NJ. Institute of Electrical and Electronic Engineers. 1992. Portable operating system interface (POSIX). IEEE Std 1003.2. IEEE, Piscataway, NJ."},{"key":"e_1_2_1_22_1","unstructured":"Klarlund N. and M\u00f8ller A. 2001. MONA Version 1.4 User Manual. Basic Research in Computer Science (BRICS) Notes Series NS-01-1. Department of Computer Science University of Aarhus Aarhus Denmark.  Klarlund N. and M\u00f8ller A. 2001. MONA Version 1.4 User Manual. Basic Research in Computer Science (BRICS) Notes Series NS-01-1. Department of Computer Science University of Aarhus Aarhus Denmark."},{"key":"e_1_2_1_23_1","volume-title":"Symposium on String Processing and Information Retrieval (SPIRE).","author":"Laurikari V.","year":"2000","unstructured":"Laurikari , V. 2000 . NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions . In Symposium on String Processing and Information Retrieval (SPIRE). Laurikari, V. 2000. NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions. In Symposium on String Processing and Information Retrieval (SPIRE)."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press","author":"Levin M. Y.","year":"2003","unstructured":"Levin , M. Y. 2003 . Compiling regular patterns . In Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press , New York, NY, 65--77. 10.1145\/944705.944712 Levin, M. Y. 2003. Compiling regular patterns. In Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming. ACM Press, New York, NY, 65--77. 10.1145\/944705.944712"},{"volume-title":"Document structure description 2.0. Tech. rep. Basic Research in Computer Science (BRICS). Department of Computer Science","author":"M\u00f8ller A.","key":"e_1_2_1_26_1","unstructured":"M\u00f8ller , A. 2003. Document structure description 2.0. Tech. rep. Basic Research in Computer Science (BRICS). Department of Computer Science , University of Aarhus , Aarhus, Denmark . M\u00f8ller, A. 2003. Document structure description 2.0. Tech. rep. Basic Research in Computer Science (BRICS). Department of Computer Science, University of Aarhus, Aarhus, Denmark."},{"key":"e_1_2_1_27_1","unstructured":"Murata M. 1999. Hedge automata: a formal model for XML schemata. Available online at http:\/\/www.geocities.com\/murata_makoto.  Murata M. 1999. Hedge automata: a formal model for XML schemata. Available online at http:\/\/www.geocities.com\/murata_makoto."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Twentieth ACM Symposium on Principles of Database Systems. ACM Press","author":"Murata M.","year":"2001","unstructured":"Murata , M. 2001 . Extended path expressions for XML . In Proceedings of the Twentieth ACM Symposium on Principles of Database Systems. ACM Press , New York, NY, 126--137. 10.1145\/375551.375569 Murata, M. 2001. Extended path expressions for XML. In Proceedings of the Twentieth ACM Symposium on Principles of Database Systems. ACM Press, New York, NY, 126--137. 10.1145\/375551.375569"},{"volume-title":"Proceedings of the Conference on Extreme Markup Languages (Montreal, P.Q., Canada).","author":"Murata M.","key":"e_1_2_1_29_1","unstructured":"Murata , M. , Lee , D. , and Mani , M . 2001. Taxonomy of XML schema languages using formal language theory . In Proceedings of the Conference on Extreme Markup Languages (Montreal, P.Q., Canada). Murata, M., Lee, D., and Mani, M. 2001. Taxonomy of XML schema languages using formal language theory. In Proceedings of the Conference on Extreme Markup Languages (Montreal, P.Q., Canada)."},{"key":"e_1_2_1_30_1","volume-title":"Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science","volume":"1530","author":"Neumann A.","unstructured":"Neumann , A. and Seidl , H . 1998. Locating matches of tree patterns in forests . In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science , vol. 1530 . Springer-Verlag, Berlin, Germany, 134--145. Neumann, A. and Seidl, H. 1998. Locating matches of tree patterns in forests. In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1530. Springer-Verlag, Berlin, Germany, 134--145."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_32_1","volume-title":"Semantics in Databases. Lecture Notes in Computer Science","volume":"2582","author":"Neven F.","unstructured":"Neven , F. and Schwentick , T . 2001. Automata- and logic-based pattern languages for tree-structured data . In Semantics in Databases. Lecture Notes in Computer Science , vol. 2582 . Springer. Berlin, Germany, 160--178. Neven, F. and Schwentick, T. 2001. Automata- and logic-based pattern languages for tree-structured data. In Semantics in Databases. Lecture Notes in Computer Science, vol. 2582. Springer. Berlin, Germany, 160--178."},{"key":"e_1_2_1_33_1","unstructured":"Sterling L. and Shapiro E. 1994. The Art of Prolog (second edition). MIT Press Cambridge MA.  Sterling L. and Shapiro E. 1994. The Art of Prolog (second edition). MIT Press Cambridge MA."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/507338.507360"},{"key":"e_1_2_1_35_1","unstructured":"Sumii E. May 2003. Personal communication.  Sumii E. May 2003. Personal communication."},{"volume-title":"Workshop on Types in Programming (TIP'02)","author":"Tabuchi N.","key":"e_1_2_1_36_1","unstructured":"Tabuchi , N. , Sumii , E. , and Yonezawa , A . 2002. Regular expression types for strings in a text processing language (extended abstract) . In Workshop on Types in Programming (TIP'02) . Go online to http:\/\/web.yl.is.s.u-tokyo.ac.jp\/~tabee\/xperl\/. Tabuchi, N., Sumii, E., and Yonezawa, A. 2002. Regular expression types for strings in a text processing language (extended abstract). In Workshop on Types in Programming (TIP'02). Go online to http:\/\/web.yl.is.s.u-tokyo.ac.jp\/~tabee\/xperl\/."},{"key":"e_1_2_1_37_1","unstructured":"Thompson H. S. Beech D. Maloney M. and Mendelsohn N. 2001. XML Schema. W3C Recommendation. World Wide Web Consortium. Go online to www.w3.org.  Thompson H. S. Beech D. Maloney M. and Mendelsohn N. 2001. XML Schema. W3C Recommendation. World Wide Web Consortium. Go online to www.w3.org."},{"key":"e_1_2_1_38_1","volume-title":"Elements of ML Programming","author":"Ullman J. D.","unstructured":"Ullman , J. D. 1998. Elements of ML Programming , 2 nd ed. Prentice Hall , Englewood Cliffs, NJ . Ullman, J. D. 1998. Elements of ML Programming, 2nd ed. Prentice Hall, Englewood Cliffs, NJ.","edition":"2"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM Press","author":"Vianu V.","year":"2001","unstructured":"Vianu , V. 2001 . A Web odyssey: From Codd to XML . In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM Press , New York, NY, 1--15. 10.1145\/375551.375554 Vianu, V. 2001. A Web odyssey: From Codd to XML. In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM Press, New York, NY, 1--15. 10.1145\/375551.375554"},{"key":"e_1_2_1_40_1","unstructured":"Wall L. Christiansen T. and Orwant J. 2000. Programming Perl 3rd ed. O'Reilly & Associates Sebastopol CA.   Wall L. Christiansen T. and Orwant J. 2000. Programming Perl 3rd ed. O'Reilly & Associates Sebastopol CA."},{"key":"e_1_2_1_41_1","unstructured":"Yergeau F. Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2004. Extensible Markup Language (XML) 1.0 (Third Edition). W3C Recommendation. World Wide Web Consortium. Go online to www.w3.org.  Yergeau F. Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2004. Extensible Markup Language (XML) 1.0 (Third Edition). W3C Recommendation. World Wide Web Consortium. Go online to www.w3.org."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1133651.1133652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1133651.1133652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:17Z","timestamp":1750278137000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1133651.1133652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1133651.1133652"],"URL":"https:\/\/doi.org\/10.1145\/1133651.1133652","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}