Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
"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.
