patternModerate
What does it mean to say that a language is "effectively closed" under an operation?
Viewed 0 times
whatsaymeanclosedeffectivelylanguageoperationunderthatdoes
Problem
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.
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.
Solution
"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.
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.
Context
StackExchange Computer Science Q#11920, answer score: 15
Revisions (0)
No revisions yet.