A trio is a family of languages closed under e-free homomorphism, inverse homomo

Question

A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language.

A full trio, also called a cone, is a trio closed under arbitrary homomorphism.

A (full) semi-AFL is a (full) trio closed under union.

A (full) AFL is a (full) semi-AFL closed under concatenation and the Kleene plus.

I am wondering if the four concepts are required to be closed under intersection with regular language, not intersection with languages in the same family?

why are intersection with regular languages required, not intersection?

I wonder what the concepts are if changing closure under intersection with regular language, to closure under intersection with languages in the same family?

I asked these because I saw that the recursively enumerable languages, recursive languages, context-sensitive languages, regular languages are closed under intersection with languages in the same families, while context-free languages are not

Explanation / Answer

Because it is a very natural set of operations: the full trio operations (morphism, inverse morphism, intersection with regular languages) exactly corresponds to closure under finite state transductions.

We can formulate results for such nice families. Requiring too many properties would exclude some families of languages. Who wants to miss the context-free languages?

Likewise the Boolean operations (intersection, union, complement) form a nice set, but we do not always require them.

The notion "intersection closed full AFL" is well studied

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.