1
$\begingroup$

Wikipedia says:

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.

$\endgroup$
  • 2
    $\begingroup$ I think you pretty much answered your question already: AFLs are not necessarily closed against intersection, so you get a different family (of language classes). So what are you asking for? $\endgroup$ – Raphael Jun 2 '14 at 21:04
  • $\begingroup$ (1) why are intersection with regular languages required, not intersection? (2) Are there already concepts, if changing closure under intersection with regular language, to closure under intersection with languages in the same family? $\endgroup$ – Tim Jun 2 '14 at 21:05
  • 1
    $\begingroup$ ad 1) "why is a definition like this?" is almost always tough to answer; somebody needed a name for classes with these properties, period. ad 2) What do you mean by "are there already concepts"? "Can I define it?" vs "Does the concept have a name?" vs "Are there any such classes?" vs... $\endgroup$ – Raphael Jun 2 '14 at 21:09
  • $\begingroup$ (1) Closure under intersection is more perfect mathematically than closure under intersection with regular languages only. Formal theory choose to study the latter, which seems odd if without knowing the reason. (2) Does the concept have a name? (3) My questions are not just for tros, but for al the four concepts. $\endgroup$ – Tim Jun 2 '14 at 21:11
  • 2
    $\begingroup$ Why is one more perfect than the other? Names are given to concepts that are found to be more useful. Of course that may sometimes change with time. There are many more families of languages than appear in textbooks, that people will study for one reason or other. Closure under intersection with regular sets is nearly always the case (I do not recall an example where it is not). I guess closure under intersection within the family is not so frequent for families that have been considered interesting. You may also wonder whether it enables the proof of interesting other results. $\endgroup$ – babou Jun 2 '14 at 21:29
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$
  1. It is intersection with regular languages, as Wikipedia says (not intersection with other languages in the same family).

  2. Because. Because that's what the definition says. Changing the definition would give a different concept. For instance, context-free languages are closed under intersection with regular languages, but not under intersection with other context-free languages, as you point out. This is what the standard definition says, and it is a useful concept. Beyond that, I'm not sure what you expect from a "why" question; it's a definition, and it is what it is.

  3. I don't know if there is any standard name for such a concept.

$\endgroup$
2
$\begingroup$

Definitions are chosen, and associated with names, according to their utility in the development of the mathematical theory at hand. Sometimes they are defined very locally for a specific proof, but remain uninteresting outside that proof. Other are given a wider scope because they can be more widely useful.

There may be some aesthetics in the choice of definition, when it does reflect some deep structure of the problems, and that will contribute to usefulness. But a symmetry that is seldom encountered is probably not that useful, or indicative of deep mathematical structure.

I can only talk of my very limited experience. Closure under intersection with regular sets is almost ubiquitous for families of languges. No counter-example comes to my mind. Of course, it is always possible to contrive one, but not so easily (I guess) to contrive one that corresponds to a useful family of languages.

When you choose a definition, thus focussing you interest and your work on it, you have to ask yourself two questions:

  • How often will it apply to problems you may be interested in, and how inportant these problems are likely to be (though that may be hard to estimate)

  • How convenient is this definition is to derive general results that can be applied to whatever will fit the definition.

Trios and AFLs where defined as they have been by people who found that many families of languages met the corresponding definitions. Furthermore, from the definitions, there were able to prove a variety of results abstractedly for trios and AFLs, that can be applied without further effort to all these families.

They apparently had no incentive to do it for arbitrary intersection within the family. Hence no definition and no name, that I know of.

A further remark is that all these families include regular sets. Hence they are more likely to be closed under intersection with regular sets than under arbitrary intersection within the family (which does imply closure under intersection with regular sets). Hence the definition as chosen is more likely to be applicable, hence more generally useful. And it turn out to be already very useful by itself as remarked by Jan Hendrik.

The following is pure speculation on my part. It may also be that operations considered for closure correspond to interesting structural properties of languages. For example closure under union seems naturally associated with non-determinism (recall that deterministic context-free languages are not closed under union). It may be that there is no simple such property associated with intersection. But as I said, this is not based on hard understanding.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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