[Solved]: What does it mean to say that a language is "effectively closed" under an operation?

Problem Detail: 

I've been reading some formal language theory papers, and I've come across a term that I don't understand.

The paper will often refer to a set being "effectively closed under intersection" or other operations. What does "effectively" mean here? How does this differ from normal closure?

For reference, the paper I'm seeing these in is:

M. Daley and I. McQuillan. Formal modelling of viral gene compression. International Journal of Foundations of Computer Science, 16(3):453–469, 2005.

Asked By : jmite

Answered By : Hendrik Jan

"Effectively closed" means that the family is closed under the operation, and that the closure can be computed by giving an automaton/grammar for it (if the original languages are also given in such an effective representation). E.g., given a finite state automaton, we can actually find an automaton for the complement.

Then it is a natural question, whether there are examples of closure properties that are not effective. I know one right now. For a regular language $R$ and any language $L$ the quotient $R/L$ is again regular. There is no effective way to construct a FSA for that quotient if $L$ is e.g. recursively enumarable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11920