>> The point is to figure out if one pattern is (partially) >> contained in another pattern and if strings matched >> by one pattern are also matched by another pattern >> (i.e. the set of strings mathing pattern 2 is a subset >> of the set of strings matching pattern 1.) The use >> case for this is to find ambiguities between rules using >> such related patterns such that one can test these >> patterns in groups (or, for XSLT, assign higher priority >> to the more specific pattern.)
Is this pattern optimization or pattern comparison? >> about my question whether there is a way to add >> relations between regex patterns (equality, subset, >> containment, etc.) I guess I'm missing something. Do you want Relational & Regexp fusion? Relational theory is seems so off the path of regexp. Do you have a detailed example? (Not that I could solve such a problem, I'm just curious) - malcolm >> -----Original Message----- >> From: Gunther Schadow >> [mailto:[EMAIL PROTECTED]] >> Sent: Tuesday, March 26, 2002 9:18 AM >> To: ORO Users List >> Subject: Re: Comparing two Regex *Patterns* >> >> >> Hi, >> >> about my question whether there is a way to >> add relations >> between regex patterns (equality, subset, containment, >> etc.) into ORO, I am pretty discouraged from >> browsing the >> literature. These questions have been >> addressed as early >> as in the 60s [1,2] and 70s [3,4] and even >> today the papers >> mostly talk about it in terms of decidability >> problems [5]. >> The best we might hope for is comparing for >> equality [2], >> which by itself, however, is not very useful >> (subsetting is >> the least that one would need to reason about >> ambiguities >> in regex-based systems.) This is all very entrenched >> in the nitty-gritties of computer science, and >> the best I >> hope for at this point is that someone embarks >> on a Ph.D. >> project tackling this by whatever means. A >> general solution >> seems quite unlikely, may be a constrained >> subset of regexes >> can be identified in which solutions can be >> analytically >> found or may be an approximate answer can be found on a >> larger subset of regexes. Any takers? :-) >> >> regards, >> -Gunther >> >> >> References: >> >> [1] Brzozowski JA. Derivatives of regular >> expressions. 1964; >> JACM;11(4);p481-94. >> >> [2] Ginzburg A. A procedure for checking >> equality of regular >> expressions. 1967;JACM;14(2);p355-62. >> >> [3] Stockmeyer LJ, Meyer AR. Word problems >> requiring exponential >> time: preliminary report. In Conference >> Record of Fifth Annual >> ACM Symposium on Theory of Computing 30 >> April-2 May 1973. p1-9. >> >> [4] Hunt HB, Rosenkrantz DJ. On equivalence >> and containment >> problems for formal languages. 1977; >> JACM;24(3);p387-96. >> >> [5] Calvanese D, DaGiacomo G, Lenzerini M. On >> the decidability >> of query containment under constraints. >> PODS '98, Seattle WA. >> >> >> >> -- >> Gunther Schadow, M.D., Ph.D. >> [EMAIL PROTECTED] >> Medical Information Scientist Regenstrief >> Institute for Health Care >> Adjunct Assistant Professor Indiana >> University School of Medicine >> tel:1(317)630-7960 >> http://aurora.regenstrief.org >> >> >> >> -- >> To unsubscribe, e-mail: >> <mailto:[EMAIL PROTECTED]> >> For additional commands, e-mail: >> <mailto:[EMAIL PROTECTED]> >> -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
