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