Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I want to find the largest regular language containing one set of strings but not another set.

So, I've got a programming problem and I've posed it in a good form above. Now what? How do I find a paper that talks about this or find out if it exists?

What I have access to:

  • Directory of Open Access Journals
  • arXiv
  • "Mathematics on the Web" index

For searching:

-Google Scholar - Scirus - CiteSeerX

And to my recent surprise some of the articles in "Annals of Math" are available freely in full text.

And if the paper is interesting enough I would pay a fee. Now, why is it so hard for me to find whether or not someone has answered this question? It shouldn't be so tedious. [End Rant]

So, the question. Given two sets $S$ and $T$ of $n$ text strings each that are on average $10^4$ characters long. I need an algorithm that finds the largest regular language containing all of $S$ and none of $T$.

This is interesting because I've already got a use for it. Given a set of example web pages that satisfy a certain property (like a set of Annals of Math pages on which there is a link for Full Text), and a set that don't, it should construct a regular expression that I could use to crawl a site and find all pages that satisfy the property (and list all free Annals papers on a web page). Now I could just construct a simple regex to do that, but then I'd have to do that each time and the regex required may not be as simple as *Full Article*

Oh yeah, the algorithm needs to construct a regular expression to represent the language.

share|improve this question
    
This is equivalent to finding the largest regular language not containing $T$. –  Enjoys Math Mar 22 '12 at 3:49
add comment

1 Answer

up vote 4 down vote accepted

Clearly, we must assume that $S \cap T$ is empty.

If $T$ is regular, then obviously $\Sigma^* - T$ is the largest such language.

If $T$ is not regular, then neither is $\Sigma^* - T$, and in that case, there is no such largest language: If $U$ is a regular language between $S$ and $\Sigma^* - T$, and $U$ is not all of $\Sigma^* - T$, then we can always add a missing string from $\Sigma^* - T$ to $U$, and the resulting language will remain regular.

Based on your description of your application, I'm not sure this is the problem you want to solve, though. It sounds like you want to take "good" and "bad" examples of strings and come up with a regex that matches all the goods and none of the bads. A big difficulty with this problem is defining what is considered an acceptable solution. Assuming your example sets are finite, it is easy to create solutions that undergeneralize (just list all the examples in $S$, and allow nothing else), or overgeneralize (allow everything in $\Sigma^* - T$). Neither of these extreme solutions would seem to be useful in practice. You could also specify a condition like "minimize the number of symbols in the regex", though that may turn out to be a very hard problem to solve (I haven't given it much thought).

share|improve this answer
    
Thanks. That is true. The complement doesn't do what I need. But T will be regular since it is finite (just checked Wikipedia). –  Enjoys Math Mar 22 '12 at 4:27
    
What I need to do is find the set of common substrings among the pages with Full Articles, then hand construct a regex that is relevant to Full Article link. Crawl the site and copy each Full Article link. –  Enjoys Math Mar 22 '12 at 4:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.